零知识证明【非交互知识论证】二

要研究密码学，必须对复杂度类（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)] 。

[2]中同时讨论了另外一个密码学中的重要问题，即prover是否会泄露除了 x ∈ L 以外的信息。如果没有泄露任何多余信息，我们就可以把这种proof称为zero-knowledge proof。一种正式定义zero-knowledge特性的方法就是引入simulator的概念，这在上一篇也曾经提到过，这里再重复一遍。Simulator可以完全模仿prover在protocol中的行为并在不知道witness的情况下生成一个“假的”proof。而verifier无法区分其交互的是真正的prover还是这个simulator。直观上来说，上面的定义意味着真正的proof和模拟器生成的proof无法被区分，说明真正的proof泄露的witness信息也和模拟出来的值一样多，注意，模拟器生成的证明和witness毫无关系，这就说明真实的proof是zero-knowledge的。在后续的论文[3]中，Goldreich, Micali, and Wigderson基于单项函数（one-way functions）存在的假设，构造了一个队任何NP语言都使用的zero-knowledge proofs。

在后续的研究中，为了达到简洁（succinct）的效果，计算可靠（computationally-sound）证明系统的概念被提出了，这种系统也被称为论证系统（argument systems），也是是SNARK中的argument的意思，这种系统的可靠性（soundness）只针对与计算资源有限（computatuinally bounded）的prover。如果抗碰撞哈希函数（CRHF，collision-resistant hash functions）是存在的，Kilian[4]展示了一种针对NP的交互论证（interactive argument）也是存在的。在这种protocol中，证明一个NP实例x 属于NP语言可以把通信量和verifier的运行时间现在在多项式时间内。这样可以把通信复杂度（communication complexity）和verifier的运行时间限制在witness的小的次线性（sublinear）级别，甚至独立于witness大小的论证系统，被称为succinct。

[1] László Babai. Trading group theory for randomness. In 17th ACM STOC, pages 421–429. ACM Press, May 1985.

[2] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In17th ACM STOC, pages 291–304. ACM Press, May 1985.

[3] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In27th FOCS, pages 174–187. IEEE Computer Society Press, October 1986.

[4] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In24th ACM STOC, pages 723–732. ACM Press, May 1992

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