Cryptographic simulator

A cryptographic simulator is an algorithm in a security proof that reproduces an adversary's externally observable behavior using the interfaces and cryptographic leakage allowed by an ideal cryptographic functionality. In universal composability, substituting it for the real adversary should leave every allowed cryptographic environment unable to distinguish real and ideal executions efficiently.^[ref]

The central question is what information the simulator receives. An original elementary example uses a one-time pad. For a fixed $n$-bit message $m$, let its fresh secret key $K$ be uniform on $\{0,1{\}}^n$. Its ciphertext is $C=m\oplus K$, where $\oplus$ is bitwise exclusive or. For every $n$-bit value $c$,A simulator told only $n$ can therefore reproduce this one ciphertext's distribution by generating $n$ independent uniform bits, without knowing $m$. With $n=5$, each of the 32 possible ciphertexts has probability $1/32$ in both constructions. This is a direct distribution calculation, not a complete universal composability proof for a messaging system: other visible inputs, outputs and correlations would also need to match.

Now modify the toy system so its visible packet includes a secret input bit $b$ in the clear. Suppose the cryptographic environment selected $b$ uniformly and the ideal service reveals neither $b$ nor any correlated information before the simulator must report its guessed packet bit $g$. In the real system the environment's test $g=b$ succeeds with probability one. Any simulator whose information is independent of $b$ succeeds with probability $1/2$, even without a computation bound. The cryptographic distinguishing advantage is therefore $1/2$.

Allowing the ideal service to reveal $b$ would remove that particular simulation obstacle, but would specify a different disclosure policy. A valid simulator must use the actual permitted cryptographic leakage, rather than assume access to an honest party's private data.

More generally, reproducing a cryptographic transcript requires its correlations with the cryptographic environment's state to be correct. Sampling plausible-looking individual messages is insufficient. Efficiency also matters: an unbounded reconstruction algorithm does not supply a polynomial time simulator when the security definition requires one.