ZKP and MPC 3

Lec02 Zero-Knowledge Proof under Composition

2.3 Sequential Composition

\(V^*\) : should be viewed as a black box , input \((input,randomness,messages)\) , output response

If guess wrong at \(m_i\) , we can rewind \(V^*\) 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 : \(\forall x\in L,\forall y,z\in \{0,1\}^*\) \[ \Pr\{\braket{P(y),V(z)}(x)=1\}=1 \]

    • Soundness with error \(\epsilon\) : \(\forall x\notin L,\forall y,z\in \{0,1\}^*\) \[ \forall P^*,\Pr\{\braket{P^*(y),V(z)}(x)=1\}<\epsilon \]

    • Zero-Knowledge : \(\forall V^*\) in P.P.T. , \(\exists\) expected poly-time algorithm \(M^*\) , \(\forall x\in L,\forall y,z\in \{0,1\}^*\) , \[ M^*(x,z)\sim View_{V^*(z)}^{P(y)}(x) \]

    \(y\) is indeed redundant since \(P\) is not computationally bounded

    Alternating Form of Zero-Knowledge : \(\forall V^*,\exists M^*,\forall x\in L,\forall y,z\in \{0,1\}^*\) \[ M^*(x,z)\sim \braket{P(y),V^*(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^*\) inputs \((x,z)\) , \(st_0=\varnothing\) .

    2. For \(i=1,2,\cdots q\) :

      1. Construct \(V_i^*\) : \(V_i^*(x,st_{i-1},z)=\begin{cases}V^*(x,z)&i=1\\V^*(st_{i-1})&i\ge 2\end{cases}\) , output state of \(V^*\) as \(st_i\)

        Note : for \(i\ge 2\) , \(x,z\) are contained in \(st_{i-1}\) , so we do not need to input them.

      2. By zero-knowledge , \(\exists M_i^*(x,st_{i-1}|z)\) that can simulate the output of \(V_i^*\).

      3. \(M^*\) runs \(M_i^*(x,st_{i-1}|z)\) to obtain \(st_i\).

    3. \(M^*\) invokes \(V^*\) with \(st_q\) to obtain final output.

    Proof of \(M^*(x,z)\equiv \braket{P(y),V^*(z)}(x)\)

    1. \(Hyb_0\) : Real Execution \(\braket{P(y),V^*(z)}(x)\)

    2. \(Hyb_1\) :

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

      Proof of \(Hyb_0\equiv Hyb_1\) :

      Fix state \(st_{q-1}\) . For \(Hyb_0\) , its distribution is the same as

      1. Run \(V_q^*(x,st_{q-1},z)\) to obtain \(st_q\)
      2. Run \(V^*\) with \(st_q\) to obtain final output

      By zk , given \(x,st_{q-1},z\) , \(V_q^*(x,st_{q-1},z)\equiv M_q^*(x,st_{q-1}|z)\).

      Therefore , \(Hyb_0\equiv Hyb_1\).

    3. \(Hyb_i\) : Change to \(M^*\) after the first \(q-i\) phases

      \(Hyb_{i-1}\) : using \(V^*_{q-i+1}\) , \(Hyb_i\) : using \(M^*_{q-i+1}\)

      Therefore , \(Hyb_{i-1}\equiv Hyb_i\)

    4. \(Hyb_{q+1}\) : The execution of \(M^*\) .

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 )
    • \(Commit_{pp}(m,r)\to (c,aux)\)
    • \(Verify_{pp}(m,c,aux)\to\{Accept,Reject\}\)

    Satisfying properties :

    • Hiding : \(\forall m,m'\) , the following distributions are identical/statistically indistinguishable/computationally indistinguishable

    \[ Dist\{pp\gets Gen(1^\kappa),(c,aux)\gets Commit_{pp}(m,r) : (pp,c)\} \]

    \[ Dist\{pp\gets Gen(1^\kappa),(c,aux)\gets Commit_{pp}(m',r) : (pp,c)\} \]

    • Binding : \(\forall m\neq m'\) , \(\forall pp\gets Gen(1^\kappa)\) ,

      Perfect Binding : \[ \{c|(c,aux)\gets Commit_{pp}(m,r)\}\cap\{c|(c,aux)\gets Commit_{pp}(m',r)\}=\varnothing \] Computationally Binding : \(\forall P^*\) in P.P.T.

\[ \small{\Pr\{pp\gets Gen(1^\kappa) , (c,m,aux,m',aux')\gets P^*(pp) : Verify_{pp}(c,m,aux)=Verify(c,m',aux')=Accept\}<\epsilon} \]

  1. Open Commitment ( implement \(Verify_{pp}\) )

    One general way : let \(aux=r\)

    Verify checks whether \((c,aux)=Commit_{pp}(m,r=aux)\)

    There exists faster Verify for some specific problems.

  2. 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=\braket g\) , \(|g|=p\) , \(p\sim \kappa\) , The following distributions are computationally indistinguishable \[ Dist\{a,b\gets \mathbb Z_p :(g,g^a,g^b,g^{ab})\} \]

    \[ Dist\{a,b,c\gets\mathbb Z_p:(g,g^a,g^b,g^c)\} \]

  2. Construction

    Suppose that \(m\in G\) \[ Gen(1^\kappa)\to(G,p,g) \]

    \[ Commit_{pp}(m,(a,b))\to c=(g^a,g^b,mg^{ab}),aux=(a,b) \]

    \[ Verify_{pp}(c,m,aux):\text{check }c_1=g^a\land c_2=g^b\land c_3=g^{ab} \]

  3. Perfect Binding

    For \(c=(c_1,c_2,c_3)\) , \(\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\gets \mathbb Z_p:(g^a,g^b,mg^{ab})\}\sim \{a,b\gets \mathbb Z_p:(g^a,g^b,m'g^{ab})\} \]

    1. \(Hyb_0\) : \(a,b\gets \mathbb Z_p :(g^a,g^b,mg^{ab})\)
    2. \(Hyb_1\) : \(a,b,c\gets \mathbb Z_p:(g^a,g^b,mg^c)\)
    3. \(Hyb_2\) : \(a,b,c\gets \mathbb Z_p:(g^a,g^b,m'g^c)\)\
    4. \(Hyb_3\) : \(a,b,c\gets \mathbb Z_p:(g^a,g^b,m'g^{ab})\)

    \[ Hyb_0\sim Hyb_1\equiv Hyb_2\sim Hyb_3 \]

3.3 Computationally Binding & Perfect Hiding Commitment

  1. Discrete Log Assumption

    \(G=\braket{g}\) , \(|g|=p\) . \(\forall A\) in P.P.T. , \[ \Pr\{a\gets \mathbb Z_p:A(G,p,g,g^a)=a\}<\epsilon \]

  2. Construction

    Suppose that \(m\in \mathbb Z_p\) \[ Gen(1^\kappa)\to (G,p,g,h=g^a) \] \(a\gets \mathbb Z_p\) , and we need to "forget" \(a\) . \[ Commit_{pp}(m,r):r\gets \mathbb Z_p,c=g^rh^m,aux=r \]

    \[ Verify_{pp}(c,m,aux):\text{ check } c=g^{aux}h^m \]

  3. Perfect Hiding

    \(c=g^rh^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',aux')\) , s.t. \[ c=g^{aux}h^m=g^{aux'}h^{m'} \] Therefore : \[ aux+am=aux'+am' \] Therefore : \[ a=\frac{aux-aux'}{m'-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 \(\exists\ \) poly-time algorithm \(D\) ,

      \(x\in L\Leftrightarrow \exists w\ ,\ D(x,w)=1\)

      \(w\) is called the proof .

    2. Def [ NP-Complete ] : \(L'\in NP-Complete\) if \(\forall L\in NP\) , \(\exists\ \) poly-time algorithm \(Q\) , s.t.

      \(Q(x,w)=(x',w')\) , and \(x\in L\equiv x'\in L'\) .

      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\) : \(\forall i,j\in [n]\) , \[ (c_{i,j},aux_{i,j})\gets\begin{cases} Commit_{pp}(1,r)&(i,j)\in E\\ Commit_{pp}(0,r)&(i,j)\notin E \end{cases} \]

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