Ideally, a hash function is indistinguishable from a random function. The random oracle model, introduced in 1993 by Bellare and Rogaway [Bellare-Rogaway], gives a convenient method for analyzing the security of cryptographic algorithms that use hash functions by treating hash functions as random oracles.

A random oracle acts as follows. Anyone can give it an input, and it will produce a fixed length output. If the input has already been asked previously by someone, then the oracle outputs the same value as it did before. If the input is not one that has previously been given to the oracle, then the oracle gives a randomly chosen output. For example, it could flip $n$ fair coins and use the result to produce an $n$-bit output.

For practical reasons, a random oracle cannot be used in most cryptographic algorithms; however, assuming that a hash function behaves like a random oracle allows us to analyze the security of many cryptosystems that use hash functions.

We already made such an assumption in Section 12.1. When calculating the probability that a birthday attack finds collisions for a hash function, we assumed that the output of the hash function is randomly and uniformly distributed among all possible outcomes. If this is not the case, so the hash function has some values that tend to occur more frequently than others, then the probability of finding collisions is somewhat higher (for example, consider the extreme case of a really bad hash function that, with high probability, outputs only one value). Therefore, our estimate for the probability of collisions really only applies to an idealized setting. In practice, the use of actual hash functions probably produces very slightly more collisions.

In the following, we show how the random oracle model is used to analyze the security of a cryptosystem. Because the ciphertext is much longer than the plaintext, the system we describe is not as efficient as methods such as OAEP (see Section 9.2). However, the present system is a good illustration of the use of the random oracle model.

Let $f$ be a one-way one-to-one function that Bob knows how to invert. For example, $f(x)=x^e(\text{mod}n)$, where $(e\text{,}n)$ is Bob’s public RSA key. Let $H$ be a hash function. To encrypt a message $m$, which is assumed to have the same bitlength as the output of $H$, Alice chooses a random integer $r$ mod $n$ and lets the ciphertext be

When Bob receives $(y_1\text{,}{y}_2)$, he computes

It is easy to see that this decryption produces the original message $m$.

Let’s assume that the hash function is a random oracle. We’ll show that if Alice can succeed with significantly better than 50% probability, then she can invert $f$ with significantly better than zero probability. Therefore, if $f$ is truly a one-way function, the cryptosystem has the ciphertext indistinguishability property. To test this property, Alice and Carla play the CI Game from Section 4.5. Carla chooses two ciphertexts, $m_0$ and $m_1$, and gives them to Alice. Alice randomly chooses $b=0$ or $1$ and encrypts $m_b$, yielding the ciphertext $(y_1\text{,}{y}_2)$. She gives $(y_1\text{,}{y}_2)$ to Carla, who tries to guess whether $b=0$ or $b=1$. Suppose that

Let $L=\{r_1\text{,}{r}_2\text{,}\dots \text{,}{r}_{\ell }\}$ be the set of $y$ for which Carla can compute $f^{-1}(y)$. If $y_1\in L$, then Carla computes the value $r$ such that $f(r)=y_1$. She then asks the random oracle for the value $H(r)$, computes $y_2\oplus H(r)$, and obtains $m_b$. Therefore, when $y_1\in L$, Carla guesses correctly.

If $r\notin L\text{,}$ then Carla does not know the value of $H(r)$. Since $H$ is a random oracle, the possible values of $H(r)$ are randomly and uniformly distributed among all possible outputs, so $H(m)\oplus m_b$ is the same as encrypting $m_b$ with a one-time pad. As we saw in Section 4.4, this means that $y_2$ gives Alice no information about whether it comes from $m_1$ or from $m_2$. So if $r\notin L\text{,}$ Alice has probability $1/2$ of guessing the correct plaintext.

Therefore

It follows that $\text{Prob}(x\in L)=2ϵ$.

If we assume that it is computationally feasible for Alice to find $b$ with probability at most $ϵ$, then we conclude that it is computationally feasible for Alice to guess $r$ correctly with probability ${\displaystyle \frac{1}{2}}+ϵ$. Therefore, if the function $f$ is one-way, then the cryptosystem has the ciphertext indistinguishability property.

Note that it was important in the argument to assume that the values of $H$ are randomly and uniformly distributed. If this were not the case, so the hash function had some bias, then Alice might have some method for guessing correctly with better than 50% probability when $r\notin L\text{.}$ Therefore, the assumption that the hash function is a random oracle is important.

Of course, a good hash function is probably close to acting like a random oracle. In this case, the above argument shows that the cryptosystem with an actual hash function should be fairly resistant to Alice guessing correctly. However, it should be noted that Canetti, Goldreich, and Halevi [Canetti et al.] have constructed a cryptosystem that is secure in the random oracle model but is not secure for any concrete choice of hash function. Fortunately, this construction is not one that would be used in practice.

The above procedure of reducing the security of a system to the solvability of some fundamental problem, such as the non-invertibility of a one-way function, is common in proofs of security. For example, in Section 10.5, we reduced certain questions for the ElGamal public key cryptosystem to the solvability of Diffie-Hellman problems.

Section 12.2 shows that most hash functions do not behave as random oracles with respect to multicollisions. This indicates that some care is needed when applying the random oracle model.

The use of the random oracle model in analyzing a cryptosystem is somewhat controversial. However, many people feel that it gives some indication of the strength of the system. If a system is not secure in the random oracle model, then it surely is not safe in practice. The controversy arises when a system is proved secure in the random oracle model. What does this say about the security of actual implementations? Different cryptographers will give different answers. However, at present, there seems to be no better method of analyzing the security that works widely.