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.
- 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.Google Scholar
- B1.M. Blum, Coin Flipping by Telephone, IEEE COMPCON 1982, pp. 133-137.Google Scholar
- B2.M. Blum, unpublished manuscriptGoogle Scholar
- BBS.M. Blum, L. Blum and M. Shub,A simple and secure pseudo-randomnumber generator, SIAM Journal of Computing, 198.6 Google ScholarDigital Library
- BGGHMR.M. Ben-Or, O. Goldreich, S. Goldwasser, J. Haatad, S. Mica li, and P. Rogaway, to uppearGoogle Scholar
- BH.R. Boppana, J. Hastad and S. Zachos, Interactive Proofs Systems for CO-NP Imply Polynomial Time Hierarchy Collapse, }{n preperation.Google Scholar
- BM.M. Blum and S. Micali, How To Generate Sequences Of Cr~tptographically Strong Pseudo-Random Bits, SIAM J. on Computing, Vol. 13, Nov 1984, pp. 850-864 Google ScholarDigital Library
- DH.Diffie, W., and M.E. Hellman, New Directions in Cryptography, IEEE Trans. on. Inform. Theory, Google ScholarDigital Library
- F.L. Fortnow, The Complexity of Perfect Zero- Knowledge, Proc. 19th ann. Syrup. on Theory of Computing, New ~ ork, 1987. Google ScholarDigital Library
- FFS.Feige, Fiat and A. Shamir, Zero. knowledge proofs of identity, Proceedings of the tgth Annual ACM Syrup. on Theory of Computing, 1987, pp. 210-217 Google ScholarDigital Library
- GM.S. Goldwasser, and S. Micali, Probabilistic Encryption, JCSS Vol. 28, No. 2, April 1984.Google Scholar
- GMR.S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complezity of Interactive Proof- Systems, To appear SIAM J. on Computing (manuscript available from authors). Google ScholarDigital Library
- GoMiRi.S. Goldwa~er, S. Micali, and R. Rivest, A Digital Signature Scheme Secure Against Adaptive, Chosen Ugphertext Attack To appear in SIAM J. on Computing (available from authors) Google ScholarDigital Library
- 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., 1982Google ScholarDigital Library
- 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.Google ScholarDigital Library
- GMW2.O.Goldreich, S. Micali and A. Wigderson, How to Play An~t Mental Game, Proceedings of the 19th Annual ACM Syrup. on Theory of Computing, 1987, pp. 218-229. Google ScholarDigital Library
- GS.S. Goldwasser and M. Sipser, Private Coins versus Public Coins in Interactive .Proof S~lsiems, Proceedings of the 18th Annual ACM Sympl on Theory of Computing, 1986, pp. 59-68. Google ScholarDigital Library
- R.M. Rabin, Digitalized signatures and public, key functions as intractable as factorization, MIT/LCS/TR-212, Technical report MIT, 1978 Google ScholarDigital Library
- Y.A.Yao, Theory and Application of Trapdoor Functions, Proc. of 23rd FOCS, IEEE, Nov., 1982, pp. 80-91.Google Scholar
Index Terms
- Non-interactive zero-knowledge and its applications
Recommendations
Pairing-based non-interactive zero-knowledge proofs
Pairing'10: Proceedings of the 4th international conference on Pairing-based cryptographyA non-interactive zero-knowledge proof permits the construction of a proof of the truth of a statement that reveals nothing else but the fact that the statement is true. Non-interactive zero-knowledge proofs are used in the construction of numerous ...
An enhanced Kerberos protocol with non-interactive zero-knowledge proof
As one of the most important trusted third-party-based authentication protocols, Kerberos is widely used to provide authentication service in distributed networks. However, it is vulnerable to common brute force password-guessing attacks because of its ...
Comments