= Zero-knowledge simulator
{title2=$S$}
A \b[zero-knowledge simulator] is an efficient <randomized algorithm> that reproduces the relevant verifier-view distribution of a <zero-knowledge proof> without receiving the prover's secret <cryptographic witness>. Depending on the definition, the real and simulated views must be identical, statistically close or satisfy <computational indistinguishability>.<Zero-Knowledge: a tutorial by Oded Goldreich>[The Basics, simulator and level of distribution similarity]{ref}
The <graph-isomorphism proof protocol> provides an illuminating example for <honest-verifier zero knowledge>. On a fixed public isomorphic pair $G_0,G_1$, a real prover sends a random relabeling $H$, receives a uniform challenge bit $b$, and supplies a <graph isomorphism> from $G_b$ to $H$.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Construction2.3 and the honest-verifier simulation immediately following it, printedpp.26–27]{ref}
An explicit simulation reverses that construction. First choose a uniform bit $b$ and a uniform vertex <permutation> $\rho$. Set
$$
H=\rho(G_b)
$$
and output the transcript $(H,b,\rho)$. The simulator never needs a mapping between $G_0$ and $G_1$. For an isomorphic public pair, random relabelings of either graph have the same <probability distribution>; conditional on $b$, the response mapping is uniform in both constructions. Thus the honest verifier's transcript distribution is reproduced exactly.
This does not give a live cheating prover control of the verifier's future challenge. The simulator chooses a complete transcript in a different order from the real exchange. Nor does this simple sampler establish security against an arbitrary malicious verifier, whose challenge could depend on $H$.
The example exposes the central requirement: producing one plausible accepting transcript is insufficient. The simulator must reproduce the specified distribution within the required efficiency bound and adversary model.
Back to article page
