ZKP and MPC 3

Lec02 Zero-Knowledge Proof under Composition

2.3 Sequential Composition

$V^{\ast }$ : should be viewed as a black box , input $(input,randomness,messages)$ , output response

If guess wrong at $m_i$ , we can rewind $V^{\ast }$ to the time when it receives $m_i$ , using the same input , randomness , first $i-1$ messages

1. Def [ Zero-Knowledge Proof with Auxiliary Input ] :

   $(P,V)$ is an interactive zero-knowledge proof with auxiliary input for $L$ if

   • $V$ is an efficient algorithm ( poly-time )

   • Completeness : $\mathrm{\forall }x\in L,\mathrm{\forall }y,z\in \{0,1{\}}^{\ast }$ $$Pr\{⟨P(y),V(z)⟩(x)=1\}=1$$

   • Soundness with error $ϵ$ : $\mathrm{\forall }x\notin L,\mathrm{\forall }y,z\in \{0,1{\}}^{\ast }$ $$\mathrm{\forall }{P}^{\ast },Pr\{⟨P^{\ast }(y),V(z)⟩(x)=1\}<ϵ$$

   • Zero-Knowledge : $\mathrm{\forall }{V}^{\ast }$ in P.P.T. , $\mathrm{\exists }$ expected poly-time algorithm $M^{\ast }$ , $\mathrm{\forall }x\in L,\mathrm{\forall }y,z\in \{0,1{\}}^{\ast }$ , $$M^{\ast }(x,z)\sim Vie{w}_{V^{\ast }(z)}^{P(y)}(x)$$

   $y$ is indeed redundant since $P$ is not computationally bounded

   Alternating Form of Zero-Knowledge : $\mathrm{\forall }{V}^{\ast },\mathrm{\exists }{M}^{\ast },\mathrm{\forall }x\in L,\mathrm{\forall }y,z\in \{0,1{\}}^{\ast }$ $$M^{\ast }(x,z)\sim ⟨P(y),V^{\ast }(z)⟩(x)$$

2. Lemma [ Composition Lemma ] :

   $(P,V)$ : zero-knowledge proof with auxiliary input for $L$ , $q$ is a polynomial of $\kappa$

   $(P_q,V_q)$ : An IP runs $(P,V)$ $q$ times

   Claim : $(P_q,V_q)$ are still zero-knowledge .

