26、零知识证明系统详解

零知识证明系统详解

1. 多项式时间相关概念探讨

在探讨零知识证明系统时，对于概率多项式时间算法转换为严格多项式时间算法的做法，在当前情境下并不合适。我们倾向于采用特定的定义（类似定义4.3.1 ），而非另一种定义（类似定义4.3.6 ），主要是为了避免使用期望多项式时间的概念。

期望多项式时间的简单解释是平均运行时间受输入长度的多项式所限制。但这个定义存在不足，它在归约操作下不封闭，且过于依赖具体的机器。例如，有一个函数 (f(x)) ，当 (x \in {0}^*) 时，(f(x) = 2^{|x|}) ；否则 (f(x) = |x|^2) 。该函数满足 (E[f(U_n)] < n^2 + 1) ，但 (E[f(U_n)^2] > 2^n) 。这说明一个函数的平均值受多项式限制，但其平方后的函数可能不再受多项式限制。

因此，更好的期望多项式时间解释是，运行时间受一个平均线性增长率的函数的多项式所限制。也就是说，如果存在一个多项式 (p) 和一个平均线性函数 (\ell) ，使得对于足够长的 (x) ，都有 (f(x) \leq p(\ell(x))) ，那么我们称 (f) 是平均多项式的。需要注意的是，如果 (f) 是平均多项式的，那么 (f^2) 也是。

在计算零知识的讨论中也有类似情况。定义4.3.2要求模拟器在多项式时间内工作，而更宽松的概念会允许其在期望多项式时间内工作。为了使定义更加优雅，通常会对允许期望多项式时间模拟器的定义进行修改，要求对于期望多项式时间验证者与证明者的交互，也存在这样的模拟器。

2. 诚实验证者零知识

这里简要讨论一种较弱的零知识概念——诚实验证者零知识。该概念只要求