Cryptographic security game

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.

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.