3. Proof of Composition Lemma

   Only Proof for perfect zero-knowledge

   Using Alternating Form of Zero-Knowledge

   Construction

   1. $M^{\ast }$ inputs $(x,z)$ , $s{t}_0=\varnothing$ .

   2. For $i=1,2,\cdots q$ :

      1. Construct $V_i^{\ast }$ : $V_i^{\ast }(x,s{t}_{i-1},z)=\{\begin{array}{ll}{V}^{\ast }(x,z)& i=1\\ V^{\ast }(s{t}_{i-1})& i\ge 2\end{array}$ , output state of $V^{\ast }$ as $s{t}_i$

         Note : for $i\ge 2$ , $x,z$ are contained in $s{t}_{i-1}$ , so we do not need to input them.

      2. By zero-knowledge , $\mathrm{\exists }{M}_i^{\ast }(x,s{t}_{i-1}|z)$ that can simulate the output of $V_i^{\ast }$.

      3. $M^{\ast }$ runs $M_i^{\ast }(x,s{t}_{i-1}|z)$ to obtain $s{t}_i$.

   3. $M^{\ast }$ invokes $V^{\ast }$ with $s{t}_q$ to obtain final output.

   Proof of $M^{\ast }(x,z)\equiv ⟨P(y),V^{\ast }(z)⟩(x)$

   0. $Hy{b}_0$ : Real Execution $⟨P(y),V^{\ast }(z)⟩(x)$

   1. $Hy{b}_1$ :

      1. Run $P(y)$ and $V^{\ast }(z)$ until the last phase .
      2. Record the state of $V^{\ast }$ as $s{t}_{q-1}$ .
      3. Invoke $M_q^{\ast }(x,s{t}_{q-1}|z)$ to obtain $s{t}_q$ .
      4. Invoke $V^{\ast }$ with $s{t}_q$ to obtain final output .

      Proof of $Hy{b}_0\equiv Hy{b}_1$ :

      Fix state $s{t}_{q-1}$ . For $Hy{b}_0$ , its distribution is the same as

      1. Run $V_q^{\ast }(x,s{t}_{q-1},z)$ to obtain $s{t}_q$
      2. Run $V^{\ast }$ with $s{t}_q$ to obtain final output

      By zk , given $x,s{t}_{q-1},z$ , $V_q^{\ast }(x,s{t}_{q-1},z)\equiv M_q^{\ast }(x,s{t}_{q-1}|z)$.

      Therefore , $Hy{b}_0\equiv Hy{b}_1$.

   2. $Hy{b}_i$ : Change to $M^{\ast }$ after the first $q-i$ phases

      $Hy{b}_{i-1}$ : using $V_{q-i+1}^{\ast }$ , $Hy{b}_i$ : using $M_{q-i+1}^{\ast }$

      Therefore , $Hy{b}_{i-1}\equiv Hy{b}_i$

   3. $Hy{b}_{q+1}$ : The execution of $M^{\ast }$ .

Lec03 Commitment Scheme , zk-proof for general NP

3.0 Important

In the next lecture , we re-defined commitment in a more simple way .

3.1 Commitment

Intuition :

Binding : make some choice , then won't change it . (change will be rejected)

Hiding : like "safe" , until open it , not knowing the choice . (uniform distribution)

1. Def [ Commitment ] : Three P.P.T. algorithms

   • $Gen(1^{\kappa })\to pp$ ( public parameter )
   • $Commi{t}_{pp}(m,r)\to (c,aux)$
   • $Verif{y}_{pp}(m,c,aux)\to \{Accept,Reject\}$

   Satisfying properties :

   • Hiding : $\mathrm{\forall }m,m^{\prime }$ , the following distributions are identical/statistically indistinguishable/computationally indistinguishable

   $$Dist\{pp\leftarrow Gen(1^{\kappa }),(c,aux)\leftarrow Commi{t}_{pp}(m,r):(pp,c)\}$$

   $$Dist\{pp\leftarrow Gen(1^{\kappa }),(c,aux)\leftarrow Commi{t}_{pp}(m^{\prime },r):(pp,c)\}$$

   • Binding : $\mathrm{\forall }m\ne m^{\prime }$ , $\mathrm{\forall }pp\leftarrow Gen(1^{\kappa })$ ,

     Perfect Binding : $$\{c|(c,aux)\leftarrow Commi{t}_{pp}(m,r)\}\cap \{c|(c,aux)\leftarrow Commi{t}_{pp}(m^{\prime },r)\}=\varnothing$$ Computationally Binding : $\mathrm{\forall }{P}^{\ast }$ in P.P.T.

$$Pr\{pp\leftarrow Gen(1^{\kappa }),(c,m,aux,m^{\prime },au{x}^{\prime })\leftarrow P^{\ast }(pp):Verif{y}_{pp}(c,m,aux)=Verify(c,m^{\prime },au{x}^{\prime })=Accept\}<ϵ$$

2. Open Commitment ( implement $Verif{y}_{pp}$ )

   One general way : let $aux=r$

   Verify checks whether $(c,aux)=Commi{t}_{pp}(m,r=aux)$

   There exists faster Verify for some specific problems.

3. Note : hiding and binding are incompatible

   hiding : $c$ can from different $m$

   binding : $c$ cannot from different $m$

3.2 Perfect Binding & Computationally Hiding Commitment

1. DDH assumption

   $G=⟨g⟩$ , $|g|=p$ , $p\sim \kappa$ , The following distributions are computationally indistinguishable $$Dist\{a,b\leftarrow {\mathbb{Z}}_p:(g,g^a,g^b,g^{ab})\}$$

   $$Dist\{a,b,c\leftarrow {\mathbb{Z}}_p:(g,g^a,g^b,g^c)\}$$

2. Construction

   Suppose that $m\in G$ $$Gen(1^{\kappa })\to (G,p,g)$$

   $$Commi{t}_{pp}(m,(a,b))\to c=(g^a,g^b,m{g}^{ab}),aux=(a,b)$$

   $$Verif{y}_{pp}(c,m,aux):\text{check }{c}_1=g^a\wedge c_2=g^b\wedge c_3=g^{ab}$$

3. Perfect Binding

   For $c=(c_1,c_2,c_3)$ , $\mathrm{\exists }$ unique $a,b$ , s.t. $c_1=g^a,c_2=g^b$ .

   Therefore , $m=\frac{c_3}{g^{ab}}$ , which is uniquely determined

4. Computationally Hiding [Prove by Hybrid Proof]

   We want to prove that $$\{a,b\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m{g}^{ab})\}\sim \{a,b\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m^{\prime }{g}^{ab})\}$$

   0. $Hy{b}_0$ : $a,b\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m{g}^{ab})$
   1. $Hy{b}_1$ : $a,b,c\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m{g}^c)$
   2. $Hy{b}_2$ : $a,b,c\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m^{\prime }{g}^c)$\
   3. $Hy{b}_3$ : $a,b,c\leftarrow {\mathbb{Z}}_p:(g^a,g^b,m^{\prime }{g}^{ab})$

   $$Hy{b}_0\sim Hy{b}_1\equiv Hy{b}_2\sim Hy{b}_3$$

