零知识证明【非交互知识论证】完结

一个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} .

由于g 是群 𝔾 的generator，这是一个trivial的语言：所有群 𝔾 的元素都属于Ըᴅʟog(𝔾，g)这个语言，即 ∀h ∈ 𝔾，∃x ∈ ℤ，使得 gˣ＝h，且这个 x 是不唯一的。然而，计算这个一个整数x在计算上是不可行的（computationally infeasible），这涉及到对于离散对数问题的假设，在很多密码学原型中都有所涉及。因此，要求prover展示某个 h 的离散对数是否存在是没有意义的，因为这个witness总是存在的。但是说服verifier，prover确实知道基于g的h 的离散对数 x ，就提供了非平凡（non-trivial）的信息，也就有了意义。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。