In question (1.b) in Homework 10 for Brown University's Cryptography course, they present the problem of providing a zero-knowledge proof for $L = \{ ((G_0, G_1), (G'_0, G'_1)) \mid G_0 \cong G_1 \vee G'_0 \cong G'_1 \}$

It’s trivial to show that since it is an NP language then there is a zero-knowledge proof, but I think there should be a direct proof solution.

My idea is for Alice to compute a random permutation of all graphs and send to Bob (while keeping them in the original pairs, only shuffling their order), then let Bob either ask Alice to reveal the permutations and verify they are correct or show that one of the pairs is isomorphic. The problem is I'm not sure it can be simulated without knowing the original isomorphic pair.

Note: this course already ended and I'm not a student there so it's not my homework.


1 Answer 1


This is known as an OR-proof: given $x_0$ and $x_1$, prove that $x_0\in L\vee x_1\in L$. There is a generic construction from a proof system for $L$. See section 4 of https://cs.au.dk/~ivan/Sigma.pdf. It gives a $\Sigma$-protocol for $x_0\in L\vee x_1\in L$ given one for $L$.

Applied to this specific language it would look like this:

  • Say the prover knows an isomorphism between $G_0$ and $G_1$ (the actions are symmetric for the other case). It first runs the ZK simulator for the well-known graph isomorphism $\Sigma$-protocol on input $(G'_0,G'_1)$ to get a transcript $(a',e',z')$ that's indistinguishable from a valid transcript. The prover then sends a random isomorphic copy $a\simeq G_0$ to the verifier.
  • The verifier provides a challenge $s\in\{0,1\}$.
  • The prover sets $e=s\oplus e'$ and answers to challenge $e$ for the graph isomorphism protocol: either reveal the isomorphism $z$ from $H$ to $G_0$ if $e=0$ or the isomorphism from $H$ to $G_1$ if $e=1$.
  • Verifier accepts if $s=e\oplus e'$ and if $(a,e,z)$ and $(a',e',z')$ are both accepting transcripts.
  • $\begingroup$ When it runs the simulator on $(G'_0, G'_1)$, why can we claim it is indistinguishable from a valid transcript? The indistinguishably is only guaranteed for $x \in L$ $\endgroup$
    – Stevie
    Commented Mar 12 at 16:55
  • 1
    $\begingroup$ You're correct that this construction would not work in general when indistinguishability is only guaranteed to hold for $x\in L$. But the ZK simulator for the regular graph isomorphism also works when $G_1'$ and $G_0'$ are not isomorphic. It produces $H$ isomorphic to one of the two graphs and if its guess of $e$ is correct, then the transcript is identical to a real one. $\endgroup$
    – lamontap
    Commented Mar 12 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.