40、零知识证明系统的深入探讨

零知识证明系统的深入探讨

1. 非交互式零知识证明

非交互式零知识证明结合了两个重要观察结果，且依赖于证明者（P）的高效实现。
-观察一：真实执行和模拟器输出中，公共参考字符串的分布确实有很大差异。但由于生成器（G）的伪随机性，这种差异在计算上是不可区分的。因此，真实执行中验证者的视图与公共参考字符串按模拟方式选择（但证明者按特定构造行动）时验证者的视图在计算上不可区分。
-观察二：证明者（P）的零知识属性意味着它是见证不可区分的。所以，无法区分证明者使用语言L中x的见证和使用伪随机序列p的种子作为见证这两种情况，且在多项式次数重复证明过程时同样成立。

通过混合论证证明零知识声明，中间混合情况是在模拟器生成的伪随机参考字符串上执行证明者策略，而非真正的随机参考字符串。这两个观察表明，中间混合情况与两个极端混合情况在计算上不可区分。

基于相关定理和命题，我们得到：假设陷门置换族存在，NP中的每种语言都有一个无界零知识非交互式证明系统，且证明者可以由一个以NP见证作为辅助输入的概率多项式时间机器实现。

2. 自适应零知识

之前的定义是非自适应的，涉及健全性和零知识条件。在自适应情况下，公共输入在公共参考字符串固定后由对手选择。

2.1 自适应健全性

对于非交互式证明系统（P，V），若对于每个n和每对函数 # : {0, 1}^poly(n) → ({0, 1}^n \ L) 和 : {0, 1}^poly(n) → {0, 1}^poly(n)，有 Pr [V (#(R), R, (R)) =