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

上一篇的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）的到来改变了。

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