基于 MPC 的零知识证明协议

参考文献：

1. Jawurek, M., F. Kerschbaum, and C. Orlandi. 2013. “Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently”. In: ACM CCS 13: 20th Conference on Computer and Communications Security. Ed. by A.-R. Sadeghi, V. D. Gligor, and M. Yung. ACM Press. 955–966.
2. Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation[J]. Foundations and Trends® in Privacy and Security, 2018, 2(2-3): 70-246.
3. 应用密码学：协议、算法与C源程序（机工社大黑皮）

ZKP

零知识证明协议的基本定义在这篇文章。

交互式

最近看到了另一种描述 ZKP 的表述：

1. Verifier拥有一个困难问题实例 H 1H_1 H1​，Prover声明自己拥有 H 1H_1 H1​的解法 S 1S_1 S1​
2. Prover利用$1$个随机数$r$，将这个难题实例 H 1H_1 H1​，转变为另一个同构的难题实例 H 2H_2 H2​。同时，依据 S 1S_1 S1​和$r$，得到对应的解法 S 2S_2 S2​
3. Prover对解法 S 2S_2 S2​做承诺，然后将难题 H 2H_2 H2​和承诺值$c$都发送给Verifier
4. Verifier随机要求Prover给出如下两个声明之一的Proof：
   1. 要求Prover证明两个难题同构， H 1≅ H 2H_1 \cong H_2 H1​≅H2​
   2. 要求Prover公开 S 2S_2 S2​，并证明 S 2S_2 S2​是 H 2H_2 H2​的正确解法
5. Prover给出所要求的Proof，Verifier验证它
6. 两者反复执行$n$次 step 1 ~ step 5，直到Verifier相信Prover确实拥有 S 1S_1 S1​（一般而言，$n=10$就很好了）

完备性：诚实的Prover拥有 S1 S_1S1​，他总是可以给出 step 4 中所要求的两种Proof，因此Verifier最终会相信他。

可靠性：一个恶意的Prover，他没有 S1 S_1S1​，为了通过 step 4 的验证，他不得不猜测Verifier的选择。如果猜测Verifier会执行 step 4.1，那么敌手就在 step 2 中选择一个 H2≅ H1 H_2 \cong H_1H2​≅H1​，同时他不拥有对应的 S2 S_2S2​。如果猜测Verifier会执行 step 4.2，那么敌手就在 step 2 中随机生成一个难题 H2′ H_2′H2′​以及对应的解法 S2′ S_2′S2′​，但同时他无法证明 H1≅ H2′ H_1 \cong H_2′H1​≅H2′​。

零知识性：一个恶意的Verifier，他无法让第三方Alice相信上述 Proof 的有效性。假设敌手用一个摄像机记录协议的每一步，即使视频中显示Prover总是给出了正确的 Proof，Alice也总是可以质疑：每当Prover猜对了，Verifier就保留视频；每当Prover猜错了，Verifier就删除视频。人们无法区分真实记录（in the real world）和伪造记录（in the ideal world）！

人们已经证明：

1. 任何 NP 命题都包含一个 ZKP
2. 任何数学证明都能转化为一个 ZKP
3. 能使用交互式证明完成的任何事，也能用交互式 ZKP 完成

非交互式

上述的Alice不相信的原因是，她没有介入 ZKP 的交互。为了Prover为了让任何人相信他的Proof，他需要一个非交互式的ZKP。每当Prover发布Proof后，任何人都可以验证这个Proof是否有效（身份认证协议、签名协议）。

利用 Hash 函数$H$代替了 Verifier：

1. Prover声明自己拥有一个困难问题实例$H$的解法$S$
2. Prover利用$n$个随机数{ r i}\{r_i\} {ri​}，将这个难题实例$H$，转变为随机的$n$个同构的难题实例{ H i}\{H_i\} {Hi​}。同时，依据$S$和{ r i}\{r_i\} {ri​}，得到对应的解法{ S i}\{S_i\} {Si​}
3. Prover对解法{ S i}\{S_i\} {Si​}做承诺，然后将难题{ H i}\{H_i\} {Hi​}和承诺值{ c i}\{c_i\} {ci​}都公开
4. Prover计算b=H({ c i})b = H(\{c_i\}) b=H({ci​})，截取前$n$比特$b=b[1:n]$，然后依据$b[i]\in \{0,1\}$给出如下两个声明之一的Proof：
   1. 当$b[i]=0$，Prover证明两个难题同构，H≅ H iH \cong H_i H≅Hi​
   2. 当$b[i]=1$，Prover公开 S iS_i Si​，并证明 S iS_i Si​是 H iH_i Hi​的正确解法
