Zero-Knowledge Proofs
Let \(\Sigma = \{0,1\}\). Let \(L\) be a language. Recall \(L \in NP\) means that there exists a determinstic algorithm \(V:\Sigma^* \times \Sigma^* \rightarrow \{0,1\}\) and that \(x \in L\) means that there exists a \(P \in \Sigma^*\) such that \(V(x,P) = 1\) with \(|P| \lt poly(|x|)\). We say that \(P\) is a short proof that \(x \in L\).
If \(V\) is randomized, then we have the MA complexity class. If \(V\) can interact with \(P\), then we get IP (interactive proofs). It turns out that \(IP = PSPACE\) [Shamir].
Zero-Knowledge Proof Systems
The goal is to prove a statement without leaking extra information, for example, for some \(N,x\), prove \(x\) is a quadratic residue in \(\mathbb{Z}_N^*\).
Let \(L \subseteq \Sigma^*\). A zero-knowledge proof system for \(L\) is a pair \((P,V)\) satisfying
-
(Complete) For all \(x \in L\), a verifier says "yes" after interacting with the prover
-
(Sound) For all \(x \notin L\), and for all provers \(P^*\), a verifier says "no" after interacting with \(P^*\) with probability at least \(1/2\).
-
(Perfect) For all verifiers \(V^*\), there exists a simulator \(S^*\) that is a randomized polynomial time algorithm such that for all \(x \in L\),
\[ \{ transcript((P,V^*)(x)) \} = \{S^*(x)\} \]
+ (equality of distributions)
The existence of a simulator implies that if \(x \in L\), then \(V^*\) cannot learn more than the fact that \(x \in L\).
Example: Let \(N = pq ,x \in \mathbb{Z}_N^*\). Suppose we wish to prove that \(x\) is a quadratic residue in \(\mathbb{Z}_N^*\). Then let \(x = \alpha^2\) (modulo \(N\)).
-
\(P\): \(r \leftarrow \mathbb{Z}_N\), sends \(a = r^2\)
-
\(V\): sends \(b \leftarrow \{0,1\}\)
-
\(P\): sends \(z = r \alpha^b\)
-
\(V\): tests \(z^2 = ax^b\). If so, output "yes", otherwise output "no"
Completeness of this scheme is immediate. As for soundness: if \(a\) is not a quadratic residue, then the verifier says "no" with probability at least one half (i.e. when \(b = 0\)). If \(a\) is a quadratic residue, but \(x\) is not, then the verifier says "no" with probability at least one half (i.e when \(b = 1\)).
Claim: if \(x\) is not a quadratic residue in \(\mathbb{Z}^*_N\) then for all \(P^*\), \(V\) says "no" with probability at least one half.
It remains to show that the scheme is perfect zero-knowledge. Let \(V^*\) be some verifier, and suppose \(transcript((P,V^*)(N,x)) = [a,b,z]\).
Then construct a blackbox simulator \(S^*\) as follows:
-
Pick a random \(z \leftarrow \mathbb{Z}^*_N\), and a random \(b \leftarrow \{0,1\}\).
-
Set \(a=z^2 / x^b \mod N\)
-
Run \(V^*(x)\), give it \(a\) as first message from prover.
-
\(V^*\) outputs some \(b'\) in \(\{0,1\}\). If \(b \neq b'\) then goto step 1, otherwise output \([a,b,z]\) as the transcript. This takes two iterations on average.
Claim: \(\{transcript(P,V^*)(N,x)\} = \{S^*(N,x)\}\) (equality of distributions).
Sketch of proof: \(a\) is uniform in the quadratic residues of \(\mathbb{Z}_N^*\) because \(x\) is a quadratic residue. \(b\) is from the same distribution generated by \(V^*\) given \(a\). \(z\) saitsfies \(z^2 = ax^b\) and is from the correct definition.
Soundness can be improved by repeating the protocol sequentially. One might consider repetition in parallel, i.e.
-
\(P\): \(r_1,...,r_n \leftarrow \mathbb{Z}_N\), sends \(a_1 = r_1^2,...,a_n = r_n^2\)
-
\(V\): sends \(b_1,...,b_n \leftarrow \{0,1\}\)
-
\(P\): sends \(z_1 = r_1 \alpha^b_1,...,z_n = r_n alpha^b_n\)
-
\(V\): tests \(z_i^2 = a_i x^b_i\) for \(i = 1,...,n\). If so, output "yes", otherwise output "no"
This scheme is complete and sound, but it is not clear how to build a simulator. (We can only guess all the \(b_i\)'s correctly with probability \(1/2^n\).)
Theorem [KG '89]: If \(L\) has a three-round perfect zero knowledge proof with negligible cheating probability then \(L \in BPP\).
Since it is believed that quadratic residuosity is not in BPP, it is therefore also thought that no three-round strongly sound perfect zero knowledge protocol for quadratic residuosity exists.
Hence we introduce a weaker version of zero knowledge:
Computational ZK: \((P,V)\) is a \((t,\epsilon)\)-zero-knowledge proof system for a language \(L\) if it is
-
Sound
-
Complete
-
Computational ZK: for all verifiers \(V^*\) there exists a simulator \(S^*\) such that for all \(x \in L\), the distribution \(\{transcript((P,V^*)(x))\}\) is \((t,\epsilon)\)-indistinguishable from \(\{S^*(x)\}\).
Theorem [GMW '87]: If a \((t,\epsilon)\)-bit commitment scheme exists, then all languages in \(NP\) have computational ZK proofs.
Definition: (imprecise definition) A \((t,\epsilon)\)-bit commitment scheme is defined as follows:
-
Commiter has a bit \(b \in \{0,1\}\), and sends \(commit(b) \in \{0,1\}^*\) (a commitment to a bit \(b\)).
-
Commiter can open commitment as \(b'\) and the verifier can check that \(b = b'\).
This scheme should be: * Binding: infinitely powerful commiter can’t convince verifier that commitment is a commitment to \(b' \neq b\). * Sound: \(commit(b)\) reveals no information about \(b\), i.e. for any bit \(b\in\{0,1\}\), \(\{commit(b), b\}\) is \((t,\epsilon)\)-indistinguishable from \(\{commit(b), r | r\leftarrow\{0,1\}\}\).
Example: one-way permutations imply commitment schemes:
Let \(f : \{0,1\}^n \rightarrow\{0,1\}^n\) be a one-way permutation. Choose \(r\leftarrow\{0,1\}^n\), and set \(commit(b) = [f(r), B(r) \oplus b]\) where \(B\) is a hardcore bit of \(f\).
ZK for DDH
The language \(L_{DDH}\) is defined to be the set of all tuples \(\langle g, g^a, g^b, g^ab \rangle\) where \(g\in G\) is of order \(q\).
Chaum-Pederson ZK protocol: Denote \(\langle g,A,B,C \rangle = \langle g, g^a, g^b, g^{ab} \rangle\)
-
V: \(s\leftarrow\mathbb{Z}_q\), sends \(commit(s)\).
-
P: \(r\leftarrow\mathbb{Z}_q\), sends \(y_1 = g^r, y_2 = B^r\).
-
V: sends \(s\) (i.e. opens the commitment)
-
P: sends \(z = r + as \pmod q\)
-
V: checks \(g^z = A^s y_1 \pmod q\) and \(B^z = C^s y_2 \pmod q\)
Aside: consider this commitment scheme: for some \(s \in \mathbb{Z}_q\), set \(commit(s) = g^s h^r\) for some \(r \leftarrow \mathbb{Z}_q)\), where \(g,h\) are fixed and public. This is computationally binding (relying on Dlog) but unconditionally sound.
Proof of ZK: Let \(transcript((P,V^*)(I)) = [commit(s),y_1,y_2,s,z]\). Let \(V^*\) be a verifier, let \(I = \langle g,A,B,C \rangle = \langle g, g^a, g^b, g^ab \rangle \). Then a simulator \(S^*\) can be constructed as follows:
-
Pick a random \(z\leftarrow\mathbb{Z}_q\)
-
Run \(V^*\) to get \(commit(s)\)
-
Send random \(y_1, y_2\)
-
\(V^*\) sends \(s\), i.e. opens the commitment.
-
Set \(y'_1 = g^z/A^s , y'_2 = B^z / C^s\)
-
Output \([commit(s),y'_1,y'_2,s,z]\)