Strict polynomial-time in simulation and extraction

ABSTRACT

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain constant-round zero-knowledge proofs and proofs of knowledge (for NP), one had to allow simulators and knowledge-extractors to run in time which is only polynomial on the average (i.e., expected polynomial time). Whether or not allowing expected polynomial-time is necessary for obtaining constant-round zero-knowledge proofs and proofs of knowledge, has been posed as an important open question. This question is interesting not only for its theoretical ramifications, but also because expected polynomial time simulation is not closed under composition. Therefore, in some cases security is not maintained when a protocol that utilizes expected polynomial time simulation (or extraction) is used as a part of a larger protocol.A partial answer to the question of the necessity (or non-necessity) of expected polynomial-time was provided recently by Barak, who gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. His was also the first protocol that is not black-box zero-knowledge. That is, the simulator in his protocol utilizes the description of the code of the verifier in an essential way.In this paper, we completely resolve the question of expected polynomial-time in zero-knowledge arguments and arguments of knowledge. First, we show that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors. As in the simulator of Barak's zero-knowledge protocol, the extractor for our proof of knowledge is not black-box and uses the code of the prover in an essential way.On the negative side, we show that non-black-box techniques are essential to both strict polynomial-time simulation and extraction. That is, we show that no constant-round zero-knowledge argument (or proof) can have a strict polynomial-time black-box simulator. Similarly, we show that no constant-round zero-knowledge argument (or proof) of knowledge can have a strict polynomial-time black-box knowledge extractor. Thus, for constant-round black-box zero-knowledge arguments (resp., arguments of knowledge), it is imperative that the simulator (resp., extractor) be allowed to run in expected polynomial-time.

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 , Y. Lindell, Resettably-Sound Zero-Knowledge and its Applications, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.116, October 14-17, 2001
• 3: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 4: M. Blum. Coin flipping by phone. In The 24th IEEE Computer Conference, pages 133--137, 1982.
• 5: Gilles Brassard , Claude Crépeau , Moti Yung, Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds (extended abstract), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.192-195, November 1990, Houthalen, Belgium
• 6: 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]
• 7: 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]
• 8: Uriel Feige , Dror Lapidot , Adi Shamir, Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions, SIAM Journal on Computing, v.29 n.1, p.1-28, Feb. 2000 [doi>10.1137/S0097539792230010]
• 9: U. Feige. Alternative Models for Zero Knowledge Interactive Proofs. PhD thesis, Dept. of Computer Science, Weizmann Institute of Science, Israel, 1990.
• 10: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 11: 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
• 12: 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]
• 13: Goldreich. Notes on levin's theory of average-case complexity. In ECCR Technical Reports, 1997.
• 14: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 15: O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167--189, 1996.
• 16: 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]
• 17: 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]
• 18: 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]
• 19: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 20: Yehuda Lindell, Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.171-189, August 19-23, 2001
• 21: M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151--158, 1991.
• 22: R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. Technical Report TR-93-073, International Computer Science Institute, Berkeley, CA, Nov. 1993.
• 23: M. Tompa and H. Woll. Random self-reducibility and zero-knowledge interactive proofs of possession of information. In Proc. of 28th FOCS, 1987.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Experimentation, Performance, Theory