Mihir Bellare
Phillip Rogaway
ABSTRACT
We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol P is produced by first devising and proving correct a protocol PR for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function h. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.
- 1.D. BBAVBR, S. MICALI AND P. ROGAWAY, "The round complexity of secure protocols," STOC 90.]]Google Scholar
- 2.l~. BELLARE AND S. MICALI, "How to sign given any trapdoor permutation," JACM Vol. 39, No. I, 214-233, January 1992.]] Google ScholarDigital Library
- 3.L. BLUM, M. BLUM AND M. SHUB, "A simple unpredictable pseudo-random number generator," SIAM Journa/on Computing Vol. 15, No. 2, 364-383, May 1986.]] Google ScholarDigital Library
- 4.M. BLUM AND S. GOLDWASSBrt, "An efficient probabilistic public-key encryption scheme which hides all partial information," Crypto 84.]] Google ScholarDigital Library
- 5.M. BLUM AND S. MIOALI, "How to generate cryptographically strong sequences of pseudo-random bits," SIAM Journal on Computing, Vol. 13, No. 4, 850-864, November 1984.]] Google ScholarDigital Library
- 6.M. BLUM, P. FELDMAN AND S. MIOALI, "Noninteractive zero knowledge and its applications," STOC 88.]] Google ScholarDigital Library
- 7.M. BLtrM, A. DB SA~TIS, S. MICALI AND G. PBR- SIANO, "Non-interactive zero-knowledge proof systems," SIAM Journal on Computing, 20(4), 1084-1118 (December 1991).]] Google ScholarDigital Library
- 8.B. D~.N BOER AND A. BOSSELAERS, "Collisions for the compression function of MDS," Eurocrypt 93.]] Google ScholarDigital Library
- 9.G. BRASSARD, D. CHAUM AND C. CB~PBAU, "Minimum disclosure proofs of knowledge," JCSS Vol. 37, No. 2, 156-189, October 1988.]] Google ScholarDigital Library
- 10.i. DAMG~RD, "Towards practical public key cryptosystems secure against chosen ciphertext attacks," Crypto 91.]] Google ScholarDigital Library
- 11.A. DE SANTIS AND G. PER$IANO, "Zero-knowledge proofs of knowledge without interaction" FOCS 92.]] Google ScholarDigital Library
- 12.W. DIFFIE AND M. E. HELLMAN, "New directions in cryptography," IEEE Trans. in.fo. Theory IT-22, 644- 654 (November 1976).]]Google Scholar
- 13.D. DOLBV, C. DwoP~ AND M. NAOR, "Non-malleable cryptography," STOC 91.]] Google ScholarDigital Library
- 14.A. FIAT AND A. SHAMIR, "How to prove yourself: practical solutions to identification and signature problems," Crypto 86.]] Google ScholarDigital Library
- 15.U. FZIGB, A. FIAT AND A. SHAMIR, "Zero knowledge proofs of identity," Journal of Cryptology, Vol. 1, pp. 77-94 (1987).]] Google ScholarDigital Library
- 16.U. FBmB, D. LAPmOT, AND A. SHAMm, "Multiple non-interactive zero-knowledge proofs based on a single random string," FOCS 90.]]Google Scholar
- 17.Z. GALIL, S. HABBR AND M. YUNG, "Symmetric pub. lic key cryptosystems," manuscript, July 1989.]]Google Scholar
- 18.0. GOLDREICH, "A uniform complexity treatment of encryption and zero-knowledge," Journal of Cryptology, Vol. 6, pp. 21-53 (1993).]]Google ScholarDigital Library
- 19.O. GOLDI~ICH, "Foundations of cryptography," Class notes, Spring 1989, Technion University.]] Google ScholarDigital Library
- 20.O. GOLDREICH, S. GOLDWASESR AND S. MICALI, "How to construct random functions," Journa/of She ACM, Vol. 33, No. 4, 210-217, (1986).]] Google ScholarDigital Library
- 21.O. GOLDI~ICH, S. GOLDWASSBR AND S. MICALI, "On the cryptographic applications of random functions," Crypto 84.]] Google ScholarDigital Library
- 22.O. GOLDRBICH AND H. KRAWOZYK, "On the composition of zero knowledge proof systems," ICALP 90.]] Google ScholarDigital Library
- 23.O. GOLDREIOH AND L. LEVIN, "A hard predicate for all one-way functions," STOC 89.]] Google ScholarDigital Library
- 24.S. GOLDWASSBR AND S. MICALI, "Probabilistic encryption," J. o/' Computer and System Sciences 28, 270-299, April 1984.]]Google ScholarCross Ref
- 25.S. GOLDWA$SER, S. MICALI AND C. I~kCKOFF, "The knowledge complexity of interactive proof systems," SIAM J. of Comp., Vol. 18, No. i, pp. 186-208, February 1989.]] Google ScholarDigital Library
- 26.S. GOLDWASSBR, S. MICALI AND R. RIVEST, "A digital signature scheme secure against adaptive chosenmessage attacks," SIAM Journa/ of Computing, 17(2):281-308, April 1988.]] Google ScholarDigital Library
- 27.R. IMPAGLIAZZO AND S. RUDICH, "Limits on the provable consequences of one-way permutations," STOC 89.]] Google ScholarDigital Library
- 28.T. LEIGHTON AND S. MICALI, "Provably fast and secure digital signature algorithms based on secure hash functions," Manuscript, March 1993.]]Google Scholar
- 29.T. LEIGHTON AND S. MICALI, "New approaches to secret key exchange," Crypto 93.]]Google Scholar
- 30.M. LuBY AND C. RACKOFF, "How to construct pseudorandom permutations from pseudorandom functions," SIAM J. Computation, Vol. 17, No. 2, April 1988.]] Google ScholarDigital Library
- 31.M. LUBY AND C. RACKOFF, aA study of password security," manuscript.]]Google Scholar
- 32.S. MICALI, "CS proofs," Manuscript.]]Google Scholar
- 33.S. MICALI, C. I~ACKOFF AND B. SLOAN, "The notion of security for probabilistic cryptosystems," SIAM J. of Computing, April 1988.]] Google ScholarDigital Library
- 34.M. NAOR AND M. YUNG, "Public-key cryptosystems provably secure against chosen ciphertext attacks," STOC 90.]] Google ScholarDigital Library
- 35.M. RABIN, "Digitalized signatures and public-key functions as intractable as factorization," MIT Laboratory for Computer Science TR-212, January 1979.]] Google ScholarDigital Library
- 36.C. RACKOFF AND D. SIMON, "Non-interactive zeroknowledge proof of knowledge and chosen ciphertext attack," Crypto 91.]] Google ScholarDigital Library
- 37.R. RIVBST, "The MD5 message-digest algorithm," IETF Network Working Group, RFC 1321, April 1992.]] Google ScholarDigital Library
- 38.R. RIVEST, A. SHAMIR, AND L. ADLEMAN, "A method for obtaining digital signatures and public key cryptosystems," CACM 21 (1978).]] Google ScholarDigital Library
- 39.RSA DATA SECURITY, INC., "PKCS #i: RSA Encryption Standard," June 1991]]Google Scholar
- 40.P. ROGAWAY AND B. BLAKLBY, "An asymmetric authentication protocol," IBM Technical Disclosure Bulletin (1993).]]Google Scholar
- 41.G. TSUDIK, "Message authentication with one-way hash functions," IEEE INFOCOM '92.]] Google ScholarDigital Library
- 42.H. WILLIA}~IS, "A modification of the RSA public key encryption procedure," IEEE ~ransacfions on Information Theory, Vol. IT-26, No. 6, November 1980.]]Google Scholar
- 43.A. YAO, "Theory and apphcations of trapdoor functions," FOCS 82.]] Google ScholarCross Ref
- 44.Y. ZH~NG AND J. SBBBRP~Y, "Practical approaches to attaining security against adaptively chosen ciphertext attacks," Crypto 92.]] Google ScholarDigital Library
Index Terms
- Random oracles are practical: a paradigm for designing efficient protocols
Recommendations
Secure universal designated verifier signature without random oracles
In Asiacrypt 2003, the concept of universal designated verifier signature (UDVS) was introduced by Steinfeld, Bull, Wang and Pieprzyk. In the new paradigm, any signature holder (not necessarily the signer) can designate the publicly verifiable signature ...
Designated verifier proxy signature scheme without random oracles
In a designated verifier proxy signature scheme, one can delegate his or her signing capability to another user in such a way that the latter can sign messages on behalf of the former, but the validity of the resulting signatures can only be verified by ...
Secure public-key encryption scheme without random oracles
Since the first practical and secure public-key encryption scheme without random oracles proposed by Cramer and Shoup in 1998, Cramer-Shoup's scheme and its variants remained the only practical and secure public-key encryption scheme without random ...
Comments