 Graph-isomorphism proof protocol

The 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 $\varphi :G_0\to G_1$.^[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 {\varphi }^{-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 $\varphi$ 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 areEach 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.^[ref]