Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

ABSTRACT

A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. Richardson and Kilian have shown that there exists a concurrent zero-knowledge proof for any language in NP, but with round complexity polynomial in the maximum number of concurrent proofs. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a poly-logarithmic round complexity: specifically, &ohgr;(log^2 k) rounds given at most k concurrent proofs. Finally, we show that a simple modification of our proof is a resettable zero-knowledge proof for NP, with &ohgr;(log^2 k) rounds; previously known protocols required a polynomial number of rounds.

REFERENCES

• 1: 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]
• 2: Gilles Brassard , Claude Crépeau , Moti Yung, Constant-round perfect zero-knowledge computationally convincing protocols, Theoretical Computer Science, v.84 n.1, p.23-52, July 22, 1991 [doi>10.1016/0304-3975(91)90259-5]
• 3: Ran Canetti , Oded Goldreich , Shafi Goldwasser , Silvio Micali, Resettable zero-knowledge (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.235-244, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335334]
• 4: Ran Canetti , Joe Kilian , Erez Petrank , Alon Rosen, Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.570-579, July 2001, Hersonissos, Greece [doi>10.1145/380752.380852]
• 5: Giovanni Di Crescenzo , Rafail Ostrovsky, On Concurrent Zero-Knowledge with Pre-processing, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.485-502, August 15-19, 1999
• 6: I. Damgard. "Efficient Concurrent Zero-Knowledge in the Auxiliary String Model." Advances in Cryptology - Eurocrypt 2000 Proceedings, Lecture Notes in Computer Science, Berlin: Springer-Verlag, 2000.
• 7: Ivan B. Damgård , Torben P. Pedersen , Birgit Pfitzmann, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.250-265, January 1994, Santa Barbara, California, United States
• 8: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 9: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 10: Cynthia Dwork , Amit Sahai, Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.442-457, August 23-27, 1998
• 11: U. Feige. Ph.D. thesis, Weizmann Institute of Science, 1990.
• 12: U. Feige, D. Lapidot and A. Shamir. Multiple non-interactive zero-knowledge proofs based on a singe random string. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, pages 308-317, 1990.
• 13: Uriel Feige , Adi Shamir, Zero knowledge proofs of knowledge in two rounds, Proceedings on Advances in cryptology, p.526-544, July 1989, Santa Barbara, California, United States
• 14: U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
• 15: O. Goldreich. Foundation of Cryptography - Fragments of a Book . Available from the Electronic Colloquium on Computational Complexity (ECCC) http://www.eccc.uni-trier.de/eccc/, February 1995.
• 16: O. Goldreich and A. Kahan, "How to Construct Constant-Round Zero-Knowledge Proof Systems for NP", Journal of Cryptology, Vol. 9, No. 2, 1996, pp. 167-189.
• 17: Oded Goldreich , Hugo Krawczyk, On the Composition of Zero-Knowledge Proof Systems, SIAM Journal on Computing, v.25 n.1, p.169-192, Feb. 1996 [doi>10.1137/S0097539791220688]
• 18: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 19: Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1-32, Winter 1994.
• 20: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• 21: 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]
• 22: J. Kilian. Zero-Knowledge with Log-Space Verifiers Proceedings, 29th annual IEEE Symposium on the Foundations of Computer Science.
• 23: J. Kilian and E. Petrank. Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds. Available at http://www.cs.technion.ac.il/erez/publications.html
• 24: Joe Kilian , Erez Petrank , Charles Rackoff, Lower Bounds for Zero Knowledge on the Internet, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.484, November 08-11, 1998
• 25: M. Naor. "Bit Commitment Using Pseudo-Randomness,", Journal of Cryptology, vol. 4, 1991, pp.151-158.
• 26: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 27: Y. Oren. On the cunning powers of cheating verifiers: Some observations about zero knowledge proofs. In Ashok K. Chandra, editor, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 462-471, Los Angeles, CA, October 1987. IEEE Computer Society Press.
• 28: Ransom Richardson and Joe Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In Proceeedings of Advances in Cryptology - EUROCRYPT '99, May 1999, Lecture Notes in Computer Science Vol. 1592 Springer 1999, pp. 415-431
• 29: Alon Rosen, A Note on the Round-Complexity of Concurrent Zero-Knowledge, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.451-468, August 20-24, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Performance, Theory, Verification