Provable security notes / VI

Random oracles and programmability

The random oracle model gives the reduction a public random function it can answer consistently and sometimes program.

A random oracle is an ideal public function

\[H:\{0,1\}^*\to R.\]

The proof implements it by lazy sampling. Maintain a table. If an input was queried before, return the stored value. If not, sample a fresh output and store it.

Why it helps

Random oracles are useful because they let reductions control the hash interface. The adversary sees a consistent random function. The reduction may use the oracle table to embed a challenge, detect when the adversary has queried an important value, or make a simulated ciphertext or signature distribution consistent.

Programmability

Programming means choosing the oracle value at a particular input instead of sampling it uniformly at the moment the input first appears. This is valid only if the adversary has not already received a different value for the same input.

Programming is the reason many random-oracle proofs track hash-query lists explicitly.

Fiat-Shamir example

In a Schnorr identification protocol, the prover sends \(R=g^r\), receives challenge \(c\), and answers

\[s=r+cx\bmod q.\]

Verification checks

\[g^s=RY^c.\]

Fiat-Shamir replaces \(c\) by \(H(R,m)\) to produce a signature. A forking proof rewinds the adversary and answers the same query with a different challenge. Two valid responses for the same commitment give

\[x=(s-s')(c-c')^{-1}\bmod q.\]

The extraction depends on the ability to control the challenge in the proof.

Random oracle is not a hash theorem

A random-oracle proof does not prove the same statement for every concrete hash function. It proves security in a model where the hash behaves as an ideal random function and the adversary interacts with it only through oracle queries.

Where model gaps appear

A concrete implementation can fail through ambiguous encodings, missing domain separation, length-extension behavior, cross-protocol hash reuse, or side channels around hash inputs. Those are not modeled by a plain random oracle.

When to accept the model

The random oracle model is often a pragmatic proof tool. It is especially common in OAEP, Fujisaki-Okamoto transforms, and Fiat-Shamir signatures. The right reading is neither blind trust nor automatic rejection. Record exactly where programmability is used; those are the steps that would require different structure in a standard-model proof.