3.3 Computationally Binding & Perfect Hiding Commitment

1. Discrete Log Assumption

   $G=⟨g⟩$ , $|g|=p$ . $\mathrm{\forall }A$ in P.P.T. , $$Pr\{a\leftarrow {\mathbb{Z}}_p:A(G,p,g,g^a)=a\}<ϵ$$

2. Construction

   Suppose that $m\in {\mathbb{Z}}_p$ $$Gen(1^{\kappa })\to (G,p,g,h=g^a)$$ $a\leftarrow {\mathbb{Z}}_p$ , and we need to "forget" $a$ . $$Commi{t}_{pp}(m,r):r\leftarrow {\mathbb{Z}}_p,c=g^r{h}^m,aux=r$$

   $$Verif{y}_{pp}(c,m,aux):\text{ check }c=g^{aux}{h}^m$$

3. Perfect Hiding

   $c=g^r{h}^m$ , which is the same distribution as $g^r$ , since $r$ is random .

4. Computationally Binding

   Suppose that we have P.P.T. $A$ that $A(G,p,g,h)\to (c,m,aux,m^{\prime },au{x}^{\prime })$ , s.t. $$c=g^{aux}{h}^m=g^{au{x}^{\prime }}{h}^{m^{\prime }}$$ Therefore : $$aux+am=au{x}^{\prime }+a{m}^{\prime }$$ Therefore : $$a=\frac{aux-au{x}^{\prime }}{m^{\prime }-m}$$ which contradicts with Discrete Log assumption

5. How to generate $h=g^a$

   • Generate by Sender ? NO

     knows $a$ , then $c=g^{r+am}$ . Sender can choose proper $r$ to reconstruct $m$ .

   • Generate by Receiver ? YES

     knows $a$ not affect hiding

   perfect binding + computationally hiding : Sender runs Gen

   computationally binding + perfect hiding : Receiver runs Gen

3.4 General NP Problem

1. NP , NPC

   1. Def [ NP ] : $L\in NP$ if $\mathrm{\exists }$ poly-time algorithm $D$ ,

      $x\in L\iff \mathrm{\exists }w,D(x,w)=1$

      $w$ is called the proof .

   2. Def [ NP-Complete ] : $L^{\prime }\in NP-Complete$ if $\mathrm{\forall }L\in NP$ , $\mathrm{\exists }$ poly-time algorithm $Q$ , s.t.

      $Q(x,w)=(x^{\prime },w^{\prime })$ , and $x\in L\equiv x^{\prime }\in L^{\prime }$ .

      i.e. all NP problems can be poly-reducible to NP-Complete Problem

2. Graph Hamiltonicity

   1. Def [ Hamiltonian ] : A graph $G$ is Hamiltonian , if there exists a cycle visiting each node exactly once.

   2. Construct zk-proof for Graph Hamiltonicity

      1. Like GI :

         Step 1 : send $\tilde{G}$ , where $G\sim \tilde{G}$

         Step 2 : give a cycle of $\tilde{G}$ to prove its Hamiltonian

         Traditional ways : we cannot realize both

      2. Protocol with commitment

      Commitment of a graph $G$ : $\mathrm{\forall }i,j\in [n]$ , $$(c_{i,j},au{x}_{i,j})\leftarrow \{\begin{array}{ll}Commi{t}_{pp}(1,r)& (i,j)\in E\\ Commi{t}_{pp}(0,r)& (i,j)\notin E\end{array}$$

      Prover		Verifier
      $\pi \leftarrow S_n$ , $\tilde{G}:=\pi (G)$
      Commit $\tilde{G}$ :	---$c_{i,j}$-->
      	<--$b$---	$b\leftarrow \{0,1\}$
      If $b=0$	---$\pi ,m_{i,j},au{x}_{i,j}$-->	Checks $\tilde{G}=\pi (G)$
      If $b=1$	---cycle for $\tilde{G}$ , $m_{i,j},au{x}_{i,j}$ in cycle--->	Checks cycle and edges existence