Random oracle model proofs and programmability

Question

1. Proving the security of a scheme with the random oracle model (ROM) involves two steps: first you prove that the scheme is secure in an idealized world where a random oracle exists, and then you implement this scheme in the real world by replacing the random oracle with a hash function. Why wouldn't you prove the security of the scheme with the hash function that you end up implementing the world with? Is it because no proof has been found or are there any other reasons? Could you give me some examples?

2. Could you explain to me the "programmability" feature of the random oracle model? In my book (Katz-Lindell) it says: The reduction may choose values for the output of H as it likes (as long as these values are correctly distributed, i.e. uniformly random).

3. If I understand correctly, the function $H$ that will act as a random oracle can be fixed beforehand or it can be generated "on the fly", by generating a table of inputs and outputs and when there is a new input the function generates a new output and enters it into the table. What is the theoretical difference between the two?

Answer 1

Your second question was about programmability. This hasn't been directly addressed yet by Thomas' answer or the comments, so I'll focus on that question only. Unfortunately I don't know of a simple primitive that is secure in the random oracle model that requires programmability, but I'll use one that is hopefully clear once I explain the background. It's called the Fiat-Shamir heuristic; it's a nice trick to make non-interactive zero knowledge proofs.

Before getting to Fiat-Shamir, consider how your favorite basic zero-knowledge proof works. Since this is Crypto SE, not CSTheory SE, hopefully you are thinking about proving knowledge of discrete logarithms and quadratic residues, not graph isomorphisms or 3-coloring graphs. ;)

