Non-interactive zero-knowledge and its applications

ABSTRACT

We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

REFERENCES

• ACGS: W. Alexi, B. Chor, O. Goldreich, and C. Schnorr RSA/Rabin Bits Are 1/2+ 1/votv(logN) Secure, To appear SIAM J. on Computing.
• B1: M. Blum, Coin Flipping by Telephone, IEEE COMPCON 1982, pp. 133-137.
• B2: M. Blum, unpublished manuscript
• BBS: L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
• BGGHMR: M. Ben-Or, O. Goldreich, S. Goldwasser, J. Haatad, S. Mica li, and P. Rogaway, to uppear
• BH: R. Boppana, J. Hastad and S. Zachos, Interactive Proofs Systems for CO-NP Imply Polynomial Time Hierarchy Collapse, }{n preperation.
• BM: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• DH: Diffie, W., and M.E. Hellman, New Directions in Cryptography, IEEE Trans. on. Inform. Theory,
• F: L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States [doi>10.1145/28395.28418]
• FFS: U. Fiege , A. Fiat , A. Shamir, Zero knowledge proofs of identity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.210-217, January 1987, New York, New York, United States [doi>10.1145/28395.28419]
• GM: S. Goldwasser, and S. Micali, Probabilistic Encryption, JCSS Vol. 28, No. 2, April 1984.
• GMR: 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]
• GoMiRi: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• GMT: S. Goldwasser, S. Micali, and P. Tong, Why and how to establish a perivate code in a public network, Proc. 23rd Symp. on Foundations of Computer Science, Chicago, Ill., 1982
• GMW: O. Goldreich, S. Micali and A. Wigderson, Proofs that Yield Nothing but their Validity and a Methodology of C~ptographic Design, Proc. of FOCS 1986.
• GMW2: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• GS: S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
• R: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• Y: A.Yao, Theory and Application of Trapdoor Functions, Proc. of 23rd FOCS, IEEE, Nov., 1982, pp. 80-91.

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.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Performance, Theory