第五章 高级协议
5.1 零知识证明
下面是另一个故事：
Alice：“我知道联邦储备系统计算机的口令，汉堡包秘密调味汁的成分以及Knuth第四卷的内容。”
Bob：“不，你不知道。”
Alice：“我知道。”
Bob：“你不知道！”
Alice：“我确实知道！”
Bob：“请你证实这一点！”
Alice：“好吧，我告诉你！”（她悄悄地说出了口令）。
Bob：“太有趣了！。现在我也知道了。我要告诉《华盛顿邮报》”
Alice：“啊呀！”
不幸的是，Alice要证明一些事情给Bob看的通常方法是Alice告诉Bob。但这样一来Bob也知道了这些事情。现在，Bob就可以告诉他想要告诉的其它人，而且Alice对此毫无办法。（在文献中，协议常常使用不同的人物。Peggy通常扮成证明者，而Victor则扮成验证者，他们的名字将代替Alice和Bob出现在下面的例子中。）
Peggy可使用单向函数进行零知识证明[626]。这个协议向Victor证明Peggy确实拥有一部分信息，但却没有给予Victor确定这个信息是什么的办法。
这些证明采取了交互式协议的形式。Victor问Peggy一系列问题，如果Peggy知道那个信息，她就能正确地回答所有问题，如果她不知道，她仍有正确回答的机会--在如下例子中有50%的机会。大约在十个问题之后，将使Victor确信Peggy知道那个信息。然而，所有的问题或回答都没有给Victor提供关于Peggy所知信息的任何信息——只有她知道这个信息。
基本的零知识协议
Jean-Jacques Quisquater和Louis Guillou[1281]用一个关于洞穴的故事来解释零知识，如图5.1所示，洞穴里面有一个秘密，知道咒语的那些人能打开C和D之间的密门。对其他任何人来说，两条通道都是死胡同。
Peggy知道这个洞穴的秘密。她想对Victor证明这一点，但她不想泄露咒语。下面是她如何使Victor相信的过程：
（1）Victor站在A点；
（2）Peggy一直走进洞穴，到达C点或者D点；
（3）在Peggy消失在洞穴中之后，Victor走到B点；
（4）Victor向Peggy喊叫，要她：
（a）从左通道出来，或者
（b）从右通道出来；
（5）Peggy答应了，如果有必要她就用咒语打开密门；
（6）Peggy和Victor重复步骤（1）至（5）n次。
图 5.1 零知识洞穴
假设Victor有一个摄像机并记录下他所看到的一切。他记录下Peggy消失在洞中的情景，记录下他喊叫Peggy从他选择的地方出来的时间，记录下Peggy走出来。他记录下所有n次试验。如果他把这些记录给Carol看，她会相信Peggy知道打开密门的咒语吗？肯定不会。在不知道咒语的情况下，如果Peggy和Victor事先商定好Victor喊叫什么，那将如何呢？Peggy会确信她走进Victor叫她出来的那一条路。然后她就可以在不知道咒语的情况下在Victor每次要她出来的地方出来。或许他们不那么做，Peggy会走进其中一条通道，Victor会发出一个随机的要求。如果Victor猜对了，好极了；如果他猜错了，他们会从录像带中删除这个试验。总之，Victor能获得一个记录，它准确显示与实际证明Peggy知道咒语相同的事件顺序。
这说明了两件事情。其一，Victor不可能使第三方相信这个证明的有效性。其二，它证明了这个协议是零知识的。在Peggy不知道咒语的情况下，Victor显然不能从记录中获悉任何信息。但是，因为无法区分一个真实的记录和一个伪造的记录，所以Victor不能从实际证明中了解任何信息——它必定是零知识。
协议使用的技术叫做分割选择，因为它类似于将任何东西等分的经典协议：
（1）Alice将东西切成两半；
（2）Bob给自己选择一半；
（3）Alice拿走剩下的一半。
Alice最关心的是在步骤（1）中的等分，因为Bob可以在步骤（2）中选择他想要的那一半。Michael Rabin是第一个在密码学中使用分割选择技术的人[1282]。交互式协议和零知识的概念是后来才正式提出的[626，627]。
分割选择协议起作用是因为Peggy没有办法重复猜出Victor要她从哪一边出来。如果Peggy不知道这个秘密，那么她只能从进去的路出来。在协议的每一轮（有时叫一次鉴别）中她有50%的机会猜中Victor会叫她从哪一边出来，所以她有50%的机会欺骗他。在两轮中她欺骗Victor的机会是25%。而所有n次她欺骗Victor机会是2n分之一。经过16轮后，Peggy只有65536分之一的机会欺骗Victor。Victor可以安全地假定，如果所有16次Peggy的证明都是有效的，那么她一定知道开启C点和D点间的密门的咒语。（洞穴的比拟并不完美。Peggy可能简单地从一边走进去，并从另一边出来；这里并不需要任何分割选择协议，但是，数学上的零知识需要它。）
假设Peggy知道一部分信息而且这个信息是一个难题的解法，基本的零知识协议由下面几轮组成。
（1）Peggy用她 的信息和一个随机数将这个难题转变成另一难题，新的难题和原来的难题同构。然后她用她的信息和这个随机数解这个新的难题。
（2）Peggy利用比特约定方案提交这个新的难题的解法。
（3）Peggy向Victor透露这个新难题。Victor不能用这个新难题得到关于原难题或其解法的任何信息。
（4）Victor要求Peggy或者：
（a）向他证明新旧难题是同构的（即两个相关问题的两种不同解法）。
（b）公开她在步骤（2）提交的解法并证明是新难题的解法。
（5）Peggy同意。
（6）Peggy和Victor重复步骤（1）至（5）n次。
还记得洞穴协议中的摄像机吗？在此你可以做同样的事。Victor可以做一个在他和Peggy之间交换的副本。他不能用这个副本让Carol信服，因为他总能串通Peggy制造出一个伪造Peggy知识的模拟器。这个论点可以用来论证这样的证明是零知识的。
这类证明的数学背景是很复杂的。这个问题和这个随机变换一定要仔细挑选，使得甚至在协议的多次迭代之后，Bob仍不能得到关于原问题解法的任何信息。不是所有难题都能用作零知识证明，但很多可以。
图同构
举个例子来解释这个概念可能要费很多笔墨。这个概念来自图论[619，622]。连结不同点的线构成的网络称为图。如果两张图除点的名字不同其它都一样，它们叫“同构”。对于一个非常大的图，找出两个图是否同构需要计算机工作几百年的时间；这是在11.1节中讨论的那些NP—完全问题之一。
假设Peggy知道图G1和G2之间同构，下面的协议将使Victor相信Peggy的知识：
（1）Peggy随机置换G1产生另一个图H，并且H和G1同构。因为Peggy知道G1和H同构，她也就知道H和G2同构。对其他人来说，发现G1和H或H和G2之间同构与发现G1和G2之间同构一样难。
（2）Peggy把H送给Victor。
（3）Victor要求Peggy或者：
（a）证明G1和H同构，或者
（b）证明G2和H同构。
（4）Peggy同意。她或者：
（a）证明G1和H同构，但不证明G2和H同构，或者
（b）证明G2和H同构，但不证明G1和H同构。
（5）Peggy和Victor重复步骤（1）至（4）n次。
如果Peggy不知道G1和G2之间的同构性，她就不能创造出和这两个图都同构的图H。她只能创造一个图或者与G1同构或者与G2同构。同前面的那个例子一样，她只有50%的机会猜中Victor在第（3）步中会要求她执行哪一个证明。
这个协议没有给Victor任何有用的信息以帮助他了解G1和G2之间的同构性。因为Peggy在协议的每一轮都产生一个新图H，故不管他们经过多少轮协议Victor也得不到任何信息，他不能从Peggy的答案中了解G1和G2的同构性。
在每一轮中，Victor都得到H的一个新的随机置换，以及H和G1或G2之间的同构性。Victor也可以自己来产生这个协议。因为他能做一个此协议的模拟器，它能被证明是零知识的。
汉密尔顿圈
另一不同的例子是由Manuel Blum最先提出的[196]。Peggy知道一条沿图线走向的环形连续路径，通过每个点仅一次，这个环形连续路径被称为“汉密尔顿圈”。找到一个汉密尔顿圈是另一难题。Peggy拥有这部分信息——她可能通过利用某个汉密尔顿圈来构造图而得到该信息——这正是她想要Victor相信她知道的信息。
Peggy知道一个图G的汉密尔顿圈。Victor知道图G，但是不知道它的汉密尔顿圈。在不暴露汉密尔顿圈的情况下，Peggy要向Victor证明她知道这个汉密尔顿圈。下面是她的做法：
（1）Peggy随机地置换图G。她移动这些点并改变他们的标号，生成一个新图H。因G和H在拓扑上同构（即相同的图），如果她知道G的汉密尔顿圈，那么她能很容易地找到H的汉密尔顿图。如果她不是自己创造H，则确定两个图之间的同构性将是另一难题；它也需花费计算机几百年的时间。她加密H得到Hˊ（这必定是一种对H的每一条线的概率加密，即，对H的每一条线加密0或加密1）。
（2）Peggy给Victor一个Hˊ的副本。
（3）Victor要求Peggy或者
（a）向他证明Hˊ是G的同构副本的加密，或者
（b）向他出示H的汉密尔顿圈。
（4）Peggy同意，她或者
（a）通过揭示置换和解密一切证明Hˊ是G的同构副本的加密，但不出示G或H的汉密尔顿圈，或者
（b）仅通过解密构成汉密尔顿圈的那些线出示H的汉密尔顿圈，但不证明G和H在拓扑上同构。
（5）Peggy和Victor重复步骤（1）至（4）n次。
如果Peggy诚实，她就能给Victor提供步骤（4）中两个证明中的任何一个。但是，如果她不知道G的汉密尔顿圈，她就不能创造一个加了密的图H'，这个图H'能满足两个要求。她最多能做到的是使其所创造的图或者与G同构，或者具有相同数目的点线及一个有效的汉密尔顿圈。虽然她有50%的机会猜中Victor在执行第（3）步中将要他完成哪一个证明，但Victor可将协议重复足够多次来使他自己确信Peggy知道G的汉密尔顿圈。
并行零知识证明
基本的零知识协议包括Peggy和Victor之间的n次交换。可以把它们全部并行完成：
（1）Peggy使用她的信息和n个随机数把这个难题变成n个不同的同构难题，然后用她的信息和随机数解决这n个新的难题。
（2）Peggy提交这n个新难题的解法。
（3）Peggy向Victor透露这n个新难题。Victor无法利用这些新难题得到关于原问题或其解法的任何信息。
（4）对这n个新难题中的每一个，Victor要求Peggy或者：
（a）向他证明新旧难题是同构的，或者
（b）公开她在步骤（2）中提交的解法，并证明它是这个新难题的解。
（5）Peggy对这n个新难题中的每一个都表示同意。
很不幸，事情并非如此简单。该协议没有同前协议相同的零知识性质。在第（4）步，Victor可以把第（1）步所提交的所有值的单向HASH函数作为询问，这样就使副本不可冒充。它仍然是零知识的，但属于不同种类。实际应用中它似乎是安全的，但是没有人知道怎样证明它。我们确实知道，在某些环境下，针对某些问题的某些协议可以并行运行，并同时保留它们的零知识性质[247，106，546，616]。
非交互式零知识证明
不能使Caro相信是因为这个协议是交互式的，并且她没有介入交互中。为了让Carol和其他感兴趣的人相信，我们需要一个非交互式的协议。
人们已经发明了非交互式零知识证明的协议[477，198，478，197]。这些协议不需要任何交互作用，Peggy可以公布他们，从而向任何花时间对此进行检验的人证明协议是有效的。
这个基本协议类似于并行零知识证明，不过只是用单向hash函数代替了Victor：
（1）Peggy使用她的信息和n个随机数把这个难题变换成n个不同的同构问题，然后用她的信息和随机数解决这n个新的难题。
（2）Peggy提交这n个新的难题的解法。
（3）Peggy把所有这些提交的解法作为一个单向hash函数的输入。（这些行为终归不过是一些比特串），然后她保存这个单向hash函数输出的头n个比特。
（4）Peggy取出在步骤（3）中产生的n个比特。对每个难题，她依次针对第i个新难题取出这n个比特中的第i个比特并且：
（a）如果它是0，她则证明新旧问题是同构的，或者
（b）如果它是1，她则公布她在第（2）步中提交的解法，并证明它是这个新问题的解法。
（5）Peggy将步骤（2）中的所有约定及步骤（4）中的解法都公之于众。
（6）Victor或Carol或其他感兴趣的人，可以验证步骤（1）至（5）是否被正确执行。
这很令人惊异：Peggy可以公布一些不含有关她的秘密的信息、却能让任何人相信这个秘密的存在。如果把这个问题作为初始消息和要签名的消息的单向hash，则这个协议也可用于数字签名方案。
这个协议起作用的原因在于单向hash函数扮演了一个无偏随机比特发生器的角色。如果Peggy要进行欺骗，她必须能预测这个单向hash函数的输出。（记住，如果她不知道这个难题的解法，她可以完成步骤（4）的（a）或（b），但不能两者一起。）如果由于什么原因她知道了这个单向hash函数会叫她做什么，那么她可以进行欺骗。然而，Peggy没有办法强迫这个单向hash函数产生哪些比特或猜中它将产生哪些比特。这个单向hash函数在协议中实际上是Victor的代替物——在步骤（4）中随机地选择两个证明中的一个。
在一个非交互式协议中，必定有更多的问/答序列迭代。不是Victor而是Peggy在用随机数挑选这些难题，她可以挑选不同的问题，因此有不同的提交矢量，直到这个hash函数产生她希望的东西为止。在一个交互式协议中，10次迭代——Peggy能进行欺骗的概率为210分之一（1024分之一）——是很好的了。但是，对非交互式零知识证明是不够的；记住，Mallory总能完成步骤（4）的（a）或(b)，他能设法猜测会要他完成哪一步，处理完步骤（1）直到步骤(3)，并弄清他是否猜对。如果他没有猜对，可以再试——反反复复。在计算机上进行1024次猜测不是难事。要防止这种穷举攻击，非交互式协议需要64次迭代，甚至128次迭代才是有效的。
这就是使用单向HASH函数的全部要点：Peggy不能预测HASH函数的输出，是因为她不能预测其输入。只有在她解决了新的难题以后，才能知道作为输入的提交。
一般性
Blum证明了任何数学定理都能被转化为一个图，使得这个定理的证明等价于证明图的汉密尔顿圈。假设有了单向函数并因此有了好的加密算法，则任何NP命题包括一个零知识证明，这种一般情况已在[620]中得到证明。任何数学证明都能被转化成一个零知识证明。采用这项技术，研究人员能向世人证明他们知道一个特殊定理的解法但又不会泄露那个证明是什么。Bium可以公布他的结果，同时又不泄露它们。
也存在一些最小泄露证明[590]。在最小泄露证明中，具有以下性质：
1．Peggy不能欺骗Victor。如果Peggy不知道证明，她使Victor相信她知道这个证明的概率是非常小的。
2．Victor不能欺骗Peggy。除了Peggy知道证明这个事实，他得不到关于证明的轻微线索。尤其在他自己没有完完全全地证明它的情况下，Victor不可能向其它人论证这个证明。
零知识证明有一个附加条件：
3．除了Peggy知道证明这个事实，Victor不能从Peggy处得到任何东西，因为没有Peggy 他不能自己得到有用的信息。
最小泄露证明与零知识证明之间存在相当大的数学区别。这个区别超越了本书的范围，但欢迎愿意深入研究的读者参阅参考书籍。概念介绍请看[626，619，622]。关于概念的更详尽的描述，基于不同数学假设，已在[240，319，239]阐述。
这里也有不同类型的零知识证明：
——完美的。有一个使副本与正本具有相同分布的模拟器（例如汉密尔顿圈和图的同构）。
——统计的。除了一定数量的例外，有一个使副本与正本具有相同分布的模拟器。
——计算的。有一个使副本与正本不能区别的模拟器。
——无用的。可能不存在模拟器，但是我们可以证明Victor不能从证明中得到任何更多的信息（例如并行证明）。
在这些年中，关于最少泄露和零知识证明，无论是理论还是应用上，人们已做了广泛的工作。Mike Burmester和Yvo Desmedt发明了广播交互式证明，其间的一个证明者能将零知识交互式证明广播给一大群验证者[280]。密码学家们证明，能用一个交互式证明证明的每一件事，也能用一个零知识交互式证明来证明[753，137]。
关于该题目的好综述文章是[548]。更多的数学上的细节、变化、协议和应用，请参看[590，619，240，319，620，113，241，1528，660，238，591，617，510，592，214，104，216，832，97，939，622，482，615，618，215，476，71]，关于这个主题的论文比比皆是。
留言评论（旧系统）：