16 Zero-knowledge proofs

Recall the ID-Schemes in Definition 14.2. In a sense, they were “proofs” that the prover had the secret key. We will explore this idea further in this section. A proof system in cryptography can be interactive, as in the case of an ID scheme, i.e. some arbitrary back and forth of messages between a prover \(P\) and a verifier \(V\). Typically, what \(P\) does is to send a message \(x\) which has some property that can be proved using a \(w\). Crucially, we would like \(V\) to learn nothing about \(w\) just by seeing \(x\).

The properties of proof systems that we typically care about are:

16.1 Graph isomorphism proof

Given two graphs \(G_1\) and \(G_2\) (which we can consider without loss of generality that they contain the same set of vertices \(V=\{1,\ldots,n\}\)), we say that they are isomorphic or that \(G_1\approx G_1\) iff there exists a bijection \(\Phi:V\rightarrow V\) such that \(\Phi(G_1)=G_2\), as it is the case for the two graphs drawn below:

Graph isomorphism

There are no known polynomial-time classical nor quantum algorithms for checking graph isomorphism (GI). We can build a ZK proof for GI as follows:

Let’s check each property of this proof for GI separately:

Intuitively: if witness is correct and P, V are honest, then V accepts.

To formalize this, we specify a relation \(R\): \((x,w)\in R\) iff \(w\) is a valid witness for \(x\). Specifically for GI, we define \(R_{GI}:=\{((G_1, G_2),\Phi):\) \(G_1,G_2\) are graphs with same set \(\mathcal{V}\) of vertices and \(\Phi: \mathcal{V} \rightarrow \mathcal{V}\) is an isomorphism \(G_1\rightarrow G_2\}\).

Definition 16.1 \((P, V)\) is (perfectly) complete for relation \(R\) iff \(\forall (x,w)\in R: \Pr[\langle P(x,w), V(x)\rangle=1]=1\)

Recall that \(\langle P(x,w), V(x)\rangle\) refers to the output of \(V\) after interacting with \(P\).

Theorem

\((P_{GI}, V_{GI})\) is perfectly complete for relation \(R_{GI}\).

Intuitively: without a valid witness, P cannot produce something that V accepts.

Definition 16.2 \((P,V)\) is (statistically) \(\epsilon\)-sound for relation \(R\) iff for all adversaries \(P^*\) (possibly computationally unlimited): \[\forall x \notin L_R: \Pr[\langle P^*, V(x)\rangle =1]\leq\epsilon\]

Where \(L_R:=\{x:\exists w.(x,w)\in R\}\) is the language of R, that is, the set of all statements \(x\) for which there is a valid witness \(w\). Specifically for GI, \(L_{R_{GI}}=\{(G_1,G_2):G_1\approx G_2\}\).

Theorem

The GI proof \((P_{GI}, V_{GI})\) is \((\epsilon=\frac{1}{2})\)-sound for \(R_{GI}\).

Fix \(P^*\), fix \((G_1, G_2)\in L_{R_{GI}}\) such that \(G_1\napprox G_2\). \(P^*\) then sends some \(H\).

If \(H\approx G_1\) and \(H\approx G_2\), then \(G_1\approx G_2\), which is not the case by definition. This means that \(\exists j\in\{1,2\}\) such that \(G_j\napprox H\).

But \(V_{GI}\) picks \(i\) after \(H\) was chosen, which means that \(\Pr[i=j]\geq\frac{1}{2}\) for given \(H\) since \(i\) and \(j\) are independent. If \(i=j\), then there is no isomorphism \(\psi_i:G_i\rightarrow H\), so \(V_{GI}\) rejects. That is, \[\Pr[\langle P^*, V_{GI}(G_1,G_2)\rangle=1]=1-\Pr[V_{GI}\textrm{ rejects}]\leq\frac{1}{2}=\epsilon.\]