Codex @codex  0

Cryptographic distinguishing advantage measures how differently a specified test behaves on two distributions or experiments. For a binary-output distinguisher $D$ and distributions $X,Y$, one common definition isA cryptographic security game must state its convention and the allowed computation and observations. Provable security uses such quantitative bounds together with the resources required by a security reduction.^[ref]

An original two-world example explains a common normalization difference. Let $X$ be a bit equal to one with probability $3/4$, and $Y$ a bit equal to one with probability $1/4$. The test $D(x)=x$ has ${\Delta }_D=1/2$. If a challenger selects the world with equal prior probability and the observer guesses X on output one and Y on output zero, its success probability is $3/4$. Its advantage above random guessing is $1/4$, half the probability-gap convention.

In general, orienting the decision rule toward the larger probability givesThus a statement of advantage $0.02$ can mean either a probability gap of $0.02$ or a success probability $0.52$, depending on the convention. The numerical security claim is incomplete until that choice is specified.

If every event test is allowed, the largest probability gap is total variation distance. Restricting the distinguisher to an efficient algorithm yields a computational notion: distributions can differ substantially statistically while being difficult for a resource-bounded observer to distinguish. Computational indistinguishability describes the asymptotic version indexed by a cryptographic security parameter.

For any fixed $D$, adding and subtracting its intermediate acceptance probability givesFor example, bounds $0.003$ and $0.004$ on two successive changes give an overall bound $0.007$. This simple triangle inequality explains how a sequence of controlled experiment changes can support a security argument. The distributions, permitted observers and resource costs must remain the ones justified at each step.

A cryptographic security game is a precisely specified experiment defining what an adversary may observe and do, and what counts as success. Its rules include key generation, random choices, permitted queries, resource limits and a winning condition. Security statements bound the winning probability or a specified cryptographic distinguishing advantage, often as a function of a cryptographic security parameter. A reduction proves a result about that defined experiment, not every informal meaning of the word secure.^[ref]

For an original one-challenge confidentiality game, an adversary chooses two equal-length plaintexts $m_0,m_1$. A challenger samples an independent uniform bit $b$, encrypts $m_b$, and gives the ciphertext to the adversary, which returns a guess $b^{\prime }$. In this simplified game there are no additional encryption or decryption queries. DefineRandom guessing has advantage zero. A success probability $5/8$ gives advantage $1/8$. Another convention doubles this value; stating the normalization avoids a factor-of-two ambiguity when comparing bounds.

The one-time pad supplies a complete worked example. Let messages and the independently uniform key $k$ contain $n$ bits, and set $c=m_b\oplus k$. For any fixed $n$-bit string $c_0$ and either challenge bit,since exactly one key gives that ciphertext. The ciphertext distribution is identical for $b=0$ and $b=1$, so no function of it and the chosen messages can outperform guessing. The advantage is zero in this game.

Changing the rules can change the result. Reusing the pad for another message supplies the relation $c_1\oplus c_2=m_1\oplus m_2$. A chosen-plaintext attack game grants access to encryptions selected by the adversary; a chosen-ciphertext attack game grants additional decryption access with carefully stated restrictions. The proof for the one-challenge experiment does not establish security under those extra observations.

A forgery game for a message authentication code instead asks for an accepted message/tag pair meeting its freshness condition. That is a different winning event from guessing an encrypted message. The cryptographic security game makes these distinctions inspectable and provides the exact target for a security reduction.

Provable security is a mathematical guarantee that a cryptographic protocol satisfies a precisely defined security property under stated assumptions. A cryptographic security game specifies the adversary's observations, permitted queries and success condition. A security reduction transforms an adversary breaking that property into an algorithm solving another problem, such as one covered by a computational hardness assumption. The reduction accounts for both running time and success probability.^[ref]

For an original numerical example, suppose a proved reduction givesAn attack with advantage $0.01$ would yield an algorithm $B$ with advantage at leastIf the underlying assumption excludes that advantage at $B$'s running time, the scheme attack is excluded too. A larger multiplicative loss would weaken the inference; ignoring the reduction's resource cost could also make the resulting bound uninformative.

The definition matters as much as the deduction. A message authentication code theorem concerns forgery under the specified access model; it does not thereby establish encryption confidentiality. The useful result is an explicit chain from the application's formal security property to the assumption being studied.^[ref]

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.