 Honest-verifier zero knowledge

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.^[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.^[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, soThe elementary honest-verifier simulator chooses a uniform bit and instead gives $\mathrm{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.