ZKP and MPC 1

发表于 2023-10-06 更新于 2023-10-27 分类于课程笔记，零知识证明和多方安全计算阅读次数：本文字数： 1.9k 阅读时长 ≈ 7 分钟

[2023 秋] 零知识证明与多方安全计算第一课课堂笔记 / [2023 Fall] Zero-Knowledge Proof and Secure Multi-Party Computation Lecture 1 Notes

Lec01 Basic Definitions and Examples of ZKP

1 Basic Notations

Complexity
1. Efficient Algorithm : poly-time algorithm .
2. NP class : class of problems that are easy to verify a solution (but may be hard to solve it)
  
  Formal def : Suppose $L\subset \{0,1\}^*$ is a language . $L\in NP$ if there exists a poly-time algorithm $\mathcal A$ :
  - If $x\in L$ , $\exists w\in \{0,1\}^{poly(|x|)}$ , $\mathcal A(x,w)=1$
  - If $x\notin L$ , $\forall w\in \{0,1\}^{poly(|x|)}$ , $\mathcal A(x,w)=0$
  $w$ that makes $\mathcal A(x,w)=1$ is called the proof of $x\in L$ , and $\mathcal A$ is called the verification algorithm .
Proof
1. Def : a static sequence of rules
2. E.g.1 : Prove that $f(x,y)=x^2y^3-5xy+4=0$ has a solution .
  
  Proof 1 [Explicit Proof] : $f(1,1)=0$
  
  Proof 2 [Implicit Proof] : $f(2,1)<0,f(2,2)>0$ .
  
  ( $f(2,x)$ is continuous , so $\exists x_0\in (1,2) , f(2,x_0)=0$ )

2 Interactive Proof

Interactive Proof
1. A Prover and a Verifier , Prover needs to convince Verifier some proposition .
  
  Usually , Prover needs to convince Verifier that some proposition is true . $(x\in L)$
2. Prover : with unbounded computation sources
  
  Verifier : Only efficient algorithm
3. Complexity Class : IP : class of problems that are easy to determine with an interactive proof
  - $NP\subsetneq IP$
4. Transcript
  
  Prover sends $m_1$ to Verifier , Verifier receives $m_1$ and sends $m_2$ to Prover , ... \[ \begin{aligned} P(x,r_p)\to m_1\quad \quad &\\ V(x,r_v,m_1,\cdots,m_{i-1})\to m_i\quad& \text{for odd }i\\ P(x,r_p,m_1,\cdots,m_{i-1})\to m_i\quad& \text{for even }i\\ V(x,r_v,m_1,\cdots,m_k)\to y\in \{0,1\}& \end{aligned} \]
  1. Def : transcript : $\tau=\{m_1,\cdots,m_k\}$
  2. Def : $\braket{P,V}(x):=y$
IP Criteria
1. Completeness : If Prover is honest , Verifier accepts the proof .
  
  $\forall x\in L , \Pr\{\left<P,V\right>(x)=1\}=1$
2. Soundness : If Prover is dishonest , Verifier rejects the proof (with high probability) .
3. Zero-Knowledge : If Prover is honest , Verifier cannot know more than "knowing the proposition is true"
Definition (somewhat formal (?) )

A pair of randomized algorithms $(P,V)$ is an interactive proof for $L$
1. $V$ runs in poly-time
2. Completeness : $\forall x\in L , \Pr\{\braket{P,V}(x)=1\}=1$
3. Soundness : $\forall x\notin L,\forall P^*,\Pr\{\braket{P^*,V}(x)=1\}< \epsilon$
4. Zero-Knowledge (Optimal)
  
  $\forall x\in L$ , $V$ can generate everything itself with bounded computation time without interaction
  
  gain sth. cannot gain by PPT $\Rightarrow$ gain knowledge

3 IP Examples

Graph non-Isomorphism

Description

Prover and Verifier know graphs $G_0,G_1$ .

Prover wants to convince verifier that $G_0$ is not isomorphic with $G_1$ . \[ \begin{aligned} &G_0=(V,E_0) , G_1=(V,E_1)\\ \not\exists \pi\in S_{|V|}&\ ,\ \{(\pi(u),\pi(v)):(u,v)\in E_0\}=E_1 \end{aligned} \]

Protocol

Global : Prover and Verifier already know $G_0,G_1$ .

Prover		Verifier
		$b\leftarrow \{0,1\}$ , $\pi\leftarrow S_{\|V\|}$
	<- $\tilde G$ --	$\tilde G:=\pi(G_b)$
