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

DOI10.1016/S0020-0190(99)00010-1MaRDI QIDQ294656zbMATHWikidataFDO

Authors 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)

Recommendations

• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Statistical zero-knowledge languages can be recognized in two rounds
• scientific article; zbMATH DE number 94166
• Interactive proofs and the hardness of approximating cliques
• scientific article; zbMATH DE number 1952907

Cites work

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

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)