]> Cryptography - Zero-Knowledge Proofs

Let $\Sigma =\left\{0,1\right\}$. Let $L$ be a language. Recall $L\in \mathrm{NP}$ means that there exists a determinstic algorithm $V:{\Sigma }^{*}×{\Sigma }^{*}\to \left\{0,1\right\}$ and that $x\in L$ means that there exists a $P\in {\Sigma }^{*}$ such that $V\left(x,P\right)=1$ with $\mid P\mid <\mathrm{poly}\left(\mid x\mid \right)$. 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 $\mathrm{IP}=\mathrm{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 ${ℤ}_{N}^{*}$.

Let $L\subseteq {\Sigma }^{*}$. A zero-knowledge proof system for $L$ is a pair $\left(P,V\right)$ 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$,

$\left\{\mathrm{transcript}\left(\left(P,{V}^{*}\right)\left(x\right)\right)\right\}=\left\{{S}^{*}\left(x\right)\right\}$

(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 {ℤ}_{N}^{*}$. Suppose we wish to prove that $x$ is a quadratic residue in ${ℤ}_{N}^{*}$. Then let $x={\alpha }^{2}$ (modulo $N$).

• $P$: $r←{ℤ}_{N}$, sends $a={r}^{2}$

• $V$: sends $b←\left\{0,1\right\}$

• $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 ${ℤ}_{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}\left(\left(P,{V}^{*}\right)\left(N,x\right)\right)=\left[a,b,z\right]$.

Then construct a blackbox simulator ${S}^{*}$ as follows:

1. Pick a random $z←{ℤ}_{N}^{*}$, and a random $b←\left\{0,1\right\}$.

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

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

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

Claim: $\left\{\mathrm{transcript}\left(P,{V}^{*}\right)\left(N,x\right)\right\}=\left\{{S}^{*}\left(N,x\right)\right\}$ (equality of distributions).

Sketch of proof: $a$ is uniform in the quadratic residues of ${ℤ}_{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}←{ℤ}_{N}$, sends ${a}_{1}={r}_{1}^{2},...,{a}_{n}={r}_{n}^{2}$

• $V$: sends ${b}_{1},...,{b}_{n}←\left\{0,1\right\}$

• $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: $\left(P,V\right)$ is a $\left(t,\epsilon \right)$-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 $\left\{\mathrm{transcript}\left(\left(P,{V}^{*}\right)\left(x\right)\right)\right\}$ is $\left(t,\epsilon \right)$-indistinguishable from $\left\{{S}^{*}\left(x\right)\right\}$.

Theorem [GMW '87]: If a $\left(t,\epsilon \right)$-bit commitment scheme exists, then all languages in $\mathrm{NP}$ have computational ZK proofs.

Definition: (imprecise definition) A $\left(t,\epsilon \right)$-bit commitment scheme is defined as follows:

1. Commiter has a bit $b\in \left\{0,1\right\}$, and sends $\mathrm{commit}\left(b\right)\in \left\{0,1{\right\}}^{*}$ (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}\left(b\right)$ reveals no information about $b$, i.e. for any bit $b\in \left\{0,1\right\}$, $\left\{\mathrm{commit}\left(b\right),b\right\}$ is $\left(t,\epsilon \right)$-indistinguishable from $\left\{\mathrm{commit}\left(b\right),r\mid r←\left\{0,1\right\}\right\}$.

Example: one-way permutations imply commitment schemes:

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

## ZK for DDH

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←{ℤ}_{q}$, sends $\mathrm{commit}\left(s\right)$.

• P: $r←{ℤ}_{q}$, sends ${y}_{1}={g}^{r},{y}_{2}={B}^{r}$.

• V: sends $s$ (i.e. opens the commitment)

• P: sends $z=a+\mathrm{rs}\left(modq\right)$

• V: checks ${g}^{z}={A}^{s}{y}_{1}\left(modp\right)$ and ${B}^{z}={C}^{s}{y}_{2}\left(modp\right)$

Aside: consider this commitment scheme: for some $s\in {ℤ}_{q}$, set $\mathrm{commit}\left(s\right)={g}^{s}{h}^{r}$ for some $r←{ℤ}_{q}\right)$, where $g,h$ are fixed and public. This is computationally binding (relying on Dlog) but unconditionally sound.

Proof of ZK: Let $\mathrm{transcript}\left(\left(P,{V}^{*}\right)\left(I\right)\right)=\left[\mathrm{commit}\left(s\right),{y}_{1},{y}_{2},s,z\right]$. 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←{ℤ}_{q}$

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

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 $\left[\mathrm{commit}\left(s\right),y{\prime }_{1},y{\prime }_{2},s,z\right]$