The graph clustering problem has a perfect zero-knowledge interactive proof

DOI10.1016/S0020-0190(99)00010-1zbMath1338.68099WikidataQ114826254 ScholiaQ114826254MaRDI QIDQ294656

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Oded Goldreich

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019099000101?np=y

zbMATH Keywords

computational complexitycryptographygraph isomorphismzero-knowledge interactive proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60)

Cites Work

• Unnamed Item
• Statistical zero-knowledge languages can be recognized in two rounds
• Sorting in \(c \log n\) parallel steps
• Practic zero-knowledge proofs: Giving hints and using deficiencies
• A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
• Quantifying knowledge complexity
• Definitions and properties of zero-knowledge proof systems
• Short monotone formulae for the majority function
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The knowledge complexity of interactive proof-systems
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables