安全多方计算之五：零知识证明（从入门到入土。。）

1. 简介

零知识证明（Zero Knowledge Proof）由S.Goldwasser、S.Micali 及 C.Rackoff于1985年在论文《The Knowledge Complexity of Interactive Proof Systems》（交互式证明系统中的知识复杂性）首次提出，是一种用于证明者在不泄露任何其他信息的情况下证明其掌握知识正确性的密码学协议。

该协议的一方称为证明者（Prover），用P PP表示；另一方称为验证者（Verifier），用V VV表示。零知识证明指P PP试图使V VV相信某个论断是正确的，但却不向V VV泄露任何有用的信息，即P PP在论证的过程中V VV得不到任何有用的信息。零知识证明除了证明证明者论断的正确性外不泄露任何其他信息或知识。

零知识证明一般包含以下阶段：

• 承诺（Commit）：证明者针对命题做出承诺，该承诺等待验证者提出挑战并进行验证。
  
• 挑战（Challenge）：验证者选择随机数（即上述例子中的行、列或格）对提出的承诺进行挑战。
  
• 回应挑战（Response）：证明者将收到的随机数结合给出的承诺（承诺不可修改），返回挑战的回应。
  
• 验证（Verify）：验证者验证挑战的回应是否正确，如果错误，则证明失败。
  

证明者与验证者重复执行以上步骤，直到可以相信的概率达到验证者接受的条件，证明成功。

零知识证明具有以下特点：

• 完备性（Completeness）：如果证明者和验证者都是诚实的，并遵守证明过程的每一步进行正确的计算，则该证明一定会成功，验证者也一定能够接受证明者；
• 合理性（Soundness）：没有人能够假冒证明者，从而使这个证明成功；
• 零知识性（Zero-Knowledge）：证明过程执行完后，验证者只会得悉"证明者拥有这项知识"，而没有获得关于这项知识本身的任何信息。

零知识证明与比特承诺都要求协议参与者对某种知识或某个声明做出证明或承诺，但不泄露该知识或承诺的任何信息。不同的是比特承诺需要在打开阶段揭示承诺，但零知识证明在证明过程结束后仍不会泄露掌握的知识。比特承诺一般用于在电子拍卖或电子投票中参与者对自己的投票或选票做出承诺；而在协议执行过程中，为了抵抗恶意参与者或主动攻击者，需要协议参与者通过零知识证明来证明自己所作操作都是按照协议正确执行的。

2. 零知识证明的例子

2.1 向红绿色盲证明红球、绿球

有两颗形状、大小完全一样的球：一颗红球、一颗绿球，X XX是红绿色盲，Y YY能够向X XX证明这两颗球是一红一绿吗？

• X XX左手拿着红球，右手拿着绿球，并在背后不让Y YY看到，进行交换（或者不交换）两只球
• Y YY能够根据颜色精准判断X XX是否进行了交换
• 执行上述操作N NN次后，即能在X XX是色盲的情况下，Y YY仍能够向X XX证明能这两颗球是一红一绿

2.2 数独的零知识证明

数独（Sudoku）规则如下：

9 × 9 9\times 99×9方格，其中已经填入部分数字，要求玩家在空白方格中填入数字1 − 9 1-91−9，使得完成后的每行、每列及9 99个3 × 3 3\times33×3方格都包含数字1 − 9 1-91−9且每个数字只出现一次

假设P PP给出一道数独题目，由V VV来完成，但V VV过了很久都未能解出，他怀疑该数独题目没有解，要求P PP证明该题目有解。因此P PP希望在不告诉V VV答案相关的任何信息的情况下证明这道题有解且自己知道这个解。

P PP和V VV执行以下操作：

（1）承诺

P PP将答案的每个数字写在纸片上，并按照答案摆放(正面朝下)，题目中已有的数字正面朝上，这81个纸片的放置为P PP的“承诺”。

（2）挑战

V VV不能直接将纸片翻转查看数字，但是 V VV可以在行、列、格中任意指定一种验证方式。如图所示，V VV选择按照行的方式进行挑战。

（3）挑战回应

P PP按照V VV选择行验证方式将桌面上每行的9 99张卡片装入一个袋子里，并且将纸片进行混淆后，把袋子交给V VV，作为挑战的回应。

（4）验证

V VV打开纸袋可验证每个纸袋里的9 99张纸片刚好为1 − 9 1-91−9，即P PP在承诺阶段做出的承诺满足“每行1 − 9 1-91−9都出现且只出现一次”的要求，同时在一定程度上说明P PP做出的承诺很可能是一个合法的解（因为随意给出的数字不会满足这一要求，并且在承诺的时候并不知道V VV会选择行、列、格哪种验证方式）。

由于存在1 / 3 1/31/3的概率P PP事先猜对V VV选择行验证，然后给出的承诺仅满足行要求，不满足列要求和格要求。或者P PP拥有满足两项要求，但是不满足第三项要求的错误答案，此时猜对的概率为 2 / 3 2/32/3。

但P PP为了向V VV证明自己知道该数独的解，会和V VV重复该方案的承诺、挑战、回应挑战和验证，允许V VV在挑战阶段任意选择验证方式，如果出现任何一次验证错误则表示证明失败。

假设进行的n nn次过程都验证成功，那么P PP在不知道数独答案的条件下单次验证成功的概率最大为2 / 3 2/32/3（考虑 P PP 满足两项要求，但是不满足第三项要求的错误答案），所有验证都成功的概率为 ( 2 3 ) n (\frac{2}{3})^n(32)n随着n nn的增大，这一概率趋近于0 00，而 P PP拥有正确答案的概率趋近于 1 11，表明 V VV 可以以大概率相信 P PP 拥有正确答案。

2.3 三染色问题的零知识证明

地图三染色问题：如何用三种颜色染色一个地图，保证任意两个相邻的地区都是不同的颜色。

该问题可转变成连通图的顶点三染色问题，即不同城市（节点）之间修建了一些道路（边），是否存在一种染色方式，使得每个城市都用特定的三种颜色之一表示，并且任意有道路相连的两个城市都不是相同颜色。

如图所示，证明者Alice拥有一个特地地图三染色的方案，希望在不泄漏任何信息的条件下向Bob证明自己拥有该方案。

（1）承诺

Alice将染色方案进行置换（蓝色->绿色，绿色->橙色，橙色->蓝色），然后将每个节点装入一个信封里，放在桌子上出示给Bob。

（2）挑战

Bob可以选择任意一条连边，要求Alice打开相邻两个节点的信封进行验证。

（3）回应挑战

Alice打开Bob指定的两个节点，作为对挑战的回应。

（4）验证

Bob验证结果：两节点颜色不同

重复以上过程

当重复交互很多次之后，Bob 得到了大量的信息，但没有得到关于染色方案的任何知识，却能够相信Alice拥有该方案。

2.4 Quisquater-Guillou 零知识协议

1990年，LouisC.Guillou 和 Jean-Jacques Quisquater 提出一种形象的基本零知证明协议的例子，该图表示一个迷宫，C CC与D DD之间有一道门，需知道秘密咒语才能打开。现在，证明者P PP希望向验证者V VV证明他拥有这道门的秘密语，但是P PP不愿意向 V VV泄露该咒语。P PP采用“分割与选择”（Cut-and-Choose）技术实现这一零知识协议。

• (1)验证者V VV开始停留在位置A AA
• (2)证明者P PP一直走到迷宫的深处，随机选择到位置C CC或位置D DD
• (3)V VV看不到P PP后，走到位置B BB，然后命令P PP从某个出口返回B BB;
• (4)P PP服从V VV的命令，要么原路返回至位置 B BB，要么使用秘密咒语打开门后到达位置B BB

上述协议中，若P PP不知道秘密咒语，就只能原路返回，而P PP第一次猜对V VV要求他一条路径的概率为0.5 0.50.5，第一轮协议P PP能够欺骗V VV的概率为0.5 0.50.5。

P PP和V VV重复上述步骤n nn次，P PP成功欺骗V VV的概率为1 / 2 n 1/2^n1/2n。假定n = 20 n=20n=20，则P PP成功欺骗V VV的概率为1 / 1048576 1/10485761/1048576，如果P PP能够20 2020 次按V VV的要求返回，V VV即证明P PP确实知道秘密咒语。同时，V VV无法从上证明过程中获取任何关于P PP的秘密咒语的信息。

3. ElGamal加密的零知识证明

3.1 ElGamal加密的已知明文证明

对于 ElGamal加密方案的密文E ( M ) = ( α , β ) = ( g r , y r M ) E(M)=(\alpha, \beta)=\left(g^{r}, y^{r} M\right)E(M)=(α,β)=(gr,yrM) , 如果一个参与者知道了r rr, 则可非常方便地利用零知识证明来证明自己知道密文( α , β ) (\alpha, \beta)(α,β) 所对应的明文 M , 这就是已知明文证明。

Schonorr提出参与者能够使用零知识证明的方法俩证明他知道一个r rr 使得α = g r \alpha=g^{r}α=gr 成立, 方法如下:

