Provable Security 05: Reductions and Game Hopping
Provable security notes / V
Reductions and game hopping
A reduction is an algorithm that runs the adversary while embedding a hard challenge and keeping the simulation believable.
Most provable-security arguments are not one jump from attack to assumption. They are a sequence of games. Each game changes one aspect of the experiment, and every change is justified by an assumption, an exact equality, or a bad-event bound.
Hybrid inequality
For games \(G_0,\ldots,G_t\),
\[\left|\Pr[G_0=1]-\Pr[G_t=1]\right| \le \sum_{i=0}^{t-1}\left|\Pr[G_i=1]-\Pr[G_{i+1}=1]\right|.\]The proof must explain every summand.
PRF replacement
In a nonce encryption proof, Game 0 uses \(F_K(N)\). Game 1 uses a random function \(\mathcal R(N)\). If the adversary distinguishes these games, construct a PRF distinguisher that uses its own oracle to answer encryption queries. The reduction does not need to know whether its oracle is real or random; the adversary’s behavior tells it.
Bad events
A bad event isolates the condition under which two games may diverge. The games are identical until that event occurs.
If the event is a collision among \(q\) random \(n\)-bit values, then
\[\Pr[\mathsf{bad}]\le {q\choose 2}2^{-n}.\]The proof does not pretend the event is impossible. It pays for it explicitly.
Oracle simulation
The reduction must answer the adversary’s queries with the right distribution. This is the hard part in CCA and signature proofs.
| Oracle | Simulation difficulty |
|---|---|
| Encryption | Often easy in public-key settings because \(pk\) is public. |
| Decryption | Hard when the reduction does not know the secret key. |
| Signing | Hard when the final forgery must reveal the embedded challenge. |
| Random oracle | Flexible, because answers can be lazily sampled and sometimes programmed. |
| Decapsulation | Hard because malformed ciphertext behavior must match the real algorithm. |
A proof that says only “use the adversary to break the assumption” has skipped the simulation problem.
Tightness
A reduction is tight if the adversary’s advantage transfers to the assumption with little loss. A loose reduction may lose factors such as \(q_H\), \(q_S\), number of users, or number of sessions.
Guessing loss
If a signature proof must guess which of \(q_H\) hash queries becomes the forgery target, the bound may contain
\[\operatorname{Adv}^{\mathsf{forge}}(A) \le q_H\operatorname{Adv}^{\mathsf{dl}}(B)+\varepsilon.\]At \(q_H=2^{32}\), this consumes 32 bits of concrete margin. The theorem can be correct and still demand larger parameters.