27、零知识证明：定义与顺序组合

零知识证明：定义与顺序组合

1. 零知识证明基础回顾

在之前的零知识证明定义中，虽保证了在与证明者就任何共同输入进行交互后能有效计算的内容，也可从输入本身有效计算得出。但在实际应用里，比如交互式证明作为更大协议的子协议时，验证者与证明者就共同输入 (x) 交互时，可能拥有额外的先验信息 (z)，这可能协助验证者从证明者处“提取知识”，尤其当 (z) 与 (x) 相关时，这种风险更显著。

2. 带辅助输入的零知识证明

2.1 定义引入

为满足实际应用需求，对零知识证明定义进行了修改。设 ((P, V)) 是语言 (L) 的交互式证明，(P_L(x)) 是满足关于 (x \in L) 的完备性条件的字符串 (y) 的集合。若对于每个概率多项式时间交互式机器 (V^)，都存在一个概率算法 (M^)，其运行时间是关于第一个输入长度的多项式，使得以下两个集合在计算上不可区分（将区分差距视为 (|x|) 的函数），则称 ((P, V)) 关于辅助输入是零知识的（或辅助输入零知识）：
- ({\langle P(y_x), V^(z) \rangle(x)}_{x \in L, z \in {0, 1}^})，其中 (y_x) 是 (P_L(x)) 中的任意元素。
- ({M^(x, z)}_{x \in L, z \in {0, 1}^})

即对于每个运行时间是关于第一个输入长度的多项式的概率算法 (D)，每个多项式 (p(\cdot))，以及所有足够长的 (x \in L)，所有 (y \in P_L(x)) 和 (z \in {0, 1}^ <