2-round zero knowledge and proof auditors

ABSTRACT

We construct 2-round (ie, 2-message), public-coin, black-box (concurrent) zero-knowledge proof systems and arguments for any language in NP under the assumption that the prover is resource-bounded during the execution of the protocol.

REFERENCES

• 1: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 2: 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
• 3: 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
• 4: Dan Boneh , Moni Naor, Timed Commitments, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.236-254, August 20-24, 2000
• 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: 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]
• 7: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 8: C. Dwork , M. Naor, Zaps and their applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.283, November 12-14, 2000
• 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: C. Dwork and L. Stockmeyer. 2-round zero knowledge and proof auditors. http://www.almaden.ibm.com/cs/people/stock/zebra.ps.
• 12: 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
• 13: 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]
• 14: Oded Goldreich , Shafi Goldwasser , Shai Halevi, Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.105-111, August 17-21, 1997
• 15: O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for NP. J. Crypto., 9(3):167--190, 1996.
• 16: 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]
• 17: S Goldwasser , J Kilian, Almost all primes can be quickly certified, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.316-329, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12162]
• 18: S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28:270--299, 1984.
• 19: 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]
• 20: R. Impagliazzo, M. Naor, O. Reingold, and A. Ahamir, 1998. Personal communication.
• 21: J. Kilian and E. Petrank. An efficient non-interactive zero-knowledge proof system for NP with general assumptions. J. Crypto, 11(1):1--27, 1998.
• 22: 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
• 23: J. Kilian, E. Petrank, and R. Richardson. On concurrent and resettable zero-knowledge proofs for NP. http://www.cs.technion.ac.il/~erez/publications.html.
• 24: R. Richardson and J. Kilian. On the concurrent composition of zero-knowledge proofs. In EUROCRYPT'99, LNCS Vol. 1592, pages 415--431. Springer-Verlag, 1999.
• 25: R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press, 1978.
• 26: 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: Interactive and reactive computation

General Terms:
Algorithms, Security, Theory

Keywords:
advice bound, cryptography, interactive proof systems, timed protocol, zap, zero knowledge