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
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) \]
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 .
Proof of Composition Lemma
Only Proof for perfect zero-knowledge
Using Alternating Form of Zero-Knowledge
Construction
\(M^*\) inputs \((x,z)\) , \(st_0=\varnothing\) .
For \(i=1,2,\cdots q\) :
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.
By zero-knowledge , \(\exists M_i^*(x,st_{i-1}|z)\) that can simulate the output of \(V_i^*\).
\(M^*\) runs \(M_i^*(x,st_{i-1}|z)\) to obtain \(st_i\).
\(M^*\) invokes \(V^*\) with \(st_q\) to obtain final output.
Proof of \(M^*(x,z)\equiv \braket{P(y),V^*(z)}(x)\)
\(Hyb_0\) : Real Execution \(\braket{P(y),V^*(z)}(x)\)
\(Hyb_1\) :
- Run \(P(y)\) and \(V^*(z)\) until the last phase .
- Record the state of \(V^*\) as \(st_{q-1}\) .
- Invoke \(M_q^*(x,st_{q-1}|z)\) to obtain \(st_q\) .
- 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
- Run \(V_q^*(x,st_{q-1},z)\) to obtain \(st_q\)
- 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\).
\(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\)
\(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)
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} \]
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.
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
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)\} \]
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} \]
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
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})\} \]
- \(Hyb_0\) : \(a,b\gets \mathbb Z_p :(g^a,g^b,mg^{ab})\)
- \(Hyb_1\) : \(a,b,c\gets \mathbb Z_p:(g^a,g^b,mg^c)\)
- \(Hyb_2\) : \(a,b,c\gets \mathbb Z_p:(g^a,g^b,m'g^c)\)\
- \(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
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 \]
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 \]
Perfect Hiding
\(c=g^rh^m\) , which is the same distribution as \(g^r\) , since \(r\) is random .
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
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
NP , NPC
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 .
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
Graph Hamiltonicity
Def [ Hamiltonian ] : A graph \(G\) is Hamiltonian , if there exists a cycle visiting each node exactly once.
Construct zk-proof for Graph Hamiltonicity
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
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