28、零知识证明系统相关研究

零知识证明系统相关研究

1. 零知识证明系统的矛盾推导

在零知识证明系统的研究中，我们定义了 $\varepsilon(n) \stackrel{\text{def}}{=} \frac{1}{Q(n) \cdot p(n)}$。通过对混合态 $H(j)$ 的分析，结合 $i$ 和 $i - 1$ 混合态的定义与平均论证，对于每个 $x$、$z$ 和 $i$，存在一个 $z’$，使得：
[
\left|
\Pr\left[
D\left(
x, z, M^{}_{Q(|x|) - i}(x, \langle P, V^{}(z’) \rangle(x))
\right) = 1
\right]
-
\Pr\left[
D\left(
x, z, M^{}_{Q(|x|) - i}(x, M^{}(x, z’))
\right) = 1
\right]
\right| > \varepsilon(|x|)
]
这几乎能推出我们想要的矛盾。但我们面临一个问题，即如何“知道” $i$ 和 $z$。为解决这个问题，我们利用了这样一个事实：$M^{}$ 的输出即使对于非均匀多项式规模电路，也应与 $V^{}$ 和 $P$ 的交互不可区分。因此，我们可以将 $i$ 和 $z$ 合并到一个新的辅助输入 $z’‘$ 中，其中 $z’$ 是 $z’‘$ 的前缀，且 $z’‘$ 对 $V^{}$ 和 $M^{}$ 看起来与 $