• 步骤1: Alice 选择随机数z zz 发送 a ′ = g z a^{\prime}=g^{z}a′=gz 至 Bob。
• 步骤2: Bob 选择随机数 c cc 发送至 Alice。
• 步骤3: Alice 发送 k = ( z + c r )   m o d   q k=(z+c r) \bmod qk=(z+cr)modq 至 Bob。
• 步骤4: Bob 验证 g k = a ′ α c g^{k}=a^{\prime} \alpha^{c}gk=a′αc 。

3.2 ElGamal加密的二选一零知识证明

Cramer 提出, Alice 对消息M MM 的 ElGamal 加密( α , β ) = ( g r   m o d   p , y r M   m o d   p ) (\alpha, \beta)=\left(g^{r} \bmod p, y^{r} M \bmod p\right)(α,β)=(grmodp,yrMmodp)在不泄露 M MM 的前提下, 可以向其他人证明 M = 1 M=1M=1 或 M = Z M=ZM=Z, 步骤如下:

步骤 1 :

• 若M = 1 M=1M=1 , Alice 选择随机数 r 1 , d 1 , w r_{1}, d_{1}, wr1,d1,w , 发送( α , β ) , a 1 = g r 1 α d 1 , b 1 = y r 1 ( β z ) d 1 , a 2 = g w , b 2 = y w (\alpha, \beta), a_{1}=g^{r_1} \alpha^{d_{1}}, b_{1}= y^{r_{1}}\left(\frac{\beta}{z}\right)^{d_{1}}, a_{2}=g^{w}, b_{2}=y^{w}(α,β),a1=gr1αd1,b1=yr1(zβ)d1,a2=gw,b2=yw至 Bob;
  
• 若M = Z M=ZM=Z , Alice 选择随机数 r 2 , d 2 , w r_{2}, d_{2}, wr2,d2,w, 发送( α , β ) , a 1 = g w , b 1 = y w , a 2 = g r 2 α d 2 , b 2 = y r 2 β d 2 (\alpha, \beta), a_{1}= g^{w}, b_{1}=y^{w}, a_{2}=g^{r_{2}} \alpha^{d_{2}}, b_{2}=y^{r_{2}} \beta^{d_{2}}(α,β),a1=gw,b1=yw,a2=gr2αd2,b2=yr2βd2至 Bob。
  

步骤 2: Bob 发送随机数c cc 至 Alice。

步骤 3:

• 若M = 1 M=1M=1 , Alice 发送d 1 , d 2 = ( c − d 1 )   m o d   p , r 1 , r 2 = ( w − r d 2 )   m o d   p d_{1}, d_{2}=\left(c-d_{1}\right) \bmod p, r_{1}, r_{2}=\left(w-r d_{2}\right) \bmod pd1,d2=(c−d1)modp,r1,r2=(w−rd2)modp至 Bob;
  
• 若M = Z M=ZM=Z , Alice 发送d 1 = ( c − d 2 )   m o d   p , d 2 , r 1 = ( w − r d 1 )   m o d   p , r 2 d_{1}=\left(c-d_{2}\right) \bmod p, d_{2}, r_{1=}\left(w-r d_{1}\right) \bmod p, r_{2}d1=(c−d2)modp,d2,r1=(w−rd1)modp,r2至 Bob。
  

步骤 4: Bob 验证c = ( d 1 + d 2 )   m o d   p , a 1 = g r 1 α d 1 , b 1 = y r 1 ( β z ) d 1 , a 2 = g r 2 α d 2 , b 2 = y r 2 β d 2 c=(d_{1}+d_{2})\bmod p, a_{1}=g^{r_{1}} \alpha^{d_{1}}, b_{1}=y^{r_{1}}\left(\frac{\beta}{z}\right)^{d_{1}}, a_{2}=g^{r_{2}} \alpha^{d_{2}}, b_{2}= y^{r_{2}} \beta^{d_{2}}c=(d1+d2)modp,a1=gr1αd1,b1=yr1(zβ)d1,a2=gr2αd2,b2=yr2βd2

3.3 ElGamal加密的1-out-of-N零知识证明

Alice 对消息m mm 的 ElGamal 加密( α , β ) = ( g r   m o d   p , y r m   m o d   p ) (\alpha, \beta)=\left(g^{r} \bmod p, y^{r} m \bmod p\right)(α,β)=(grmodp,yrmmodp)

M = ( m 1 , m 2 , … , m N ) M= \left(m_{1}, m_{2}, \ldots, m_{N}\right)M=(m1,m2,…,mN) 为明文集合 。m = m t , t ∈ [ 1 , N ] m=m_{t}, t \in[1, N]m=mt,t∈[1,N]，可以在不泄露m mm的情况下， 证明m ∈ M m \in Mm∈M 。

