零知识性
零知识性用来保护诚实的 Prover 不被恶意的 Verifier 欺骗而泄露证明所需的秘密证据。
上文中已经提到了证明系统的零知识性,将其简单描述为 Verifier 无法从交互中获取任何“知识”。这个描述是不确切的,因为它并没有给出一个严格的判断标准。零知识性的定义本身是违直觉的:Prover 明明发送了一些比特数据给 Verifier,为什么这个系统会是“零知识”的呢?实际上,“信息”并不等同于“知识”。如果 Verifier 获取了信息,但获得这些信息并不能让 Verifier 计算出更多结果,或者说这些信息是 Verifier 自己就能够计算出来的,那么 Verifier 就没有获取任何“知识”。在一个证明系统的执行过程中,Verifier 获得的所有信息包括:
;Verifier 自己的随机数r;Prover 发送给 Verifier 的所有信息 (记为p)。我们把这些信息称为 Verifier 的“视野”,记为
这些信息是 Verifier 计算过程中的所有不确定性的来源。确定了这些信息后,其他的一切都可以确定性地计算出来。注意到,
是一个随机变量。当 Verifier 与 Prover 执行了证明系统之后,Verifier 会获得这个随机变量的一个样本。如果 Verifier 能在没有 Prover 参与的情况下独自采样
那么这个系统就是零知识的。我们把采样
这个随机变量的算法叫做模拟器 (Simulator)。根据模拟器工作方式的不同,有如下不同的定义方式:
非黑盒模拟器,相对应的零知识性叫做非黑盒零知识。这个零知识的定义允许每个 Verifier 都存在一个“独家定制”的模拟器,这种定义允许模拟器针对不同的 Verifier 的实现细节来定制不同的采样过程。
黑盒模拟器,对应的就是黑盒零知识。这个零知识的定义要求存在唯一的模拟器,使得对所有的 Verifier,它都能够采样出
这个唯一的模拟器不可能知道所有 Verifier 的具体实现细节,所以它只能通过黑盒调用的方式来访问 Verifier。不过,模拟器对 Verifier 具有完全的控制权。模拟器可以决定 Verifier 的随机数 r,并给 Verifier 输入任何的 Prover 消息或
所以,在模拟器的眼里,Verifier 是一个黑盒的确定性算法。
如果模拟器只针对诚实 Verifier,对应的是诚实 Verifier 零知识 (Honest Verifier ZK)。因为诚实 Verifier 的行为是完全在预期中的,模拟器自然可以利用这些信息,因此这个模拟器对 Verifier 的访问是非黑盒的。
非黑盒模拟器访问到的信息更多,所以非黑盒零知识性比黑盒零知识性更容易成立。而诚实 Verifier 零知识是最容易实现的。关于诚实 Verifier 零知识,这里的诚实 Verifier 更准确地说是半诚实 (Semi-Honest) 的,或者说“诚实但好奇的”。这样的 Verifier 表面上会遵守协议,但有可能私下里试图从消息中提取知识。相比之下,恶意 Verifier 的行为是完全不受限制的。Verifier 可能宕机、发送不符合格式的消息、不按协议规定的分布采样,等等。要证明一个系统对恶意的 Verifier 满足零知识性,就要把所有这些情况都覆盖到。模拟器是一个随机算法,它的输出值也是一个随机变量,记为SimV 零知识性要求
和 SimV 这两个随机变量难以区分。不过,“难以区分”这个词也有很多种版本,由此可以推出零知识证明的多种定义:
如果两个随机变量的分布是统计不可区分的,也就是它们的统计距离 (Statistical Distance) 可忽略,就称这个证明系统是统计零知识 (Statistically Zero-Knowledge) 的;如果统计距离就是 0,又叫做完美零知识 (Perfect Zero-Knowledge) 的;
如果两个随机变量的分布是计算不可区分的,也就是任何多项式时间的随机敌手都无法区分这两个分布,就称这个证明系统是计算零知识 (Computationally Zero-Knowledge)的。
注意到,零知识的定义中,只要求对于正确的陈述 x SimV 和
的分布难以区分。对于错误的陈述,我们并不关心 Verifier 能够获取什么知识,因为这种情况下 Prover 本身就是不诚实的,没有必要去保护它,或者说,Prover 既然不遵守协议,那我们的协议设计得再好也保护不到它。不过,虽然x是错误的情况下,零知识性对 SimV的分布不做任何假定,但如果输入错误的x采样得到的SimV 被 Verifier 验证通过的概率和x 正确的情况下有显著差别的话,我们就可以借此判断x的正确性。这就意味着x只能来自一个平凡的 NP 语言。所以,对于困难的 NP 问题,把错误的x输入给模拟器,得到的SimV 也能够以一样的概率被验证通过。这么一来,零知识性和可靠性岂不是矛盾的?换句话说,对于错误的x Prover 为什么不能调用模拟器来欺骗 Verifier?实际上,Prover 不能控制 Verifier,它也就不能为模拟器提供采样SimV 所需要的资源。的确,一个恶意的 Prover 可以去调用模拟器,但是这对它来说没用,因为模拟器输出的 SetupV 中的 r 并不是正在与 Prover 交互的 Verifier 的随机数。此外,模拟器输出的 SetupV 也可能和 Verifier 收到的 SetupV 不同而导致验证不通过。不过,Prover 调起的模拟器无法获取 Verifier 的随机数,这已经足够保证安全性了,所以交互式证明中 SetupV 即使是固定常量也没问题。