GMR89：The knowledge complexity of interactive proof systems

这篇博客有点头重脚轻的感觉，因为笔者觉得后面的很多定义没有必要重述，对于文章中的协议也没有进行重写，笔者的思考好像也在introduction都讲了，这篇文章感觉也是重在引入，因此在后面写的比较简略，只记录了相对比较重要的内容，大年初一属实是有点太累了😫，一会还想陪女朋友聊会天🥰，后面再进行完善。

Abstract

通常，在定理的证明往往会包含除定理正确性（correctness）之外的其他“知识”（knowledge）。在这篇文章中，作者进一步发展了证明中包含的知识的计算复杂性理论，零知识证明被定义为除了问题中命题的正确性外，不传递其他知识的证明。

Introduction

我们通常认为一种语言L是NP的（即在非确定性多项式时间内是可接受的）等价于说存在一个针对L的多项式时间“证明系统”：对于输入\(x\)，Prover生成字符串\(\alpha\)，Verifier在\(x\)和\(\alpha\)上进行运算，在时间\(O(|x|)\)时间内判断\(x\)是否属于L。

我们可以仔细思考一下这样的证明系统，可以得到更多的信息：

• NP问题只要求给定一个解，我们能够在多项式时间内验证该解的正确性，所以我们对于Prover的计算资源是没有限制的，对于Verifier的计算资源，我们要求是多项式时间的
• 由于Verifier是多项式时间的，所以给定的解的大小也一定是多项式大小的，否则仅仅是读取就已经超出了Verifier的能力。
• 在这样的证明系统中，Verifier和Prover之间没有交互，Verifier只读取了Prover给出的解
• Verifier和Prover都没有使用Randomness，然而Randomness是一个非常强大的工具，在实际情况下这个限制貌似没有那么必要。

在这种理解下的NP和数学证明（mathematical proof）很相似

因此我们解除NP的一些限制，允许（1）Verifier和Prover之间进行交互，（2）允许Verifier和Prover使用Randomness。从而，我们就得到了交互式证明系统（Interactive Proof system）。交互式证明系统能力十分强大，可以证明PSPACE中的所有问题。

接下来，我们考虑在Verifier和Prover交互过程中传递的知识，以下为两个极端情况：

• \(F\in \mathrm{SAT}\)：针对SAT问题，Prover可以直接将一个满足的赋值发送给Verifier，这样Verifier不仅知道了\(F\in \mathrm{SAT}\)，而且还知道了\(F\)的一个赋值
• \(Q\in\mathrm{P}\)：对于多项式时间问题，Prover不需要发送任何信息，Verifier就可以知道\(Q\in \mathrm{P}\)

如果语言L的一个交互式证明系统中，Prover只传递给Verifier命题正确性，不包含其他任何知识，我们就称其具有零知识性。零知识性需要保证无论Verifier是否遵守协议，都要满足。

如果只能保证诚实Verifier情况下的零知识性，我们称之为HVZK（Honest Verifier Zero-Knowledge）

在零知识交互式证明中，验证者在协议中获取到的应该是验证者可以自己计算的东西，或者称之为可以模拟出来的东西，这就引出来了Simulator的概念。（后面会有提到）

零知识证明有很多的应用场景，比如密码信息交换等，用于替代可信第三方的存在，证明Prover所说的话是属实的，但是替代可信第三方的存在势必需要Prover具备更强的能力（信息、资源等），这也是一种trade off。

目前已知所有NP问题都具有零知识证明。

其实很好证明，我们对SAT问题具有零知识证明（Sumcheck），SAT是NP-complete问题，因此\(\mathrm{NP}\subseteq\mathrm{IP}\)

Interactive proof systems

在上一节的基础上，我们首先考虑一个高效的定理证明都需要有哪些性质：

• 我们可能证明一个正确的定理（Completeness）
• 我们不可能证明一个错误的定理（Soundness）
• 不考虑生成证明的难度，Verifier可以高效的验证定理的正确性

NP其实在一定程度上具备了上述性质，但是我们希望能够泛化一下这个概念：Verifier具备Randomness，允许一定概率的error。

Interactive Turing Machine

Interactive proof systems

定义：我们定义\((A,B)\)为\(L\)的交互式证明系统，如果\((A,B)\)满足：

• 对于每个\(k\)，对于作为\((A,B)\)输入的\(L\)中足够大的\(x\)，\(B\)停止并接受的概率至少为\(1-|x|^{-k}\)。
• 对于每个\(k\)，对于足够大的\(x\not\in L\)，对于任何ITM \(A^{\prime}\)，在输入\(x\)到\(\left(A^{\prime},B\right)\)时，\(B\)最多接受\(|x|^{-k}\)的概率。

对于第一种情况，B将以不可抗拒的概率接受x，对于第二种情况，B被欺骗的概率可忽略不计。值得一提的是，在交互式证明系统中，B不需要相信与它交互的对象，只需要相信自己所投掷的硬币即可（Randomness）。

对于以上定义的更泛化的版本是A可以不仅仅是一个ITM，还可以是一个无限状态机，甚至确定型PSPACE机。

