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

[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.

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