Abstract
A cryptographic scheme is “provably secure” if an attack on the scheme implies an attack on the underlying primitives it employs. A cryptographic scheme is “provably secure in the random-oracle model” if it uses a cryptographic hash function F and is provably secure when F is modeled by a public random function. Demonstrating that a crypto graphic scheme is provably secure in the random-oracle model engenders much assurance in the scheme's correctness. But there may remain some lingering fear that the concrete hash function which instantiates the random oracle differs from a random function in some significant way. So it is good to limit reliance on random oracles. Here we describe two encryption schemes which use their random oracles in a rather limited way. The schemes achieve semantic security and plaintext awareness under specified assumptions. One scheme uses the RSA primitive; another uses Diffie-Hellman. In either case messages longer than the modulus length can be safely and directly encrypted without relying on the hash functions modeled as random-oracles to be good for private-key encryption.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
M. Bellare, R. Canetti and H. Krawczyk, “Keying hash functions for message authentication,” Advances in Cryptology — Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed., Springer-Verlag, 1996.
M. Bellare and P. Rogaway, “Minimizing the use of random oracles in authenticated encryption schemes.” More complete version of this paper, http://wwwcsif.cs.ucdavis.edu/-rogaway.
M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” Proceedings of the First Annual Conference on Computer and Communications Security, ACM, 1993.
M. Bellare and P. Rogaway, “Optimal asymmetric encryption-How to encrypt with RSA”. Current version available at URL of either author. Earlier version in Advances in Cryptology — Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed., Springer-Verlag, 1994.
M. Bellare and P. Rogaway, “The exact security of digital signatures-How to sign with RSA and Rabin.” Current version available at URL of either author. Earlier version in Advances in Cryptology — Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996.
M. Blum and S. Goldwasser, “An efficient probabilistic public-key encryption scheme which hides all partial information,” Advances in Cryptology — Crypto 84 Proceedings, Lecture Notes in Computer Science Vol. 196, R. Blakely ed., Springer-Verlag, 1984.
I. Damgård, “Towards practical public key cryptosystems secure against chosen ciphertext attacks,” Advances in Cryptology — Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991.
D. Dolev, C. Dwork and M. Naor, “Non-malleable cryptography,” Proceedings of the 23rd Annual Symposium on Theory of Computing, ACM, 1991.
C. ELLISON, personal communication, September 1996.
S. Goldwasser and S. Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences28, 270–299, April 1984.
IEEE P1363 COMMITTEE, IEEE P1363 Working Draft, February 6, 1997. Lisa Yiquin, editor. Current draft in http://stdsbbs.ieee.org/groups/1363/index.html.
D. Johnson and S. Matyas. “Asymmetric encryption: evolution and enhancements,” CryptoBytes, Vol. 2, No. 1, Spring 1996.
D. Johnson, A. Lee, W. Martin, S. MATYAS and J. Wilkins, “Hybrid key distribution scheme giving key record recovery,” IBM Technical Disclosure Bulletin, 37(2A), 5–16, February 1994.
D. Johnson, S. Matyas, M. Peyravian, “Encryption of long blocks using a short-block encryption procedure.” November 1996. Available in http://stdsbbs.ieee.org/groups/1363/index.html.
IEEE P1363 COMMITTEE, Burt Kaliski, chair. Unpublished e-mail memorandum with subject heading: “Technical Subcommittee on Encryption Schemes.” September 10, 1996.
M. Luby and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions.” SIAM J. Computation, Vol. 17, No. 2, April 1988.
S. Matyas, M. Peyravian, A. Roginsky, “Security analysis of Feistel ladder formatting procedure.” March 1997. Available in http://stdsbbs.ieee.org/groups/1363/index.html.
M. Naor and M. Yung, “Public-key cryptosystems provably secure against chosen ciphertext attacks,” Proceedings of the 22nd Annual Symposium on Theory of Computing, ACM, 1990.
D. Pointcheval and J. Stern, “Security proofs for signatures,” Advances in Cryptology — Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996.
R. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public key cryptosystems,” CALM 21 (1978).
RSA Data Security, Inc., “PKCS #1: RSA Encryption Standard,” June 1991.
Y. Zheng, “Public key authenticated encryption schemes using universal hashing,” (15 Oct 96). Unpublished contribution to P1363. ftp://stdsbbs.ieee.org/pub/p1363/contributions/aes-uhf.ps
Y. Zheng and J. Seberry, “Immunizing public key cryptosystems against chosen ciphertext attack.” IEEE Journal on Selected Areas in Communications, vol. 11, no. 5, 715–724 (1993).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Bellare, M., Rogaway, P. (1997). Minimizing the use of random oracles in authenticated encryption schemes. In: Han, Y., Okamoto, T., Qing, S. (eds) Information and Communications Security. ICICS 1997. Lecture Notes in Computer Science, vol 1334. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028457
Download citation
DOI: https://doi.org/10.1007/BFb0028457
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63696-0
Online ISBN: 978-3-540-69628-5
eBook Packages: Springer Book Archive