A note on efficient zero-knowledge proofs and arguments (extended abstract)

ABSTRACT

In this note, we present new zero-knowledge interactive proofs and arguments for languages in NP. To show that x &egr; L, with an error probability of at most 2-k, our zero-knowledge proof system requires O(|x|c1)+O(lgc2|x|)k ideal bit commitments, where c1 and c2 depend only on L. This construction is the first in the ideal bit commitment model that achieves large values of k more efficiently than by running k independent iterations of the base interactive proof system. Under suitable complexity assumptions, we exhibit zero knowledge arguments that require O(lgc|x|kl bits of communication, where c depends only on L, and l is the security parameter for the prover. This is the first construction in which the total amount of communication can be less than that needed to transmit the NP witness. Our protocols are based on efficiently checkable proofs for NP[4].

REFERENCES

• 1: Joan Boyar , Gilles Brassard , René Peralta, Subquadratic zero-knowledge, Proceedings of the 32nd annual symposium on Foundations of computer science, p.69-78, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185350]
• 2: G. Brassard and C. Cr#peau. Non-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond, Proc. of FOCS86.
• 3: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 4: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 5: Joan F. Boyar , Stuart A. Kurtz, A discrete logarithm implementation of perfect zero-knowledge blobs, Journal of Cryptology, v.2 n.2, p.63-76, 1990
• 6: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 7: S. Goldwasser, S. Micali, and R. Rivest. A Paradoxical Solution to the Signature Problem. Proc. of. FOCS84
• 8: O. Goldreich, S. Micali, and A. Wigderson. Proofs that Yield Nothing but Their Validity and a Methodology of Cryptographic Protocol Design, Proc. of FOCS86.
• 9: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 10: Russell Impagliazzo , Moti Yung, Direct Minimum-Knowledge Computations, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.40-51, August 16-20, 1987
• 11: J. Kilian, S. Micali and R. Ostrovsky. Minimum Resource Zero-Knowledge Proofs, Proc. of FOCS89.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

General Terms:
Performance, Theory