A是随机性对于实现零知识证明至关重要

Arthur-Marlin game

Arthur指的是Verifier，Marlin指的是Prover，Arthur-Marlin是一种public coin IP，Verifier只能向Prover发送其产生的随机数，AM可以通过Shamir转换转变为非交互式证明系统，IP[k]也可以通过set lower bound协议和Lautemann证明来转换为AM[k+2]

AM所能证明的问题集合和IP是一样的，但是IP中的private coin对于零知识性是至关重要的，存在语言L具备完美或统计零知识的IP，但是不具备完美或统计零知识的AM。

Zero-knowledge

交互式证明系统的完备性（Completeness）取决于Prover和Verifier，稳健性（Soundness）取决于Verifier，零知识性（Zero-knowledge）仅取决于Prover。

对于上述表述，我们可以理解为我们对于Verifier或Prover没有要求，不必是honest，不必遵守协议

IP的零知识性我们可以理解为，在交互过程中B从A看到的随机分布，也可以通过自己生成。

Indistinguishability of random variables

随机变量：\(U=\{U(x)\}\)，其中参数\(x\)取自\(L\)。如果随着\(|x|\)的增大，\(U=\{U(x)\}\)可以被\(V=\{V(x)\}\)所替代，我们就称\(U=\{U(x)\}\)和\(V=\{V(x)\}\)是不可区分的。

我们可以考虑以下game：从\(U=\{U(x)\}\)和\(V=\{V(x)\}\)随机抽取一个变量，并将其发送给一个判定者。判定者输出\(0\)，则代表变量来自于\(U=\{U(x)\}\)；判定者输出\(1\)，则代表变量来自于\(V=\{V(x)\}\)。如果随着\(|x|\)的增长，判定者的输出逐渐变的没有意义，则说明\(U=\{U(x)\}\)和\(V=\{V(x)\}\)不可区分。

有三种不同程度的不可区分性：

• 等价（equality）：\(U=\{U(x)\}\)和\(V=\{V(x)\}\)完全相等
• 统计不可区分性（statistics indistinguishability）：判定者可以使用无限时间，但是有限的抽样
• 计算不可区分性（computational indistinguishability）：判定者可以使用有限时间和有限的抽样

形式化定义：（统计不可区分性）设\(L \subset\{0,1\}^*\)为一种语言。随机变量\(\{U(x)\}\)和\(\{V(x)\}\)的两族在统计学上无法在\(L\)上区分，如果 \[ \sum_{\alpha \in\{0,1\}^*}|\operatorname{prob}(U(x)=\alpha)-\operatorname{prob}(V(x)=\alpha)|<|x|^{-c} \]

对于所有常量\(c>0\)和所有足够长的\(x \in L\)。

举例：设\(U(x)\)为所有长度\(|x|\)的字符串分配相等的概率，并让\(V(x)\)将概率\(2^{-|x|}\)分配给所有长度\(|x|\)的字符串，除了\(0^{|x|}\)，其概率为0和\(1^{-|x|}\)，即概率为\(2^{-|x|+1}\)。那么\(\{U(x)\}\)和\(\{V(x)\}\)是\(\{0,1\}^*\)上统计上无法区分的两个随机变量族。

形式化定义：（计算不可区分性）。设\(L \subset\{0,1\}^*\)为一种语言。随机变量\(U\)和\(V\)的两个有界族在\(L\)上在计算上是不可区分的，如果对于所有多尺寸电路族\(C\)，对于所有常数\(c>0\)和所有足够长的字符串 \(x \in L\)，

\[ |P(U, C, x)-P(V, C, x)|<|x|^{-c} 。 \] 举例：考虑一个在Goldwasser和Micali意义上安全的概率加密算法；对于\(n\)整数，让\(U\left(1^n\right)\)和\(V\left(1^n\right)\)是随机变量，分别将安全参数\(n\)上的0和1的可能加密作为值。那么\(U\)和\(V\)在\(L=\{1\}^*\)上是计算无法区分的。

我们认为，随机变量的计算不可区分性的概念达到了正确的通用性水平。因此，我们将称不可区分的任意两个计算上不可区分的随机变量家族。

Zero-knowledge

形式化定义：设\(L \subset\{0,1\}^*\)为语言，\((A, B)\)为协议。我们说\((A, B)\)是完美的（统计/计算）\(L\)的零知识，对于\(B^{\prime}\)，如果随机变量族\(View_{A，B^{\prime}}\)是完美的（统计/计算）近似的 \[ L^{\prime}=\left\{(x, H) \mid x \in L \text { and }|H|=|x|^c\right\} 。 \]

我们说\(（A，B）\)是\(L\)上的完美（统计/计算）零知识，如果它是所有概率多项式时间ITM \(B^{\prime}\)上的完美（统计/计算）零知识。

各种复杂度类的零知识性：

• 所有的BPP问题都有完美零知识证明
• GI问题有完美零知识证明
• GNI问题有统计零知识证明
• 在安全加密机制存在的假设下，所有NP问题都有计算零知识证明
• 如果NP-complete问题有完美或统计零知识证明，则PH会坍缩