# State of the art for Graph Isomorphism

I want to know the state of the art result for proving knowledge of graph isomorphism. As described here, the classical Goldreich-Micali-Wigderson (GMW) protocol is a $$\Sigma$$-protocol with soundness error $$\frac{1}{2}$$, so it requires repetition. They then showed a $$5$$-round protocol for GI, essentially forcing the verifier to commit to their challenges to allow for knowledge extraction (please correct me if my understanding is wrong).

Question: Is there a $$\Sigma$$-protocol with negligible soundness?

The G&K impossibility you mention in your answer only concerns black-box simulation ZK. For weaker flavors of zero-knowledge, it can be circumvented. For example, it is well known that HVZK $$\Sigma$$-protocols compose in parallel, so you have negligible soundness and HVZK with 3 messages. It is also possible for notions of ZK that are weaker than black-box ZK, but still stronger than HVZK. To the best of my knowledge, the interactive proof which has the fewer rounds and still satisfies the stronger notion of black-box simulation is the protocol of Feige and Shamir which has 4 messages (2 rounds).

• I have accepted your answer since it's more helpful than mine :D However, I still have a question. Can you explain the proof of that HVZK $\Sigma$-protocol retains HVZK under parallel repetition? It seems the answer lies in Theorem 1 of Damgard that you linked, but it's four pages long and I don't understand much of it. Specifically I don't understand the rewinding part, and he uses this matrix thing which is confusing :( (Or point me to some easier resources?) Sep 14, 2023 at 1:37
• Theorem 1 in Damgard's notes is to prove that $\Sigma$-protocols are proofs of knowledge. It's Lemma 1 that states parallel repetition, but it is not proven in the document. The idea is that parallel repetitions are of the form $(a_{1\dots k},e_{1\dots k},z_{1\dots k})$ where $(a_i,e_i,z_i)$ is the transcript of the $i$th repetition. Then you can just call the HVZK simulator $k$ times to get $k$ transcripts. Sep 14, 2023 at 13:17

Goldreich and Krawczyk proved the following theorem:

Theorem 6.2: A language L has a three-round interactive proof which is black-box simulation zero-knowledge if and only if L ∈ BPP

So unless GI is BPP (which is unlikely), it is impossible.

Is there a ΣΣ-protocol with negligible soundness?

An interactive proof (protocol) for directed graph isomorphism was constructed by extending Schnorr protocol, and from polynomial graph representation.

Prover picks distinct finite field elements for each vertex of both graphs, like $$\{1, 2, \dots k\}$$, such that corresponding vertices share the same finite-field-label $$w$$. Polynomial graph representation is introduced: a product over all edges, a bivariate polynomial linear in both labels of the connected vertices: $$$$f(x, y | \Gamma) = \prod_{ \forall (e = \vec{H T}) \in Edges(\Gamma)} (1 + x w_H + y w_T)$$$$ The decision goes from, for any pair of isomorphic graphs as assignment exists resulting in the same "characteristic function" representing both graphs, and no such assignment for non-isomorphism case.

Now the label permutation is the witness, a set of secrets to commit to and run the well-known Schnorr protocol. We focus on Schnorr responses, treating them as linear univariate polynomials before the variable is chosen at random as a Schnorr challenge (indexed by vertices): $$$$W_v(z) = z w_v + \alpha_v$$$$ Informally, we replace secrets with responses. That is, consider a function composition: $$$$F(x, y, z | \Gamma) = \prod_{ \forall (e = \vec{H T}) \in Edges(\Gamma)} (z + x W_H(z) + y W_T(z))$$$$ Observe the top-degree coefficient of $$F(z,..)$$ is the graph characteristic polynomial $$f()$$. That is, it does not depend on random coins $$\alpha$$ from the first step of Schnorr.

It follows, Verifier can test graph characteristic polynomial equality at a random point $$(x,y)$$ chosen as the first challenge, only having Schnorr responses calculated at some random $$z$$ (the regular Schnorr challenge) and homomorphic commitments (Pedersen) to all the lower-degree coefficients of $$F(z,)$$ sent by the Prover.

Soundness follow from Schwartz-Zippel lemma. Negligible soundness in a single round, as requested. In modern parlance, this might be called a polynomial interactive oracle proof.

Presented at ISCOPT 2007 and Central European Conference on Cryptography 2009, accessible through WebArchive/Wayback.

IACR preprint 2008/363 for graph hamiltonicity using this technique. Graph coloring in MFCS (EATCS) 2012.