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]$