[Aside: technically these are not true zero-knowledge proofs, they are honest-verifier zero-knowledge proofs (sometimes called $\Sigma$-protocols) but we don't care about that distinction here]

Schnorr's proof of knowledge of a discrete logarithm

$P$ (for prover) comes along with two values $g$ and $y$ in some group $\mathbb{G}_q$ where the discrete logarithm is hard. She claims: I know the value $x$ such that $y=g^x$. As $x$ is the discrete logarithm of $y$ base $g$, computing $x$ directly is infeasible so $V$ (verifier) cannot initially be sure if she really knows $x$ or not.

The Schnorr protocol lets $P$ prove knowledge of $x$ to $V$ in a way that does not disclose anything about $x$. It goes as follows:

1. $P$ generates a random value $a$, computes $b=g^a$, and sends $b$ to $V$
2. $V$ generates a random value $c$ and sends $c$ back to $P$
3. $P$ computes $d=a+cx$ and sends $d$ to $V$
4. $V$ accepts $\langle b,c,d\rangle$ as proof for $\langle g,y \rangle$ iff $g^d=by^c$

Security Analysis

We can ask ourselves, what do you we want in terms of security from such a protocol? $V$ is concerned that sending a bunch of numbers back and forth might not actually constitue a proof that $P$ knows such an $x$. If he can actually conclude that $P$ must know $x$ if $P$ can produce many accepting $\langle b,c,d\rangle$ transcripts, the proof is said to be sound.

$P$ may be concerned that $V$ might learn some information about $x$ from seeing one or more accepting transcripts. This is supposed to be a proof that leaks zero information about $x$ (glossing over the honest verifier technicality). If it leaks zero information, it is said to be zero-knowledge.

Soundness (via Extraction)

To show the Schnorr protocol is sound, we are actually going to do it indirectly. We are first going to show it is something called "extractable" and then show that extractability implies soundness. I'm not going to give actual definitions or proofs, just a sketch of what is going on.

Schnorr protocols have a special soundness property (called, you guessed it, special soundness): if there are two accepting transcripts $t_1=\langle b,c,d \rangle$ and $t_2=\langle b,c',d' \rangle$ where $t_1$ shares the same value of $b$ with $t_2$ but $c$ (and thus $d$) are different, then it is possible to calculate the value of $x$: $x=(d-d')/(c-c')$. If $P$ can reliably generate accepting transcripts, then there is no reason to suppose she couldn't generate $t_1$. Likewise $t_2$. And if she can produce both, then she "knows" $x$ in the sense that the knowledge required to produce $t_1$ and $t_2$ is sufficient to produce $x$ itself.

When we eventually get to Fiat-Shamir, it will be important to have formalized this notion of "extractability" a little bit. Consider the situation where $P$ is a compiled binary program instead of a person. You can run $P$ which will perform the protocol and you can rewind $P$ to a previous internal state, but you can't decompile it or look at the internal state (this is called rewindable blackbox access; why these special powers are allowed in proving extractability is a topic for another time).

We say that a protocol is extractable if you can get $x$ from interacting with such a black box. And we say a protocol is sound if it is extractable in this way (a blackbox that you can rewind). Both of these propositions have proofs in the literature with lots of fine-print I am omitting. Note that you can prove soundness in other ways than extractability or other flavours than blackbox-rewindable extractability (extractability is sufficient but not necessary).

For Schnorr, it should be obvious how, but you do the following:

1. Let $P$ output $b$
2. Give $P$ a random $c$ as input
3. Let $P$ output $d$
4. Rewind $P$ to after step 1 and before step 2
5. Give $P$ a different random $c'$ as input
6. Let $P$ output $d'$
7. Compute $x$ from $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$

Zero-knowledge (via Simulation)

Similarly, we can indirectly prove the protocol is zero-knowledge by showing it has a different property: simulatability. In this case, we get a compiled binary of $V$ and have to reliably supply it with acceptable $b$ and $d$ values for the $c$'s it gives us. However the protocol is for knowledge of an $x$ we do not actually know! If we can simulate acceptable protocol runs without knowing $x$, then the values in the protocol must not really be leaking any information about $x$. So if the protocol is simulatable in this regard, then it is zero-knowledge.

I mentioned before that Schnorr is not actually a zero-knowledge protocol. This creates some problems with simulating Schnorr transcripts that will get resolved when we use a random oracle with Fiat-Shamir. To simulate Schnorr protocols, we do the following:

1. Generate random value $d$
2. Guess the value of $c$
3. Supply $b=g^dy^{-c }$ as input to $V$
4. Let $V$ output $c'$
5. If $c'\neq c$ (you guessed wrong), rewind to step 2. Else continue
6. Supply $d$ to $V$ which will accept

If the values of $c$ are really short (say a bit), then the simulator is efficient. For longer values, you can't prove the zero-knowledgeness of Schnorr with this method. There are a handful of tricks to convert Schnorr into something that is true zero-knowledge.

Fiat-Shamir Heuristic

Reading the above, you might do a double-take: on one hand, you can show that $x$ must be known if transcripts accept and on the other, you can generate transcripts that accept without $x$: what gives? If you look closely, you'll see that the simulated transcripts are generated out of order while the extractable ones are generated in order. In fact, by generating out of order, we cannot produce $\langle b,c,d \rangle$ and $\langle b,c',d'\rangle$ transcripts since the value of $b$ is no longer being chosen: it is determined by $d$ and $c$.

The idea of Fiat-Shamir is to make Schnorr (and related) protocols non-interactive. This means $P$ can produce all three values $\langle b,c,d \rangle$ instead of relying on $V$ to provide $c$. Furthermore, since we know transcripts are simulatable, $P$ can produce a value of $c$ that has to have been generated after the value $b$ thus ruling out any simulation. How? It is really easy actually: set $c=\mathcal{H}(b)$. The verifier additionally checks that $c=\mathcal{H}(b)$. [Aside: there is actually a neat optimization here where you don't have to send the value $b$ at all but leave that aside].

Finally we can introduce random oracles. It turns out that if you use regular hash functions, you can't wrestle extractability or simulation out of the protocol. We'll try but ultimately we will require a random oracle that can be programmed.

Extraction with Fiat-Shamir heuristic

Recall that extraction relies on pairs of transcripts like $\langle b,c,d \rangle$ and $\langle b,c',d' \rangle$. With Fiat-Shamir, $c=\mathcal{H}(b)$ so if the values of $b$ between two transcripts are identical, then $c$ and thus $d$ will be as well. Therefore, we cannot get two such transcripts with a regular deterministic hash function. But if $\mathcal{H}$ is a programmable random oracle, we can get it to produce different values for the same input. Once again, we play the game of having rewindable blackbox access to $P$ but this time we also get the random oracle:

1. Let $P$ generate $b$
2. See $P$ query $O$ with $b$ for $\mathcal{H}(b)$
3. Generate random $c$ and program $c=\mathcal{H}(b)$ in $O$
4. Let $O$ answer query
5. Let $P$ compute $d$
6. Let $P$ output $\langle b,c,d \rangle$
7. Rewind to end of step 2
8. Generate random $c'$ and program $c'=\mathcal{H}(b)$ in $O$
9. Proceed as before and eventually let $P$ output $\langle b,c',d' \rangle$

A few notes: (1) because this is non-interactive, $P$ does not output $b$ after step 1, so we rely on the ability to see queries to the random oracle; (2) if the oracle generates answers "on the fly" (instead of entering the protocol with a codebook of all queries/responses), we don't actually have to program it with different values of $c$. We just rewind to before the point it is about to generate a response and let it generate a random value (which will overwhelmingly be different than in the first execution). This sheds some light on the original poster's third question.

Simulation with Fiat-Shamir

Similarly to extraction, the use of a random oracle makes simulation a breeze. Assuming you've read this far, you can probably see how so I will just say it in a sentence: Set a random value for $c$, compute $\langle b,c,d \rangle$ by choosing $d$ first, and when the verifier checks with the oracle that $c=\mathcal{H}(b)$, program $c$ as the response.

Answer 2

A random oracle is an ideal object; see this previous question for some details. What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme:

• $H$ is a random oracle which outputs $n$-bit values.
• The key is a $K$, a string of $k$ bits.
• A single message $m$ is encrypted by computing $c = m \oplus H(K || 1) || H(K || 2) || ...$ (you repeatedly "hash" with the random oracle the successive strings obtained by concatenating $K$ with a counter, and you concatenate the oracle outputs into a big stream which is XORed with the message to encrypt).

If $H$ is a random oracle, then it is reasonably easy to prove that the encryption is secure up to a work factor of $2^{k-1}$ invocations of $H$: for any index $i$, you can learn nothing on the bit $i$ of the generated stream ("nothing" as in "not even the slightest statistical bias") unless you do invoke $H$ on the exact input which yielded it; since there are $2^k$ possible values for $K$, the best possible attack is just trying them out (in any order), which, on average, will hit the right key after $2^{k-1}$ guesses. Each guess involve invoking $H$.

Now, with a cryptographic hash function, things are not that easy. A cryptographic hash function is defined as being resistant to preimages, second preimages, and collisions. These are much weaker properties. A function could be a good hash function and still fail to be a random oracle. This is especially true with the commonly used Merkle-Damgård function such as SHA-256 and SHA-512: these functions suffer from the so-called "length extension attack". Given $H(x)$, it is possible, under certain conditions but without knowing $x$, to compute $H(x||x')$ for some values of $x'$. A random oracle would not allow that. And this specific property totally destroys our attempts at proving the security of the encryption scheme described above. Nevertheless, the "length extension" does not seem to help in any way when you try to compute preimages or collisions. Indeed, no efficient preimage or collision attack is currently known on SHA-256 or SHA-512.

To sum up, a random oracle is an ideal object which allows for easy proofs of constructions in which they are used, proofs which rely on properties that actual hash functions do not necessarily exhibit (even if they are "secure" hash functions).

---

When we "implement" a random oracle, we use hash functions and other primitives in such a way to mimic the ideal properties of a random oracle. Existing hash functions are not good enough for that by themselves, as seen above. A common tool is HMAC, which uses a key and is built over an existing hash function, but invokes it twice in a specific way so as to avoid known shortcomings of concrete functions such as SHA-256. This is why, for instance, when building a cryptographically secure pseudorandom number generator as described by NIST, you may prefer the "HMAC_DRBG" construction over the faster, but "less proven" Hash_DRBG.

There is still a bit of technicality, intuition, and downright faith, in using a given construction with hash function in a protocol where a random oracle should be used. But we have nothing better: we do not know if random oracles really exist (or even secure hash functions, for that matter).

---

Whether a given implementation uses tables to store precomputed results has no influence whatsoever on theoretical security: a proof in the random oracle model relies on the number of times the oracle must have been invoked (on distinct inputs), but not on when the invocations took place. You can use internal tables as you wish.

There is a subtlety on the birth date of the function: if the oracle is HMAC with a key, then the oracle "exists" since the key was generated, and all oracle invocations must have used that key; on the other hand, a key-less hash function such as SHA-256 can be thought of as a kind-of random oracle which has existed since SHA-256 was first defined, more than ten years ago, and the whole World may have been busy invoking it during the last decade. So using raw SHA-256 as a random oracle (if we ignore the bit about length extensions) is equivalent to considering that the attacker could be as powerful as the whole World with a ten-years computational head start. To avoid that, it is commonplace to define protocols which use a keyed function as random oracle.

Answer 3

The question of programmability of ROM, and why it's a feature which leads to "errors" when applying ROM-proved constructions with real hash-functions, is considered in details in https://link.springer.com/chapter/10.1007/3-540-45708-9_8

Answers to your questions:

1. Yes, it's often impossible to find a proof based on properties of the hash-functions, like collision-resistance preimage-resistance. Example is a proof for Schnorr signature.

2. Programmability of random oracle is often an essential property for constructing of proofs. It means, that responses of the oracle are not fixed beforehand (as it is for a real hash-function, where all hash-values are fixed), but we can choose them adaptively during an experiment considered in the proof. E.g., a proof for Schnorr signature shows that if there's an attacker A for Schnorr signature, then we can create attacker B which will use A as a black-box subroutine and will be able to break discrete logarithm problem. To run A, B should emulate its environment: respond to random oracle queries, respond to signing oracle queries. But B don't know secret key (which is a discrete log and B actually wants to find it!), so how it could respond to A on signing oracle requests? This is where random oracle programmability comes to the scene. B will assign a specific value as a random oracle response to specific request, so that B will able to create a signature (from some point of view, "forge" a signature by manipulating random oracle responses). But in a way that A can't recognize this hacking of B (can't distinguish that value from random one).

3. In reality, hash function values are known beforehand (once hash function is declared/chosen). Random oracle values are allowed to be chosen on the fly, which essentially helps in constructing of proofs.