5. Prover公布 step 4 中的$n$个Proof，任何人都可以验证它：先根据{ c i}\{c_i\} {ci​}计算出$b$，然后依次检查第$i$个Proof是否是关于$b[i]$声明的合法证明。

这儿的$H$扮演了无偏随机比特发生器的角色。如果恶意Prover不拥有$S$，那么他最多只能给出 step 4 中的某一个Proof，而不能同时都给出Proof，因此为了欺骗，他必须能够预测$H$的输出。

当然，是Prover（而非Verifier）来挑选的$b$，因此敌手完全可以随机猜测$b$的前$n$位，然后尝试不同的 { Si}\{S_i\}{Si​}组合，直到全部猜对$n$个比特。此时，敌手就可以给出一个合法的 Proof 了。为了抵挡敌手的穷举攻击，我们需要将$n$设置的比较大，例如$64,128$

JKO（2013）

ZKP 可以作为一种特殊的 malicious secure computation，根据声明$y$构造电路$C(\cdot ,y)$（$C(x,y)=1⟺(x,y)\in R$），其中作为Prover的一方输入证据$x$，作为Verifier的一方什么也不输入，最后电路结果$C(x,y)$输出给Prover。

很明显，利用任意的 cut-and-choose-based 2PC protocol，总是可以实现上述的恶意敌手安全的两方计算。但是，直接使用 C&C 技术的 2PC 协议，对应的混淆电路过于巨大。

Jawurek, Kerschbaum 和 Orlandi 观察到：由于 Verifier 没有输入，因此如果让他来生成 GC，那么这个 GC 可以同时用来 checking 和 evaluation：翻转角色，我们让 Verifier 生成一个Yao’s Garbled Circuit，在打开后 Prover 虽然能观察到全部的 label，理论上可以获得 Verifier 的任意明文输入比特，但是奈何 Verifier 根本就没有隐私输入。因此，只需要令重复因子为$\rho =1$，C&C 技术下的混淆电路规模大幅减小。

JKO协议如下：

1. Verifier P 1P_1 P1​ 生成$C(\cdot ,y)$的$1$个混淆电路 GC，发送给 Prover P 2P_2 P2​
2. P 2P_2 P2​ 利用 OT 协议获得 $x$ 对应的混淆输入，计算电路得到证明结果$v\in \{0,1\}$的混淆输出 k outvk_{out}^v koutv​
3. P 2P_2 P2​对 k outvk_{out}^v koutv​做承诺，只将承诺值c=commit( k outv,r)c = commit(k_{out}^v,r) c=commit(koutv​,r)发送给 P 1P_1 P1​
4. 接收到$c$后， P 1P_1 P1​打开 GC， P 2P_2 P2​检查它是否正确，
   1. 如果电路正确，那么 P 2P_2 P2​发送( k outv,r)=decommit(c)(k_{out}^v,r) = decommit(c) (koutv​,r)=decommit(c)给 P 1P_1 P1​
   2. 如果电路错误，那么 P 2P_2 P2​终止协议（发现恶意Verifier）
5. P 1P_1 P1​验证解承诺是否合法，
   1. 如果合法， P 1P_1 P1​输出标签 k outvk_{out}^v koutv​对应的明文输出$v$（当$v=1$时， P 1P_1 P1​相信 P 2P_2 P2​证明了$(x,y)\in R$）
   2. 如果非法， P 1P_1 P1​输出$0$（发现恶意Prover）

明显上述的非交互式 ZKP 协议是完备的。下面讨论其安全性：

1. secure against a cheating verifier（可靠性）：在 Verifier 打开 GC 之前，Prover 已经对输出结果做了承诺，因此恶意的Prover难以在不知道$x$的情况下计算出 k out1k_{out}^1 kout1​
2. secure against a cheating prover（零知识性）：只有当 Prover 验证这个 GC 确实是电路$C(\cdot ,y)$ 的正确的混淆版本之后，才会揭露最终计算结果 k outvk_{out}^v koutv​，因此 Verifier 无法利用错误的电路来学习到关于$x$的任何信息。