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

上一篇的interactive proofs可以看作是非交互证明（non-interactive proofs）的宽松版本，也就是我们允许prover和verifier进行交互。这一篇我们会讨论只需要prover向verifier发送一条信息的protocol。Verifier会对着一条信息（即proof）进行验证，然后决定是否接受。这个proof和之前提到的witness很像，但是proof不会向verifier泄露过多信息。

首先我们需要判定这样的证明是否存在。这样的系统被称为非交互零知识证明系统（NIZK，non-interactive zero-knowledge proof systems）。这个问题从实际的角度考虑也非常重要：在现实世界中，交互性意味着通过网络进行信息交换，这会引发一些延迟性问题。然而，在后续的研究中，我们发现在没有任何信任机制的标准模型中，我们不可能构造出对所有非平凡（non-trivial）语言都使用的单轮交互模型。

为了解决这个问题，后续的研究方向集中在了如果寻找最小的信任假设（trust assumptions）来建立一个高效的NIZK proof systems。Damgård[1]提出了公共参考字符串（CRS，common reference string）模型。该模型使用了这样一个假设：存在一个可信的设置（setup），使所有的相关方都可以访问从某个分布（distribution）D 中提取的相同字符串crs。在CRS模型中被证明安全的方案，只要设置是被正确执行的就可以被认为是安全的。CRS模型已经被证明在构建各种有强安全需求的高效原型（primitives）是非常方便的。但是依然存在一个没有解决的问题，那就是如果准确地执行setup。在实际操作中，解决方案是同过组织多方计算（MPC，multi-party computation）来实现，参与者需要被确信不会相互串通。另一个术语是结构化参考字符串（SRS，structured reference string），因为 SNARKs 使用的 CRS 通常具有某些代数结构。

Blum等作者提出了最早的NIZK proof system，并且提出了知道现在仍然被广泛使用的CRS模型[2]。这个最早的构造是一个有界的（bounded）NIZK proof system，这意味着对于不同的NP语言的statements，需要使用不同的CRS，而且statement的长度需要题CRS的长度控制。之后，Blum等作者又提出了一个针对3SAT问题的更加通用的NIZK proof system[3]，允许使用相同的CRS证明多个statement。[2]、[3]两种方案都是基于特定的数论（number-theoretic）假设，后来，很多研究展示了各种不同假设的不同构造方法。

在后面很长一段时间，有两种主要的NIZK proof systems：高效但启发式安全（heuristically secure）的proof systems，这种系统在随机预言机模型（ROM，random oracle model）中构造；低效，在隐藏随机位（hidden random bits）模型中构造，这种系统可以在标准模型中被实例化（instantiate），同时基于经过充分研究的假设。这一状态被配对密码学（pairing-based cryptography）的到来改变了。

Groth, Ostrovsky, and Sahai提出的GOS系统[4]是第一个针对任意NP语言的NIZK论证系统（argument system），同时也是第一个对于任意NP语言的通用可组合安全（UC-secure，universal composable secure，这也是个大坑…）argument system。该系统解决了NIZK protocols的一个核心开放问题（open problem），与之前[2]、[3]中的系统有这非常显著的区别。

这一系列的工作最终以Groth-Sahai proofs框架[5]的提出宣告完成，GS框架确定了一类受限（restricted），但非常强大的语言，这些语言可以设计出高效的基于pairing的NIZK，其安全性基于几乎所有对配对友好（pairing-friendly）群（group）上的标准假设。这个框架极大的提高了NIZK的效率和实用性，并且创造了一个新的NIZK应用的研究方向。

然而，这些方案为了实现针对不诚实（dishonest）prover的自适应可靠性（adaptive soundness），在proof statement的长度上有一定的限制。Abe and Fehr提出了第一个对NP语言的自适应可靠（adaptively-sound）的统计（statstical）NIZK argument，不对proof statement进行任何限制，需要不可证伪（non-falsifiable）的假设。他们同时提出了另一个结果：除非NP ⊆ P/poly ，否则不存在针对NP-complete语言的adaptively-sound statstical NIZK argument可以具有对标准密码学假设的“直接黑盒（direct black-box）”安全规约（reduction）。

[1] Ivan Damgård. Efficient concurrent zero-knowledge in the auxiliary string model. In Bart Preneel, editor,EUROCRYPT 2000, volume 1807 of LNCS, pages 418–430. Springer, Heidelberg, May 2000.

[2] Manuel Blum, Paul Feldman, and Silvio Micali. Non-interactive zero-knowledge and its applications (extended abstract). In20th ACM STOC, pages 103–112. ACM Press, May 1988.

[3] Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Non-interactive zero-knowledge with preprocessing. In Shafi Goldwasser, editor,CRYPTO’88, volume 403 of LNCS, pages 269–282. Springer, Heidelberg, August 1990.

[4] Jens Groth, Rafail Ostrovsky, and Amit Sahai. Perfect non-interactive zero knowledge for NP. In Serge Vaudenay, editor,EUROCRYPT 2006, volume 4004 of LNCS, pages 339–358. Springer, Heidelberg, May / June 2006.

[5] Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In Nigel P. Smart, editor,EUROCRYPT 2008, volume 4965 of LNCS, pages 415–432. Springer, Heidelberg, April 2008.

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