Subquadratic Zero-Knowledge

The communication complexity of zero-knowledge proof systems is improved. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega (kn) bit commitments in order to achieve a probability of undetected cheating not greater than 2/sup -k/. In the case k=n, the communication complexity of these protocols is therefore Omega (n/sup 2/) bit commitments. A zero-knowledge proof is given for achieving the same goal with only O(n/sup m/+k square root n/sup m/) bit commitments, where m=1+ epsilon /sub n/ and epsilon /sub n/ goes to zero as n goes to infinity. In the case k=n, this is O(n square root n/sup m/). Moreover, only O(k) commitments need ever be opened, which is interesting if committing to a bit is significantly less expensive than opening a commitment. >

Authors

• Joan Boyar
• Gilles Brassard
• René Peralta 0001

Keywords

• Circuits
• Complexity theory
• Cryptographic protocols
• Costs
• Polynomials
• Cryptography
• Contracts
• Computer science
• H infinity control
• Confidence Level
• Decoding
• Matrix Size
• Matrix Production
• Matrix Multiplication
• Dot Product
• Complex Communication
• Preprocessing Stage
• Non-interactive
• Pseudo-random Sequence
• Pseudo-random Number Generator
• Bit Length
• NOT Gate
• Polylogarithmic
• Zero-knowledge Proof