Cryptography

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

   $$\{\mathrm{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=\mathrm{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 \{\mathrm{0,1}\}$

• $P$: sends $z=r{\alpha }^b$

• $V$: tests $z^2={\mathrm{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 $\mathrm{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 \{\mathrm{0,1}\}$.

2. Set $a=z^2/x^{b}modN$

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

4. $V^{*}$ outputs some $b\prime$ in $\{\mathrm{0,1}\}$. If $b\ne b\prime$ then goto step 1, otherwise output $[a,b,z]$ as the transcript. This takes two iterations on average.

Claim: $\{\mathrm{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={\mathrm{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 \{\mathrm{0,1}\}$

• $P$: sends $z_1=r_1{\alpha }_1^b,...,z_n=r_n{\mathrm{alpha}}_n^b$

• $V$: tests $z_i^2=a_i{x}_i^b$ 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 \mathrm{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 $\{\mathrm{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 $\mathrm{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 \{\mathrm{0,1}\}$, and sends $\mathrm{commit}(b)\in \{\mathrm{0,1}{\}}^{*}$ (a commitment to a bit $b$).

2. Commiter can open commitment as $b\prime$ and the verifier can check that $b=b\prime$.

This scheme should be: Binding: infinitely powerful commiter can't convince verifier that commitment is a commitment to $b\prime \ne b$. Sound: $\mathrm{commit}(b)$ reveals no information about $b$, i.e. for any bit $b\in \{\mathrm{0,1}\}$, $\{\mathrm{commit}(b),b\}$ is $(t,\epsilon )$-indistinguishable from $\{\mathrm{commit}(b),r\mid r\leftarrow \{\mathrm{0,1}\}\}$.

Example: one-way permutations imply commitment schemes:

Let $f:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^n$ be a one-way permutation. Choose $r\leftarrow \{\mathrm{0,1}{\}}^n$, and set $\mathrm{commit}(b)=[f(r),B(r)\oplus b]$ where $B$ is a hardcore bit of $f$.

The language $L_{\mathrm{DDH}}$ is defined to be the set of all tuples $⟨g,g^a,g^b,g^{\mathrm{ab}}⟩$ where $g\in G$ is of order $q$.

Chaum-Pederson ZK protocol: Denote $⟨g,A,B,C⟩=⟨g,g^a,g^b,g^{\mathrm{ab}}⟩$

• V: $s\leftarrow {\mathbb{Z}}_q$, sends $\mathrm{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=a+\mathrm{rs}(modq)$

• V: checks $g^z=A^s{y}_1(modp)$ and $B^z=C^s{y}_2(modp)$

Aside: consider this commitment scheme: for some $s\in {\mathbb{Z}}_q$, set $\mathrm{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 $\mathrm{transcript}((P,V^{*})(I))=[\mathrm{commit}(s),y_1,y_2,s,z]$. Let $V^{*}$ be a verifier, let $I=⟨g,A,B,C⟩=langeg,g^a,g^b,g^{\mathrm{ab}}⟩$. Then a simulator $S^{*}$ can be constructed as follows:

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

2. Run $V^{*}$ to get $\mathrm{commit}(s)$

3. Send random $y_1,y_2$

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

5. Set $y{\prime }_1=g^z/A^s,y{\prime }_2=B^z/C^s$

6. Output $[\mathrm{commit}(s),y{\prime }_1,y{\prime }_2,s,z]$