= Honest-verifier zero knowledge
\b[Honest-verifier zero knowledge] is the <zero-knowledge proof> simulation requirement restricted to a verifier that follows its prescribed algorithm. The <zero-knowledge simulator> reproduces that verifier's view without the prover's secret <cryptographic witness>. General zero knowledge must account for permitted deviations by the verifier as well.<Zero-Knowledge: a tutorial by Oded Goldreich>[The Basics, restriction to honest verifiers and simulation variants]{ref}
In the <graph-isomorphism proof protocol>, the honest verifier chooses an independent uniform challenge bit. A simulator can first choose $b$, sample a uniform <permutation> $\rho$, set $H=\rho(G_b)$ and output $(H,b,\rho)$. For isomorphic public graphs, this has the same distribution as the honest conversation.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Construction2.3, honest-verifier simulation on printedp.27]{ref}
An original small example shows what changes if the verifier deviates. Suppose $H$ is a uniform relabeling of a three-vertex path. There are three labeled paths; two contain the edge $\{1,2\}$. A different verifier could choose $b=1$ exactly when that edge is present, so
$$
\Pr(b=1)=\frac23.
$$
The elementary honest-verifier simulator chooses a uniform bit and instead gives $\Pr(b=1)=1/2$. It therefore fails to reproduce this changed verifier's view.
This comparison does not show that the standard graph protocol lacks general zero knowledge. It shows that a simulator for the honest verifier does not automatically prove the stronger property. The general analysis may use <rewinding in cryptographic proofs> to simulate challenges that depend on the first message. The stated adversary model is part of the theorem.
Back to article page
