零知识证明系统中的完美隐藏承诺方案及相关应用
在密码学和计算理论中，零知识证明系统是一个重要的研究领域，它允许一方（证明者）向另一方（验证者）证明某个陈述是真实的，而不透露除了陈述本身真实性之外的任何额外信息。本文将深入探讨零知识证明系统中的完美隐藏承诺方案，以及如何利用这些方案构建针对 NP 语言的完美零知识论证。
1. 零知识证明系统的基本条件
对于一种语言 L，如果两个机器（证明者 P 和验证者 V）在多项式时间内运行（带有辅助输入），并且满足以下两个条件，那么就构成了一个零知识证明系统（或论证）：
-完整性（Completeness）：对于每一个属于语言 L 的元素 x，存在一个字符串 y，使得对于每一个字符串 z，证明者 P(y) 和验证者 V(z) 针对输入 x 进行交互后，验证者接受的概率至少为 2/3，即 Pr [⟨P(y), V (z)⟩(x) = 1] ≥ 2/3。
-计算可靠性（Computational soundness）：对于每一个多项式时间交互机器 B，以及所有足够长的不属于语言 L 的元素 x，和任意的字符串 y 和 z，机器 B(y) 与验证者 V(z) 针对输入 x 进行交互后，验证者接受的概率至多为 1/3，即 Pr [⟨B(y), V (z)⟩(x) = 1] ≤ 1/3。
通常情况下，通过足够多次地顺序重复该协议，可以将完整性和可靠性条件中的错误概率从 1/3 降低到 2^(-poly(|x|))。不过需要注意的是，在某些情况下，并行重复可能无法降低计算可靠性的错误概率。
