 Security reduction

A security reduction turns an adversary breaking one stated cryptographic property into an algorithm breaking another property or solving an assumed-hard problem. It specifies the simulation given to the adversary, the relation between success probabilities and the additional computation required. A primitive's hardness assumption can then imply a bound for the constructed scheme.^[ref]

An original reduction illustrates this without a numerical loss. Let a pseudorandom generator expand a uniformly sampled $\lambda$-bit seed $s$ into an $n$-bit string $G(s)$. Consider one-use encryption $c=m\oplus G(s)$ for $n$-bit messages. Suppose adversary $A$ distinguishes which of $m_0,m_1$ was encrypted in the one-challenge cryptographic security game.

Construct a distinguisher $D$ given a string $w$ that is either a generator output or uniformly random. Run $A$ to obtain its message pair, select an independent uniform bit $b$, and give it $c=m_b\oplus w$. Output one exactly when $A$ guesses $b$ correctly. If $w=G(s)$, this is the real encryption experiment. If $w$ is uniform, it is a one-time pad, and the success probability is $1/2$. ThereforeAny nonzero advantage for that encryption game gives the same distinguishing advantage against the generator. The reduction adds the challenge-bit choice, an exclusive or and bookkeeping to the cost of running $A$. It establishes this one-use confidentiality result, without claiming authenticity or safe pad reuse.

Other reductions lose probability or require more computation. For a separate stipulated bound,an adversary with advantage $10^{-3}$, $q=100$ and $\delta =10^{-5}$ implies primitive advantage at least $9.9\times 10^{-6}$. Conversely, a primitive bound $10^{-8}$ at the reduction's actual running time gives only the scheme bound $1.1\times 10^{-5}$. The coefficient and additive term are original illustrative values, not a published bound for a named cipher.

The cryptographic security game and resource accounting remain part of the theorem. A proof cannot transfer a primitive bound stated for a small computation budget to a reduction that exceeds it, or replace the exact scheme's assumptions by a different informal hardness claim.