Find $b $ , $G_{\tilde b}\sim \tilde G$	-- $\tilde b$ ->
		$y=\begin{cases}1& \text{if }b=\tilde b\\0&\text{otherwise}\end{cases}$

Analysis
1. Completeness : When $G_0\not\sim G_1$ , $G_{\tilde b}\sim \tilde G\sim G_b$ , so $b=\tilde b$ . Always accept .
2. Soundness : When $G_0\sim G_1$ , any prover can only guess $\tilde b$ randomly since $G_0\sim G_1\sim \tilde G$ . $\Pr\{V\text{ accept}\}\le \frac{1}{2}$ .
  
  Proof : $P^*$ knows $\tilde G$ and wants to guess $b$ , we need to prove that \[ \forall P^* , \Pr\{P^*(\tilde G)=b\}\le \frac{1}{2} \] Since $\forall \tilde G\sim G_0\sim G_1$ , \[ \begin{aligned} \Pr\{\pi(G_0)=\tilde G\}&=\Pr\{\pi(G_1)=\tilde G\}\\ \Rightarrow \Pr\{\pi(G_b)=\tilde G|b=0\}&=\Pr\{\pi(G_b)=\tilde G|b=1\}\\ \Rightarrow \Pr\{b=0|\pi(G_b)=\tilde G\}&=\Pr\{b=1|\pi(G_b)=\tilde G\}\\ \end{aligned} \] Therefore , \[ \forall P^* , \Pr\{P^*(\tilde G)=b|\pi(G_b)=\tilde G\}\le\frac{1}{2} \] Therefore , \[ \begin{aligned} \Pr\{P^*(\tilde G)=b\}&=\sum_{\tilde G}\Pr\{P^*(\tilde G)=b|\pi(G_b)=\tilde G\}\Pr\{\pi(G_b)=\tilde G\}\\ &\le \frac{1}{2}\sum_{\tilde G}\Pr\{\pi(G_b)=\tilde G\}\\ &=\frac{1}{2} \end{aligned} \] $k$ rounds : $\Pr\{V\text{ accepts}\}\le \frac{1}{2^k}$ .
3. Zero-Knowledge
  
  Verifier itself knows $b,\pi,\tilde G$ . Prover tells Verifier $\tilde b$ .
  
  Only consider $G_0\not\sim G_1$ , then $\tilde b$ must be $b$ . Verifier itself can generate the transcript .
  
  注意：因为 zero-knowledge 是对 Prover 的保护，我们只需要保护诚实 Prover 的隐私，因此只要考虑命题成立的情况（即 $G_0\not\sim G_1$）。
Notes

Given $G_0\not\sim G_1$ , Verifier can generate the proof itself

Due to Verifier's randomness , Prover cannot generate the proof itself

Graph non-isomorphism Problem is not $NP$ , but can be solved by $IP$ .

Collision Problem

Definition
1. Given $h:\{0,1\}^n\to\{0,1\}^n$ , either $h$ is a permutation or $|Im(h)|\le 2^{n-1}$ .
2. Prover wants to convince Verifier that $h$ is a permutation .

Protocol 1

Global : Prover and Verifier already know $h$ . $\forall x\in \{0,1\}^n$ , Verifier can get $h(x)$ in poly-time .

Prover		Verifier
		$x\leftarrow \{0,1\}^n$
	<- $y$ --	$y:=h(x)$
Find $\tilde x$ , $h(\tilde x)=y$	-- $\tilde x$ ->
		$\begin{cases}1&x=\tilde x\\0&\text{otherwise}\end{cases}$

Analysis 1
1. Completeness : When $h$ is a permutation , $h$ is a injection , $x=\tilde x$ .
2. Soundness : When $h$ is not a permutation , then $|Im(h)|\le 2^{n-1}$ . \[ \forall x , P^*\ ,\ \Pr\{P^*(h(x))=x\}=\frac{1}{|h^{-1}(h(x))|} \] Therefore , \[ \begin{aligned} \Pr\{V\text{ accepts}\}&=\sum_{y\in Im(h)}\Pr\{y=f(x)|x\in \{0,1\}^n\}\Pr\{P^*(h(x))=x\}\\ &=\sum_{y\in Im(h)}\frac{|h^{-1}(y)|}{2^n}\frac{1}{|h^{-1}(y)|}\\ &=\frac{|Im(h)|}{2^n}\\ &\le \frac{1}{2} \end{aligned} \] $k$ rounds : $\Pr\{V \text{ accepts}\}\le\frac{1}{2^k}$ .
3. Zero-knowledge :
  
  Verifier itself knows $x,y$ . Prover tells Verifier $\tilde x$ .
  
  When $h$ is a permutation , $\tilde x=x$ , so Verifier can generate $\tilde x$ itself .
