6.1 零知识证明原理

零知识证明是一种加密方案，最初在20世纪80年代由MIT研究人员在论文中提出：“零知识协议是一方（证明方）可以向另一方（验证方）证明某事是真实的方法，除了这一具体陈述是真实的事实以外，不透露任何额外的信息。例如对于登录网站而言，在Web服务器上存储了客户密码的哈希值，为了验证客户实际上知道密码，目前大部分网站采用的方式是服务器对客户输入的密码进行哈希计算，并与已存结果对比，但是这种方式的弊病在于服务器在计算时就可以知道客户的原始密码，一旦服务器被攻击，用户的密码也就泄露了。如果能够实现零知识证明，那么就可以在不知道客户密码的前提下，进行客户登录的验证，即使服务器被攻击，由于并未存储客户明文密码，用户的账户还是安全的”。

基本的零知识证明协议是交互式的，需要验证方向证明方不断询问一系列有关其所掌握的“知识”问题，如果均能够给出正确回答，那么从概率上来讲，证明方的确很有可能知道其所声称的“知识”。例如某人声称知道一个数独难题的答案，一种零知识证明的方式是验证方随机指定这一次按列、按行还是按九宫格来检测，每次检测不需要看到数字摆的具体位置，只需要检测出来是否包含了1～9个数字即可，只要验证的次数足够多，那么可以大概率相信证明方是知道数独题目的解的。但是这样简单的方式还不能让人相信证明方和验证方均没有造假，在数独的案例中，两者有可能事先串通好，从而使得证明方在不知道答案的前提下通过验证。如果他们想让第三方信服，验证方必须也要证明自己每次的检测方案是随机的且自己没有和证明方串通。

由于第三方观察者难以验证交互式零知识证明的结果，因此当向多人证明某些内容时，需要付出额外的努力和成本。而非交互式的零知识证明顾名思义，不需要互动过程，避免了串通的可能性，但是可能会额外需要一些机器和程序来决定试验的序列：例如在数独的例子中，通过程序的方式来决定哪一次按行、哪一次按列来检测，但是这个试验序列必须保密，否则验证方预先知道了试验的序列就有可能利用这个信息提前准备，在并不知道真实“知识”的情况下通过验证。

零知识证明的内容可以概括为两类：“事实”类陈述：例如证明“一个特定的图可以进行三着色”，或者“一个数N是合数”；关于个人知识的陈述：例如“我知道这个特定图的染色方案”或者“我知道N的因式分解”。

但并不是所有的问题都有零知识证明的加密方案，Goldreich、Micali和Wigderson给出了理论上存在零知识证明解的有效范围。他们发现对于复杂度为多项式级的决策问题（问题的答案仅为是/否），存在已知的零知识证明方案。只需要在这样的NP问题中找到想要证明的论述，并转化为三色问题的一个实例，那么就可以利用已有的协议实现零知识证明。由于三色问题属于NPC问题，任何其他的NP问题都可以转化为这个问题的实例。