# 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

1. (Complete) For all $$x \in L$$, a verifier says "yes" after interacting with the prover

2. (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$$.

3. (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:

1. Pick a random $$z \leftarrow \mathbb{Z}^*_N$$, and a random $$b \leftarrow \{0,1\}$$.

2. Set $$a=z^2 / x^b \mod N$$

3. Run $$V^*(x)$$, give it $$a$$ as first message from prover.

4. $$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

1. Sound

2. Complete

3. 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:

1. Commiter has a bit $$b \in \{0,1\}$$, and sends $$commit(b) \in \{0,1\}^*$$ (a commitment to a bit $$b$$).

2. 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:

1. Pick a random $$z\leftarrow\mathbb{Z}_q$$

2. Run $$V^*$$ to get $$commit(s)$$

3. Send random $$y_1, y_2$$

4. $$V^*$$ sends $$s$$, i.e. opens the commitment.

5. Set $$y'_1 = g^z/A^s , y'_2 = B^z / C^s$$

6. Output $$[commit(s),y'_1,y'_2,s,z]$$

Ben Lynn blynn@cs.stanford.edu 💡