Abstract
The random oracle model is a very convenient setting for designing cryptographic protocols. In this idealized model all parties have access to a common, public random function, called a random oracle. Protocols in this model are often very simple and efficient; also the analysis is often clearer. However, we do not have a general mechanism for transforming protocols that are secure in the random oracle model into protocols that are secure in real life. In fact, we do not even know how to meaningfully specify the properties required from such a mechanism. Instead, it is a common practice to simply replace — often without mathematical justification — the random oracle with a ‘cryptographic hash function’ (e.g., MD5 or SHA). Consequently, the resulting protocols have no meaningful proofs of security.
We propose a research program aimed at rectifying this situation by means of identifying, and subsequently realizing, the useful properties of random oracles. As a first step, we introduce a new primitive that realizes a specific aspect of random oracles. This primitive, called oracle hashing, is a hash function that, like random oracles, ‘hides all partial information on its input’. A salient property of oracle hashing is that it is probabilistic: different applications to the same input result in different hash values. Still, we maintain the ability to verify whether a given hash value was generated from a given input. We describe constructions of oracle hashing, as well as applications where oracle hashing successfully replaces random oracles.
Chapter PDF
References
N. Alon and J. Spencer, The Probabilistic Method, Wiley, 1992.
M. Bellare, R. Canetti and H. Krawczyk, “Pseudorandom functions revisited: The cascade construction and its concrete security”, 37th FOCS, 1996.
M. Bellare, R. Canetti and H. Krawczyk, “Keying hash functions for message authentication”, CRYPTO'96, 1996.
M. Bellare, R. Guérin and P. Rogaway, “XOR MACs: New methods for message authentication using finite pseudorandom functions,” CRYPTO'95, 1995.
M. Bellare, J. Kilian and P. Rogaway, “The security of cipher block chaining.” CRYPTO'94, 1994.
M. Bellare and P. Rogaway, “Random oracles are practical: a paradigm for designing efficient protocols”, 1st ACM Conference on Computer and Communications Security, 62–73, 1993.
M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption”, EUROCRYPT '94 (LNCS 950), 92–111, 1995.
M. Bellare and P. Rogaway, “The exact security of digital signatures — How to sign with RSA and Rabin”, EUROCRYPT '96 (LNCS 1070), 1996.
M. Bellare and P. Rogaway, “Minimizing the use of random oracles in P1363 encryption schemes”, Contribution on IEEE P1364. November 10, 1996.
M. Blum, A. De Santis, S. Micali and G. Persiano, “Non-interactive zero-knowledge”, SIAM Journal on Computing, 20(6):1084–1118, December 1991.
B. den Boer and A. Bosselaers, “Collisions for the compression function of MD5”, EUROCRYPT'93, 293–304, 1994.
S. Brands, “An efficient off-line electronic cash system based on the representation problem”, CWI TR CS-R9323, 1993.
R. Canetti, “Towards realizing random oracles: Hash functions that hide all partial information”, in Theory of Cryptology Library, No. 97-07. http://theory.lcs.mit.edu/tcryptol, 1997.
J. L. Carter and M. N. Wegman, “Universal classes of hash functions”, JCSS No. 18, 143–154, 1979.
B. Chor and O. Goldreich, “Unbiased bits from sources of weak randomness and probabilistic communication complexity”, SIAM J. Comp., Vol. 17, No. 2, 230–261, 1988.
I.B. Damgård, “Collision free hash functions and public key signature schemes”, EUROCRYPT 87 (LNCS 304), pp. 203–216, 1988.
D. Dolev, C. Dwork and M. Naor, “Non-malleable cryptography”, 23rd STOC, 1991.
T. El-Gamal, “Cryptography and logarithms over finite fields”, Ph.D. Thesis, Stanford University, 1984.
P. Feldman, “A practical scheme for non-interactive verifiable secret sharing”, 28th FOCS, 427–437, 1987.
A. Fiat and A. Shamir, “How to prove yourself: Practical solutions to identification and signature problems”, CRYPTO'86 (LNCS 263), 186–194, 1986.
O. Goldreich, “Foundations of Cryptography (Fragments of a book)”, Weizmann Inst. of Science, 1995. (Available at http://theory.lcs.mit.edu/~tcryptol/)
Shafi Goldwasser and Silvio Micali, “Probabilistic encryption”, JCSS, Vol. 28, No 2, 270–299, April 1984.
O. Goldreich and L. Levin, A Hard-Core Predicate to any One-Way Function, 21st STOC, 1989, pp. 25–32.
S. Goldwasser, S. Micali and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks,” SIAM Journal of Computing, 17(2):281–308, April 1988.
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, “Handbook of applied cryptography”, CRC Press, 1997.
S. Micali, “CS proofs”, 35th FOCS, 436–453, 1994.
M. Naor and O. Reingold, “The Brain can Compute Pseudo-Random Functions, or Efficient Cryptographic Primitives Based on the Decisional Diffie-Hellman Assumption”, manuscript.
M. Naor and M. Yung, “Universal one-way hash functions and their cryptographic applications”, 21st STOC, 33–43, 1989.
M. Naor and M. Yung, “Public key cryptosystems provably secure against chosen ciphertext attacks”, 22nd STOC, 427–437, 1990.
T. P. Pedersen, “Distributed provers with applications to undeniable signatures”, EUROCRYPT'91, 1991.
D. Pointcheval and J. Stern, “Security proofs for signature schemes”, Eurocrypt '96 (LNCS 1070), pp. 387–398, 1996.
C. Rackoff and D. Simon, “Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack”, CRYPT0'91, (LNCS 576), 1991.
R. Rivest, “The MD5 message-digest algorithm,” IETF Network Working Group, RFC 1321, April 1992.
B. Schneier, “Applied cryptography”, 2nd edition, Wiley and sons, 1996.
FIPS 180, “Secure Hash Standard”, Federal Information Processing Standard (FIPS), Publication 180, National Institute of Standards and Technology, US Department of Commerce, Washington D.C., May 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Canetti, R. (1997). Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052255
Download citation
DOI: https://doi.org/10.1007/BFb0052255
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive