38、零知识证明系统：原理、应用与发展

零知识证明系统：原理、应用与发展

1. 多证明者零知识证明

多证明者零知识证明在特定场景下具有独特的优势，它允许“证明实体”被拆分为两个或多个部分，并且在证明过程中各部分相互不知情。在这种情况下，无需依赖复杂性理论假设就能实现完美零知识证明，而是将广泛认可的难解性假设替换为与证明过程所处特定环境相关的物理假设。

在多证明者零知识证明中，对于承诺阶段的计算，通过设置 ( s_i = \pi^{-1}{r_i}(c_i) )（或 ( s_i = \pi^{-1}{r_i}(c_i - 1) )）来计算 ( s_i )。需要注意的是，接收者在承诺阶段的视图等同于验证者与第一个证明者交换的消息，这些消息是在第一步生成的。同时，模拟器的消息分布与实际交互中证明者的消息分布相同，只是生成方式有所不同。在实际交互中，( s_i ) 在集合 ({1, 2, 3}) 中均匀选择，并与 ( r_i ) 和随机排列的着色一起确定 ( c_i )；而在模拟中，( c_i ) 在集合 ({1, 2, 3}) 中均匀选择，并与 ( r_i ) 和集合 ({1, 2, 3}) 中的随机对一起确定揭示的 ( s_i )。

该论证可以轻松扩展到协议的多项式多个实例同时执行的情况。由此得出定理：每个 NP 语言都有一个完美零知识双证明者证明系统。这个证明系统具有以下特性：
-单轮通信：验证者向两个证明者分别发送一条消息，证明者再分别回复一条消息。
-可靠性误差指数级消失：证明系统的可靠性误差会随着协议执行次数的增加而指数级减小。
-证明者策略可由概率多项式时间机器实