假设 M MM 对应的其 ElGamal 加密的密文集合为( ( α 1 , β 1 ) , ( α 2 , β 2 ) , … , ( α N ′ β N ) ) \left(\left(\alpha_{1}, \beta_{1}\right),\left(\alpha_{2}, \beta_{2}\right), \ldots,\left(\alpha_{N^{\prime}} \beta_{N}\right)\right)((α1,β1),(α2,β2),…,(αN′βN))其中( α i ′ β i ) = ( g k i   m o d   p , y k i m i   m o d   p ) \left(\alpha_{i^{\prime}} \beta_{i}\right)= \left(g^{k_{i}} \bmod p, y^{k_{i}} m_{i} \bmod p\right)(αi′βi)=(gkimodp,ykimimodp)

步骤 1:

Alice 选择随机数d 1 , d 2 , … , d N , r 1 , r 2 , … , r N d_{1}, d_{2}, \ldots, d_{N}, r_{1}, r_{2}, \ldots, r_{N}d1,d2,…,dN,r1,r2,…,rN , 计算

a i = ( α i α ) d i ⋅ g r i , b i = ( β i β ) d i ⋅ y r i , i = 1 , … , N , i ≠ t . a_{i}=\left(\frac{\alpha_{i}}{\alpha}\right)^{d_{i}} \cdot g^{r_{i}}, \quad b_{i}=\left(\frac{\beta_{i}}{\beta}\right)^{d_{i}} \cdot y^{r_{i}}, \quad i=1, \ldots, N,i \neq t .ai=(ααi)di⋅gri,bi=(ββi)di⋅yri,i=1,…,N,i=t.

a t = g w , b t = y w a_{t}=g^{w}, b_{t}=y^{w}at=gw,bt=yw, 其中 w = ( k t − r ) d t + r t w=\left(k_{t}-r\right) d_{t}+r_{t}w=(kt−r)dt+rt，并将( a i b i ) , i = 1 , … , N \left(a_{i} b_{i}\right), i=1, \ldots, N(aibi),i=1,…,N发送至 Bob。

步骤 2: Bob 发送随机数 c cc 至 Alice。

步骤 3: Alice 修改d t d_{t}dt 与 r t r_{t}rt , 使得c = ∑ i = 1 N d i , w = ( k t − r ) d t + r t c=\sum_{i=1}^{N} d_{i}, w=\left(k_{t}-r\right) d_{t}+r_{t}c=i=1∑Ndi,w=(kt−r)dt+rt

然后将 d 1 , d 2 , … , d N , r 1 , r 2 , … , r N d_{1}, d_{2}, \ldots, d_{N}, r_{1}, r_{2}, \ldots, r_{N}d1,d2,…,dN,r1,r2,…,rN 发送至 Bob。

步骤 4: Bob 验证c = ∑ i = 1 N d i , a i = ( α i α ) d i ⋅ g r i , b i = ( β i β ) d i ⋅ y r i , i = 1 , … , N c=\sum_{i=1}^{N} d_{i}, \quad a_{i}=\left(\frac{\alpha_{i}}{\alpha}\right)^{d_{i}} \cdot g^{r_{i}}, \quad b_{i}=\left(\frac{\beta_{i}}{\beta}\right)^{d_{i}} \cdot y^{r_{i}}, \quad i= 1, \ldots, Nc=i=1∑Ndi,ai=(ααi)di⋅gri,bi=(ββi)di⋅yri,i=1,…,N

4. 身份的零知识证明

一个安全的身份识别协议至少应满足以下两个条件:

• 证明者P PP能够向验证者V VV证明他的确是P PP;
• 在证明者P PP向验证者V VV证明他的身份后，验证者V VV不能获得关于P PP的任何有用信息，使得V VV不能冒充P PP向第三方证明V VV是P PP。

也就是说，P PP既能向V VV证明他的身份，又没有向V VV泄露P PP的识别信息，即安全的身份识别协议应满足零知识性和认证性。

4.1 Schnorr身份识别协议

Schnorr利用离散对数的零知识证明，设计了一个身份鉴别协议。

选择两个大素数p 、 q p、qp、q，q qq是p − 1 p-1p−1的大素因子，然后选择一个生成元g ∈ Z p ∗ g \in Z_p^*g∈Zp∗，选择随机数x , 1 < x < q x,1x,1<x<q，计算y ≡ g x   m o d   p y\equiv g^x \bmod py≡gxmodp，则私钥为x xx，公钥为( y , g , p , q ) (y,g,p,q)(y,g,p,q)。

