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

DOI10.1016/S0020-0190(99)00010-1zbMATH Open1338.68099WikidataQ114826254 ScholiaQ114826254MaRDI QIDQ294656FDOQ294656

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

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

• Title not available (Why is that?)
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The knowledge complexity of interactive proof-systems
• 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
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
• Statistical zero-knowledge languages can be recognized in two rounds

Cited In (1)

• Interactive proofs and the hardness of approximating cliques

This page was built for publication: The graph clustering problem has a perfect zero-knowledge interactive proof

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294656)