Protocol 2

Global : Prover and Verifier already know $h$ . $\forall x\in \{0,1\}^n$ , Verifier can get $h(x)$ in poly-time .

Prover Verifier

<- $y$ -- $y\leftarrow \{0,1\}^n$

Find $x$ , $h(x)=y$ -- $x$ ->

$\begin{cases}1&h(x)=y\\0&\text{otherwise}\end{cases}$
Analysis 2
1. Completeness : When $h$ is a permutation , $h$ is a bijection , $x$ always exists and unique . Always accept .
2. Soundness : When $h$ is not a permutation , $|Im(h)|\le 2^{n-1}$ . \[ \Pr\{h^{-1}(y)=\varnothing|y\leftarrow \{0,1\}^n\}=1-\frac{|Im(h)|}{2^n}\ge \frac{1}{2} \] When $h^{-1}(y)=\varnothing$ , any Prover cannot convince verifier , so \[ \Pr\{V\text{ accepts}\}\le 1-\Pr\{h^{-1}(y)=\varnothing|y\leftarrow \{0,1\}^n\}\le \frac{1}{2} \] $k$ rounds : $\Pr\{V \text{ accepts}\}\le\frac{1}{2^k}$ .
3. Zero-knowledge : NOT (dishonest-verifier) zero-knowledge
  
  $V$ knows $h^{-1}(y)$ , which cannot be computed in poly-time by itself .
  
  This is still honest-verifier zero-knowledge , see homework 1
Notes

In Protocol 1 , when $h$ is a permutation , Verifier can always generate a valid proof

In both Protocols , Prover must have the ability to solve $h^{-1}$ . This may lead Verifier knowing something more .

Prover		Verifier
	<- \(y\) --	\(y\leftarrow \{0,1\}^n\)
Find \(x\) , \(h(x)=y\)	-- \(x\) ->
		\(\begin{cases}1&h(x)=y\\0&\text{otherwise}\end{cases}\)

4 Formularize zero-knowledge IP

Security Parameter : $\kappa$
1. For efficiency : usually $|x|=poly(\kappa)$ , PPT should run in $poly(\kappa)$ .
2. For security : negligible function
Negligible function : $\epsilon$
1. Def : negligible function $\epsilon:\mathbb Z^*\to \mathbb R^*$
  
  For all polynomial $p$ , $\exists c\in \mathbb Z^* , \forall k>c,\epsilon(k)<\frac{1}{p(k)}$ .
2. Propositions :
  1. $\epsilon , \delta$ negligible $\to$ $\epsilon+\delta , \epsilon\delta$ negligible
  2. $\epsilon$ negligible $\to$ For all polynomial $p$ , $p\epsilon$ negligible
3. Conventions :
  1. $\epsilon$ noticeable : $\exists$ polynomial $p$ , $\exists c\in \mathbb Z^*,\forall k>c,\epsilon(k)\ge \frac{1}{p(k)}$
  2. $A$ happens with overwhelming probability : \[ \Pr\{A\}\ge 1-\epsilon \quad\quad \epsilon \text{ is negligible} \]
There exists function that is neither negligible nor noticeable
View of Verifier \[ View_V^P(x):=(x,r,\tau) \]
Honest-Verifier Zero-knowledge
1. Perfect honest-verifier zero-knowledge \[ \exists M\in PPT\ ,\ \forall x\in L\ ,\ View_V^P(x)\equiv M(x) \]
2. Statistical honest-verifier zero-knowledge
  
  The statistical distance between $View_V^P(x)$ and $M(x)$ is negligible
  
  $\exists M\in PPT\ ,\ \forall x\in L$ , \[ SD(View_V^P(x),M(x))=\frac{1}{2}\sum_{s}\left|\Pr\{View_V^P(x)=s\}-\Pr\{M(x)=s\}\right|<\epsilon \]
3. Computational honest-verifier zero-knowledge
  
  $\exists M\in PPT\ ,\ \forall x\in L\ , \ \forall$ distinguisher $D\in PPT$ , \[ \left|\Pr\{D(View_V^P(x))=1\}-\Pr\{D(M(x))=1\}\right|<\epsilon \]
