Concurrent zero-knowledge with timing, revisited

ABSTRACT

Following Dwork, Naor, and Sahai (30th STOC, 1998), we consider concurrent execution of protocols in a semi-synchronized network. Specifically, we assume that each party holds a local clock such that a constant bound on the relative rates of these clocks is a-priori known, and consider protocols that employ time-driven operations (i.e., time-out in-coming messages and delay out-going messages).We show that the constant-round zero-knowledge proof for NP of Goldreich and Kahan (Jour. of Crypto., 1996) preserves its security when polynomially-many independent copies are executed concurrently under the above timing model.We stress that our main result establishes zero-knowledge of interactive proofs, whereas the results of Dwork et al are either for zero-knowledge arguments or for a weak notion of zero-knowledge (called &egr;-knowledge) proofs.Our analysis identifies two extreme schedulings of concurrent executions under the above timing model: the first is the case of parallel execution of polynomially-many copies, and the second is of concurrent execution of polynomially-many copies such the number of copies that are simultaneously active at any time is bounded by a constant (i.e., bounded simultaneity). Dealing with each of these extreme cases is of independent interest, and the general result (regarding concurrent executions under the timing model) is obtained by combining the two treatments.

REFERENCES

• 1: B. Barak (Machtey Award Co-winner), How to Go Beyond the Black-Box Simulation Barrier, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.106, October 14-17, 2001
• 2: B. Barak and Y. Lindell. Non-Black-Box Proofs of Knowledge (tentative title). In preparation, 2001.
• 3: 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
• 4: M. Bellare, M. Jakobsson and M. Yung. Round-Optimal Zero-Knowledge Arguments based on any One-Way Function. In EuroCrypt'97, Springer-Verlag LNCS Vol. 1233, pages 280--305.
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: I. Damgård. Efficient Concurrent Zero-Knowledge in the Auxiliary String Model. In Eurocrypt'00, 2000.
• 10: 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]
• 11: 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]
• 12: 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
• 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: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 15: O. Goldreich. Concurrent Zero-Knowledge With Timing, Revisited. ECCC, TR01-091, 2001.
• 16: O. Goldreich and A. Kahan. How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. of Crypto., Vol. 9, No. 2, pages 167--189, 1996. Preliminary versions date to 1988.
• 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: O. Goldreich and Y. Oren. Definitions and Properties of Zero-Knowledge Proof Systems. J. of Crypto., Vol. 7, No. 1, pages 1--32, 1994.
• 20: S. Goldwasser and S. Micali. Probabilistic Encryption. JCSS, Vol. 28, No. 2, pages 270--299, 1984. Preliminary version in 14th STOC, 1982.
• 21: 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]
• 22: 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]
• 23: 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]
• 24: 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]
• 25: 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
• 26: M. Naor. Bit Commitment using Pseudorandom Generators. J. of Crypto., Vol. 4, pages 151--158, 1991.
• 27: R. Richardson and J. Kilian. On the Concurrent Composition of Zero-Knowledge Proofs. In EuroCrypt99, Springer LNCS 1592, pages 415--413.
• 28: A.C. Yao. Theory and Application of Trapdoor Functions. In 23rd FOCS, pages 80--91, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Theory

Keywords:
black-box simulation, concurrent composition, parallel composition, proofs versus arguments, timing assumptions, zero-Knowledge