Graph Isomorphism Protocol

A Cut-and-Choose protocol for proving that two graphs are isomorphic. $\mathcal{R}=\{((G_0,G_1),\sigma )\mid \sigma \text{ is an isomorphism and }\sigma (G_0)=G_1\}$

This protocol is very similar to Quadratic Residue Protocol.

The main idea

Following the Cut-and-Choose paradigm, the protocol splits $x=(G_1,G_2)$ and homomorphism $w=\sigma$ into

• $x_0=(G_0,\gamma (G_0)),w_0=\gamma$
• $x_1=(G_1,\gamma (G_0)),w_1=\gamma \circ {\sigma }^{-1}$ for a random permutation $\gamma$.

Intuition

For $H=\gamma (G_0)$, the two parts read as

• $G_0$ is isomorphic to $H$ (with random isomorphism $\gamma$)
• $G_1$ is isomorphic to $H$ (with random isomorphism $\gamma \circ {\sigma }^{-1}$)

Then we get the two required properties (see Splitting the statement into parts):

• Neither $w_0=\gamma$ nor $w_1=\gamma \circ {\sigma }^{-1}$ on their own reveal anything about $\sigma$ (given that $\gamma$ is a random isomorphism)
• Together, $w_0=\gamma$ and $w_1=\gamma \circ {\sigma }^{-1}$ reveal $\sigma$.

The protocol

Following the The protocol template:

Protocol between $P(G_0,G_1,\omega )$ and $V(G_0,G_1)$

• Announcement: Prover chooses a random graph isomorphism $\gamma$ and sends $H=\gamma (G_0)$.
• Challenge: The verifier chooses a random challenge $c\leftarrow \{0,1\}$ (challenging the prover to reveal an isomorphism between $G_c$ and $H$).
• Response: The prover reveals $\omega =\{\begin{array}{ll}\gamma & c=0\\ \gamma \circ {\sigma }^{-1}& c=1\end{array}$
• The verifier checks that $\omega$ is an isomorphism and $\omega (G_c)=H$.

Optimization of the Cut-and-Choose template

Instead of sending both “split” instances $x_0=(G_0,H)$ and $x_1=(G_1,H)$, we simply send $H$, given that the verifier already knows $G_0,G_1$.

The ZK property

This follows Typical simulator outline.

The Zero Knowledge (Classical) simulator $S(x)$ for (malicious) verifier $V^{\ast }$ works as follows:

Simulator $S(G_1,G_2)$

1. $S$ computes a random transcript of the protocol:

• $S$ chooses a random challenge $c\leftarrow \{0,1\}$
• $S$ chooses a random response $\omega \leftarrow \mathsf{Perm}$
• $S$ computes the unique fitting announcement $H=\omega (G_c)$

2. $S$ rejects challenges $c$ not consistent with what $V^{\ast }$ would output:

• $S$ chooses randomness $r$ and computes $c^{\prime }=V^{\ast }(G_1,G_2;r;H)$
• If $c^{\prime }=c$, then output the view $(x,r,H,\omega )$ Otherwise, start from the beginning and try again.

The PoK property

For simplicity, we assume that the prover has probability 1 to convince an honest verifier, which puts us into the A simplified toy definition scenario. The extractor for prover $P^{\ast }$ works as follows:

Extractor $E^{P^{\ast }}(G_0,G_1)$

• $E$ retrieves the prover’s announcement $H=P^{\ast }(G_0,G_1;r)$ (for some random $r$)
• $E$ retrieves the prover’s response for both challenges $c\in \{0,1\}$ as ${\omega }_c=P^{\ast }(G_0,G_1;r;c)$
  • From the verification equation, we get ${\omega }_c(G_c)=H$
• $E$ outputs the witness $\sigma ={\omega }_1^{-1}\circ {\omega }_0$

Intuitively, the two verification equations give us maps $G_0\stackrel{{\omega }_0}{\to }H\stackrel{{\omega }_1}{\leftarrow }{G}_1$, which we just plug together to get from $G_0$ to $G_1$ (via $H$). Formally, the witness is correct because $\sigma (G_0)={\omega }_1^{-1}({\omega }_0(G_0))={\omega }_1^{-1}(H)=G_1$.

Non-simplified scenario

Theorem: the Graph Isomorphism protocol is a Proof of Knowledge (Classical) with knowledge error $\kappa =1/2$.

For a prover that may not answer all challenges correctly always (but convinces the verifier with probability $>1/2$), it may happen that when $E$ gets the two responses in the second step, one or more of them is actually invalid, i.e. fails the verification equation. In that case, the response is useless for the extractor. In that scenario, $E$ will have to restart and try different prover randomness $r$. Using a counting argument, one can show that for some $r$, the prover has to be able to answer both challenges (otherwise it cannot be convincing with probability larger than $1/2$). The extractor then tries different $r$ until it finds one for which both challenges can be answered.

Notes

• Graph Isomorphism is not known to be $\mathbf{NP}$-complete, so the language is not of much importance. However, its complement (“prove two graphs are not isomorphic”) is not known to be in $\mathbf{NP}$, so Graph Isomorphism and its complement often come up in educational contexts as good examples for the power of the class IP.