Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

ABSTRACT

We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least \tilde&OHgr;(log n) rounds of interaction. This result substantially improves over previous lower bounds, and is the first bound to rule out the possibility of constant-round black-box concurrent zero-knowledge. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in ~$\NP$.

REFERENCES

• 1: Mihir Bellare , Russell Impagliazzo , Moni Naor, Does Parallel Repetition Lower the Error in Computationally Sound Protocols?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.374, October 19-22, 1997
• 2: M. Bellare , S. Micali , R. Ostrovsky, Perfect zero-knowledge in constant rounds, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.482-493, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100283]
• 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: 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]
• 5: 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]
• 6: R. Canetti, J. Kilian, E. Petrank and Alon Rosen. Black-Box Concurrent Zero-Knowledge Requires (log n) rounds. In IACR eprint archive, 2001.
• 7: I. Damgard. Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In EuroCrypt2000, LNCS 1807, pages 418-430, 2000.
• 8: 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]
• 9: 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
• 10: U. Feige. Ph.D. thesis, Weizmann Institute of Science, 1990.
• 11: 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]
• 12: O. Goldreich. Foundations of Cryptography - Fragments of a Book. Available from http://theory.lcs.mit.edu/oded/frag.html.
• 13: O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. Jour. of Cryptology, Vol. 9, No. 2, pages 167-189, 1996.
• 14: 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]
• 15: 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]
• 16: O. Goldreich and Y. Oren. Definitions and Properties of Zero-Knowledge Proof Systems. Jour. of Cryptology, Vol. 7, No. 1, pages 1-32, 1994.
• 17: 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]
• 18: Satoshi Hada , Toshiaki Tanaka, On the Existence of 3-Round Zero-Knowledge Protocols, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.408-423, August 23-27, 1998
• 19: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 20: Joe Kilian , Erez Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.560-569, July 2001, Hersonissos, Greece [doi>10.1145/380752.380851]
• 21: 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
• 22: M. Naor. Bit Commitment using Pseudorandomness. Jour. of Cryptology, Vol. 4, pages 151-158, 1991.
• 23: R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In EuroCrypt99, Springer LNCS 1592, pages 415-431, 1999.
• 24: 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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

General Terms:
Languages, Performance, Theory, Verification