]> Cryptography - Zero-Knowledge Proofs

Let Σ={0,1 }. Let L be a language. Recall LNP means that there exists a determinstic algorithm V:Σ *×Σ *{0,1 } and that xL means that there exists a PΣ * such that V(x,P)=1 with P<poly(x). We say that P is a short proof that xL.

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 N *.

Let LΣ *. A zero-knowledge proof system for L is a pair (P,V) satisfying

  1. (Complete) For all xL, a verifier says "yes" after interacting with the prover

  2. (Sound) For all xL, 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 xL,

    {transcript((P,V *)(x))}={S *(x)}

    (equality of distributions)

The existence of a simulator implies that if xL, then V * cannot learn more than the fact that xL.

Example: Let N=pq,x N *. Suppose we wish to prove that x is a quadratic residue in N *. Then let x=α 2 (modulo N).

  • P: r N, sends a=r 2

  • V: sends b{0,1 }

  • P: sends z=rα 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 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 N *, and a random b{0,1 }.

  2. Set a=z 2 /x bmodN

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

  4. V * outputs some b in {0,1 }. If bb 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 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 N, sends a 1 =r 1 2 ,...,a n=r n 2

  • V: sends b 1 ,...,b n{0,1 }

  • P: sends z 1 =r 1 α 1 b,...,z n=r nalpha n b

  • V: tests z i 2 =a ix 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 LBPP.

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,ε)-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 xL, the distribution {transcript((P,V *)(x))} is (t,ε)-indistinguishable from {S *(x)}.

Theorem [GMW '87]: If a (t,ε)-bit commitment scheme exists, then all languages in NP have computational ZK proofs.

Definition: (imprecise definition) A (t,ε)-bit commitment scheme is defined as follows:

  1. Commiter has a bit b{0,1 }, and sends commit(b){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 bb. Sound: commit(b) reveals no information about b, i.e. for any bit b{0,1 }, {commit(b),b} is (t,ε)-indistinguishable from {commit(b),rr{0,1 }}.

Example: one-way permutations imply commitment schemes:

Let f:{0,1 } n{0,1 } n be a one-way permutation. Choose r{0,1 } n, and set commit(b)=[f(r),B(r)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 g,g a,g b,g ab where gG is of order q.

Chaum-Pederson ZK protocol: Denote g,A,B,C=g,g a,g b,g ab

  • V: s q, sends commit(s).

  • P: r q, sends y 1 =g r,y 2 =B r.

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

  • P: sends z=a+rs(modq)

  • V: checks g z=A sy 1 (modp) and B z=C sy 2 (modp)

Aside: consider this commitment scheme: for some s q, set commit(s)=g sh r for some r 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=g,A,B,C=langeg,g a,g b,g ab. Then a simulator S * can be constructed as follows:

  1. Pick a random 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]