证明者Alice能够使用零知识证明的方法向验证者Bob证明她知道一个x xx，使得y ≡ g x   m o d   p y\equiv g^x \bmod py≡gxmodp

协议描述

• 步骤1: Alice 选择随机数k , 0 ≤ k ≤ q − 1 k,0\leq k \leq q-1k,0≤k≤q−1 发送 z ≡ g k   m o d   p z\equiv g^{k} \bmod pz≡gkmodp 至 Bob。
• 步骤2: Bob 选择随机数 c , 1 ≤ c ≤ 2 t ( t ≤ ∣ q ∣ ) c,1 \leq c \leq 2^t(t \leq |q|)c,1≤c≤2t(t≤∣q∣) 发送至 Alice。
• 步骤3: Alice 计算 s ≡ ( k + c x )   m o d   q s\equiv (k+cx) \bmod qs≡(k+cx)modq 至 Bob。
• 步骤4: Bob 验证 g s ≡ z y c   m o d   q g^{s}\equiv zy^{c} \bmod qgs≡zycmodq 。

协议说明

g s = g k g c x = z ( g x ) c = z y c g^{s}= g^{k}g^{cx} = z(g^{x})^c = zy^{c}gs=gkgcx=z(gx)c=zyc

4.2 Fiat-Shamir 身份识别协议

1986 年，A. Fiat与A. Shamir 提出了一种基于二次剩余根的身份识别协议，即Fiat-Shamir 身份识别协议。

1988 年，U.Feige、A.Fiat和 A.Shamir 把 Fiat-Shamir 身份识别协议改进为零知识证明的身份识别协议，即Feige-Fiat-Shamir身份识别协议，简称 F.F.S协议。该协议把“分割与选择”和“挑战与应答”的思想结合起来，其目的是证明者P PP向验证者V VV证明他的身份，且事后V VV不能冒充P PP。

协议描述

假定存在一个可信任的中心TA，该中心的唯一任务是选择形式为4 r + 3 4r+34r+3的两个大素数p 、 q p、qp、q，使得n = p × q n = p \times qn=p×q是难分解的，然后向其他人公布n nn(n nn为Blum 数)。TA任务完成后可被关闭或取消，因为它不再有其他的任务，但该中心不能泄露p 、 q p、qp、q的信息。

证明者P PP的秘密身份由k kk个数x 1 , . . . , x i , . . . , x k x_1,...,x_i,...,x_kx1,...,xi,...,xk表示，其中1 ≤ x i < n , i = 1 , 2 , . . . , k 1 \le x_i1≤xi<n,i=1,2,...,kP PP的公开身份由其他k kk个数y 1 , . . . , y i , . . . , y k y_1,...,y_i,...,y_ky1,...,yi,...,yk来表示，其中y i y_iyi也满足1 ≤ y i < n , i = 1 , 2 , . . . , k 1 \le y_i1≤yi<n,i=1,2,...,k且x i x_ixi和y yy满足:y i x i 2 ≡ ± 1   m o d   n , i = 1 , 2 , . . . , k y_ix_i^2 \equiv \pm1 \bmod n, i= 1,2,...,kyixi2≡±1modn,i=1,2,...,k初始状态下验证者V VV知道TA公布的Blum数n nn和证明者P PP的公开身份y 1 , . . . , y i , . . . , y k y_1,...,y_i,...,y_ky1,...,yi,...,yk，现在P PP希望向V VV证明他知道他自己的秘密身份。协议执行的步骤如下:

• P PP随机选择一个整数a aa，计算r ≡ ± a 2   m o d   n r \equiv \pm a^2 \bmod nr≡±a2modn并把其中一个值发送给V VV;
  
• V VV从1 , 2 , … , k {1,2,…,k}1,2,…,k中选择一子集e = { e 1 , e 2 , . . . , e j } e=\{e_1,e_2,...,e_j\}e={e1,e2,...,ej}，然后将e ee交给P PP;
  
• P PP计算出T x ≡ ∏ i = 1 j x e i   m o d   n T_x \equiv \prod_{i=1}^{j} x_{e_i} \bmod nTx≡∏i=1jxeimodn，并将b ≡ a T x   m o d   n b \equiv aT_x \bmod nb≡aTxmodn交给V VV;
  
• V VV计算出T y ≡ ∏ i = 1 j y e i   m o d   n T_y \equiv \prod_{i=1}^{j} y_{e_i} \bmod nTy≡∏i=1jyeimodn，并验证r ≡ ± b 2 T y   m o d   n r \equiv \pm b^2 T_y \bmod nr≡±b2Tymodn 是否成立;
  

若验证通过，则重复执行上述步骤；否则拒绝。