零知识证明【非交互知识论证】完结 (2-1)

一个zero-knowledge proof，或者它的宽松版本argument，是prover P和verifier V之间的一种protocol，用来证明一个statement x 属于某种语言 L 。这种protocol必须满足三种性质：

• 完备性（completeness）：对于一个有效的statement x和一个有效的witness ω ，一个诚实的prover生成的proof总是会被诚实的verifier接受。

• 可靠性（soundness）:所有无限制的对手（adversary）都不能让一个诚实的verifier接受 x ∉ L 的proof（statistically）。所有PPT（probabilistic polynomial time）的adversary都不能让一个诚实的verifier接受 x ∉ L 的argument（computationally）。

• 零知识性（zero-knowledge）：对于任何statement x ∈ L ，都可以在不知道witness ω的情况下，模拟polynomial-time下prover和verifier的交互。（这意味着verifier无法在证明过程中获得statement的任何信息。

诚实验证者零知识（Honest-verifier zero-knowledge）arguments或proofs和上述定义类似，但我们假设verifier是诚实的，并且遵照协议的内容执行操作。这种放宽可以使我们构造更加高效的方案。

我们之前讨论的proof和argument都是用来证明从属关系statement的工具，即证明一个statement x 属于某种语言 L。如果把目光限制在NP语言，这样的命题可以被转换为存在性声明（existential statement），其形式为 ∃ω，Rʟ(x，ω)＝1 。知识证明（proof of knowledge）和传统zero-knowledge proof相比强化了安全保证。Zero-knowledge proof仅限于让verifier相信存在一个witness ω使得statement成立，而proof of knowledge则进一步展示了prover确实知道这样一个witness ω。

为了实现这一目标，我们首先需要定义，对于prover，什么叫做确实知道这样一个witness ω。直观上来说，要确保prover使用了这个witness，我们应该可以从prover那里“提取（extarct）”出这个知识。非正式的说，我们认为一个高效的算法 A 知道一个值 ω ，如果我们可以构造一个simulator Sim，对于任何可以生成接受性转录（accepting transcript）的 A ，Sim都可以从与 A 的交互中提取出witness ω。

其次，proof of knowledge的另一个重要性质是，即使对于从存在性角度来时是平凡（trivial）的statement，它仍然是有意义的。换句话说，对于一些trivial语言来说，确定一个statement的是否属于这个语言的是显而易见的，但是要算出来却非常困难。这里，我们使用一个经典例子：

离散对数语言（Discrete Logarithm Language）。设Ըᴅʟog(𝔾，g)表示一个循环群（cyclic group) (𝔾，·)，其中 g 是这个群的生成元（generator），对于以下语言：

Ըᴅʟog(𝔾，g)＝{h ∈ 𝔾|∃x ∈ ℤ，gˣ＝h} .

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。