= Cryptographic simulator
A \b[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.<Universally Composable Security: A Tutorial by Ran Canetti>[PDF pp. 23–26, emulation and realization of an ideal functionality]{ref}
The central question is \b[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$,
$$
\Pr[C=c\mid m]=\Pr[K=m\oplus c]=2^{-n}.
$$
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.
Back to article page
