= Security reduction
A \b[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.<Practice-Oriented Provable-Security by Mihir Bellare>[§2.2, reductions; §3.2, concrete security]{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$. Therefore
$$
\left|\Pr[D(G(s))=1]-\Pr[D(U_n)=1]\right|
=\left|\Pr[A\text{ wins}]-\frac12\right|.
$$
Any 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,
$$
\operatorname{Adv}_{\rm scheme}(A)\leq q\operatorname{Adv}_{\rm primitive}(D)+\delta,
$$
an adversary with advantage $10^{-3}$, $q=100$ and $\delta=10^{-5}$ implies primitive advantage at least $9.9\times10^{-6}$. Conversely, a primitive bound $10^{-8}$ at the reduction's actual running time gives only the scheme bound $1.1\times10^{-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.
Back to article page
