Subquadratic zero-knowledge
- 1 November 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (6) , 1169-1193
- https://doi.org/10.1145/227683.227686
Abstract
We improve on the communication complexity of zero-knowledge proof systems. Let C bea boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiabilityof C require the use of \Omega\Gamma kn) bit commitments in order to achieve a probability ofundetected cheating below 2\Gammak. In the case k = n, the communication complexity ofthese protocols istherefore\Omega\Gamman2) bit commitments.In this paper, we present a zero-knowledge proof system for achieving...Keywords
This publication has 21 references indexed in Scilit:
- Bounds on certain multiplications of affine combinationsDiscrete Applied Mathematics, 1994
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- On the distribution of quadratic residues and nonresidues modulo a prime numberMathematics of Computation, 1992
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- How convincing is your protocol?ACM SIGACT News, 1991
- Realistic analysis of some randomized algorithmsJournal of Computer and System Sciences, 1991
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- Minimum disclosure proofs of knowledgeJournal of Computer and System Sciences, 1988
- Probabilistic encryptionJournal of Computer and System Sciences, 1984
- On Non-Averaging Sets of IntegersCanadian Journal of Mathematics, 1953