基于 MPC 的零知识证明协议

参考文献：

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.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.应用密码学：协议、算法与C源程序（机工社大黑皮） ZKP

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

交互式

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

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

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

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

人们已经证明：

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

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

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

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

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

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

JKO（2013）

ZKP 可以作为一种特殊的 malicious secure computation，根据声明 y y y构造电路 C ( ⋅ , y ) C(\cdot,y) C(⋅,y)（ C ( x , y ) = 1    ⟺    ( x , y ) ∈ R C(x,y)=1 \iff (x,y) \in R C(x,y)=1⟺(x,y)∈R），其中作为Prover的一方输入证据 x x x，作为Verifier的一方什么也不输入，最后电路结果 C ( x , y ) C(x,y) 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 根本就没有隐私输入。因此，只需要令重复因子为 ρ = 1 \rho=1 ρ=1，C&C 技术下的混淆电路规模大幅减小。

JKO协议如下：

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

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

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