零知识证明【非交互知识论证】二 (3-1)

要研究密码学，必须对复杂度类（complexity class）有一定的了解。在后续的内容中，将会多次出现“多项式时间（polynomial time），”对数空间（logarithmic space）”，“常数深度（constant depth）”等概念，这些概念用来定义我们所探讨的计算问题的类型，计算模型，需要约束的计算资源等。另外还有两个主要的基本复杂度类，P与NP，相关材料很多，这里不展开讨论了。

首先我们还是重复一下什么是NP类，NP类包含了所有可以由一个无限制（unbounded）的prover计算出确定性证明（deterministic proofs）的语言。这里生成的proof可以被视为一个多项式长度的字符串。交互证明（interactive proof）在两个方面放松了上述的条件：首先，prover和verifier可以使用随机币（public coins），即可以在交互过程中加入随机性；其次，验证proof的输出只需要以足够合理的概率与statement的实际真相一致；最后，显然各方之间是可以进行交互的。

在1985年，在两篇独立论文中，Babai[1]和Goldwasser, Micali, and Rackoff[2]引入了interactive proofs，也被称为Arthui-Merlin proofs的概念，这两篇论文获得了Gödel奖，这是理论计算机界最高的奖项之一。两篇论文都谈论了复杂度类，其中计算能力无限的prover必须通过多次交互说服多项式计算能力的verifier一个statement的真实性。这两篇论文的主要区别在于对verifier的random coins的使用上，在[1]中，verifier必须想prover展示其在计算过程中使用的所有random coins。这样的interactive proofs被称为public coin interactive proofs。而[2]中正相反，verifier不需要展示其内部的计算状态，这种被称为private coin interactive proofs。和public coin interactive proofs相关的复杂度类被Babai表示为AM[f(n)] ，AM代表Arthur-Merlin， n 代表输入的长度， f(n) 代表允许的交互轮数。和private coin interactive proofs相关的复杂度类被Goldwasser, Micali, and Rackoff表示为 lP[f(n)] 。

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