= Graph-isomorphism proof protocol
The \b[graph-isomorphism proof protocol] is a three-message <interactive proof system> for the claim that public <graphs> $G_0,G_1$ are isomorphic. An honest <prover in an interactive proof> knows a <cryptographic witness> $\phi:G_0\to G_1$.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Construction2.3, printedpp.26–27]{ref}
The prover samples a uniform vertex <permutation> $\pi$ and sends $H=\pi(G_0)$. The <verifier in an interactive proof> replies with a uniform bit $b$. The prover then sends an isomorphism $\rho_b:G_b\to H$: use $\rho_0=\pi$ or $\rho_1=\pi\circ\phi^{-1}$. The verifier checks the mapping and its effect on all edges.
For an original three-vertex example, let $G_0$ have edges $\{1,2\},\{2,3\}$, and let $\phi$ map $(1,2,3)$ to $(2,3,1)$. Then $G_1$ has edges $\{2,3\},\{1,3\}$. Choose $\pi$ mapping $(1,2,3)$ to $(2,1,3)$; the sent graph $H$ has edges $\{1,2\},\{1,3\}$. The two responses are
$$
\rho_0:(1,2,3)\mapsto(2,1,3),\qquad
\rho_1:(1,2,3)\mapsto(3,2,1).
$$
Each maps the corresponding input graph's edges to those of $H$. These tiny graphs illustrate the checks, not a difficult cryptographic instance.
An honest prover always passes. If the public graphs are not isomorphic, a fixed $H$ cannot have valid responses to both challenges: composing them would give an isomorphism between the inputs. Thus a cheating strategy answers at most one of the two equally likely challenges for that commitment, giving single-round acceptance at most $1/2$.
The standard protocol also admits <zero-knowledge simulator> constructions. An elementary sampler proves <honest-verifier zero knowledge>; treating arbitrary verifier strategies requires an additional simulation argument.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Construction2.3 and subsequent honest/general-verifier simulations, printedpp.27–28]{ref}
Back to article page