Dishonest Verifier

$\braket{P,V}$ achieves perfect/statistical/computational dishonest-verifier zero-knowledge if :

$\forall V^*\in PPT\ , \ \exists$ expected poly-time randomized algorithm $M^*$ , $\forall x\in L$ , $View_{V^*}^P(x)$ and $M^*(x)$ are perfectly/statistically/computationally indistinguishable .

Graph Isomorphism IP with dishonest-verifier zero-knowledge

Definition

Prover and Verifier know graph $G_0,G_1$ .

Prover wants to convince Verifier that $G_0\sim G_1$ , i.e. $\exists \pi,\pi(G_0)=G_1$ .

Protocol

Prover		Verifier
$\pi_r\leftarrow S_n$
$\tilde G:=\pi_r(G_0)$	--$\tilde G$->
	<-$b$--	$b\leftarrow \{0,1\}$
find $\pi_b$ , s.t. $\tilde G=\pi_b(G_b)$	--$\pi_b$->
		$\begin{cases}1&\tilde G=\pi_b(G_b)\\0&\text{otherwise}\end{cases}$

Note : If Prover knows $\pi$ that $\pi(G_0)=G_1$ , then $\pi_b$ can be constructed : \[ \pi_b=\begin{cases}\pi_r&b=0\\\pi_r\circ\pi^{-1}&b=1\end{cases} \]

Analysis
1. Completeness : If $G_0\sim G_1$ , $\pi_b$ can be constructed as above . Always Accept .
2. Soundness : If $G_0\not\sim G_1$ , $\exists b^*\in \{0,1\},G_{b^*}\not\sim\tilde G$
  
  $\Pr\{V \text{ rejects}\}\ge \Pr\{V\text{ chooses }b^*\}=\frac{1}{2}$
  
  Note : we cannot let Verifier just choose $b=1$ , since a malicious Prover can violate the protocol , $\pi_r$ may not be a permutation , and $\tilde G$ may not isomorphic to $G_0$ .
3. honest-verifier zero-knowledge :
  
  Verifier itself knows : $G_0,G_1,b$ , $r$ : randomness generating $b$ . Prover tells verifier $\tilde G,\pi_b$ .
  
  $View_V^P=(G_0,G_1,r,b,\tilde G,\pi_b)$ .
  
  $M_V$ :
  1. sample $b\leftarrow \{0,1\}$
  2. choose $\pi_b\leftarrow S_n$
  3. $\tilde G:=\pi_b(G_b)$
  Since Prover and Verifier are honest , $b$ is independent of $G $ , and $\pi_b$ is generated by a uniformly random $\pi_r$ hence is also uniformly random .
4. dishonest-verifier zero-knowledge :
  
  Malicious Verifier can choose $b$ based on $\tilde G$ to gain more knowledge .
  
  $M^*$ : should perform as Prover :
  1. guess $b^*\in \{0,1\}$
  2. compute $\pi_r\leftarrow S_n$ , $\tilde G:=\pi_r(G_{b^*})$
  3. use Verifier to receive $b$
  4. If $b\neq b^*$ , go back to 1.
  5. If $b=b^*$ , then let $\pi_b=\pi_r$ , get the view

Prover		Verifier
		\(b\leftarrow \{0,1\}\) , \(\pi\leftarrow S_{\|V\|}\)
	<- \(\tilde G\) --	\(\tilde G:=\pi(G_b)\)
Find $b $ , \(G_{\tilde b}\sim \tilde G\)	-- \(\tilde b\) ->
		\(y=\begin{cases}1& \text{if }b=\tilde b\\0&\text{otherwise}\end{cases}\)

Prover		Verifier
		\(x\leftarrow \{0,1\}^n\)
	<- \(y\) --	\(y:=h(x)\)
Find \(\tilde x\) , \(h(\tilde x)=y\)	-- \(\tilde x\) ->
		\(\begin{cases}1&x=\tilde x\\0&\text{otherwise}\end{cases}\)

Prover		Verifier
\(\pi_r\leftarrow S_n\)
\(\tilde G:=\pi_r(G_0)\)	--\(\tilde G\)->
	<-\(b\)--	\(b\leftarrow \{0,1\}\)
find \(\pi_b\) , s.t. \(\tilde G=\pi_b(G_b)\)	--\(\pi_b\)->
		\(\begin{cases}1&\tilde G=\pi_b(G_b)\\0&\text{otherwise}\end{cases}\)