想象一下，你有一些有用的知识——也许是秘方，或者密码的关键。 你能在不透露任何信息的情况下向朋友证明你有这方面的知识吗？ 计算机科学家在 30 多年前证明，如果你使用所谓的零知识证明，你可以做到。
为了简单地理解这个想法，假设您想向您的朋友展示您知道如何通过迷宫，但不透露有关路径的任何细节。 您可以在限定时间内简单地穿越迷宫，而您的朋友则被禁止观看。 （时间限制是必要的，因为只要有足够的时间，任何人最终都可以通过反复试验找到出路。）你的朋友会知道你可以做到，但他们不知道怎么做。
零知识证明对处理秘密信息的密码学家很有帮助，也对计算复杂性研究人员有帮助，后者处理对不同问题的难度进行分类。 “许多现代密码学都依赖于复杂性假设——假设某些问题很难解决，因此这两个世界之间一直存在一些联系，”说 克劳德·克雷波，麦吉尔大学的计算机科学家。 “但是[这些]证明创造了一个完整的联系世界。”
零知识证明属于称为交互式证明的类别，因此要了解前者的工作原理，有助于理解后者。 第一的 描述 在计算机科学家 1985 年的一篇论文中 沙菲·戈德华瑟, Silvio Micali 和 Charles Rackoff，交互式证明的工作就像审讯：在一系列消息中，一方（证明者）试图说服另一方（验证者）给定的陈述是真实的。 交互式证明必须满足两个属性。 首先，一个真实的陈述总是最终会说服一个诚实的验证者。 其次，如果给定的陈述是错误的，那么任何证明者——即使是一个假装拥有某些知识的人——都无法说服验证者，除非概率很小。
交互式证明本质上是概率性的。 证明者仅仅靠运气就可以正确回答一两个问题，因此需要足够多的挑战，证明者必须正确完成所有挑战，验证者才能确信证明者确实知道该陈述是正确的。
当 Micali 和 Goldwasser（当时是加州大学伯克利分校的研究生）对通过网络玩扑克的逻辑感到困惑时，产生了这种互动的想法。 所有玩家如何验证当他们中的一个人从虚拟套牌中获得一张牌时，结果是随机的？ 交互式证明可以引领潮流。 但是，玩家如何才能验证整个协议——全套规则——是否被正确遵循，同时又不暴露每个玩家的手牌呢？
为了实现这一目标，Micali 和 Goldwasser 在交互式证明所需的两个属性中添加了第三个属性：证明不应该揭示任何知识本身，只揭示陈述的真实性。 “有一个通过协议的概念，在协议的最后，你相信[扑克玩家]除了他们应该知道的之外，什么都不知道，”Goldwasser 说。
让我们考虑一个经典的例子。 Alice 想向 Bob 证明某个图 G ——由边（线）连接的独特的顶点（点）集合——具有“哈密顿循环”。 这意味着该图有一条路径，该路径只访问每个点一次，并在它开始的同一个点处结束。 爱丽丝可以通过简单地向鲍勃展示这样做的路径来做到这一点，但当然他也会知道路径。
下面是爱丽丝如何在不向鲍勃展示的情况下让鲍勃相信她知道存在这样一条路径的方法。 首先她画了一张新图， H，看起来不像 G 但在一个关键方面是相似的：它具有相同数量的顶点，以相同的方式连接。 （如果 G 确实有一个哈密顿循环，这种相似性意味着 H 也会。）然后，在覆盖每个边缘之后 H 用胶带把她锁起来 H 在一个盒子里，然后把盒子交给鲍勃。 这可以防止他直接看到它，但也可以防止她改变它。 然后 Bob 做出选择：要么他可以让 Alice 证明 H 真的很像 G，或者他可以让她给他看哈密顿循环 H. 这两个请求对 Alice 来说应该很容易，假设 H 真的很相似 G，而且她确实知道这条路。
当然，即使爱丽丝不知道哈密顿循环 G，她可以尝试通过绘制与 G，或者通过提交她不知道路径的图表。 但是在他们玩了多轮之后，爱丽丝每次都欺骗鲍勃的机会变得微乎其微。 如果她做对了，最终 Bob 会确信 Alice 知道图中的哈密顿循环 G，而鲍勃从未见过它。
在首次描述此类证明的最初论文之后，Micali 和两位数学家——Oded Goldreich 和 Avi Wigderson——发现了一个具有深远影响的意想不到的结果。 它与难度大致相同的一类主要问题有关，称为 NP。 这些问题很难解决，但它们的解决方案很容易验证。 三位研究人员 发现, 如果真正安全加密 是可能的，那么NP中每个问题的解也可以用零知识证明来证明。 这项研究帮助研究人员 想象 一开始甚至不需要安全加密的零知识证明的变体； 这些被称为多证明者交互式证明。
而在 1988 年，Micali 等人 显示 如果证明者和验证者共享一串随机比特，则无需交互。 这在理论上意味着零知识证明不必是交互式的，这意味着不需要两方之间的持续通信。 这将使它们对研究人员更有用，但直到 21 世纪之交之后，这种证明才开始流行。
“在 2000 年代后期，我们开始看到构建零知识证明的有效技术的发展，”说 马修·D·格林，约翰霍普金斯大学的密码学家。 “我们意识到，'等一下，实际上可能有一种方法可以在实践中使用它。'”
现在，证明者可以向验证者发送一条消息，而无需双方都在线，研究人员可以创建一个非常简短的证明，即使是非常复杂的问题也可以快速验证。 这导致了一些实际用途，例如能够在加密货币交易后快速验证区块链，同时隐藏交易细节。 而在 2016 年，一群物理学家 显示 零知识证明如何帮助核裁军：在不透露其核弹头设计的任何秘密的情况下，一个国家现在可以向核检查员证明弹头是活跃的还是不活跃的。
最近，量子计算的进步迫使 Crépeau 对过去的研究进行压力测试，以确保零知识协议仍然可行。 2021年，他帮助 演示 即使在涉及量子计算机的情况下，多证明者交互式证明也确实保持其保密性，但实现相同级别的安全性会使协议速度慢得多。 他说，这一发现是个好消息，但随着技术的进步，将会出现新的担忧。
“我们未来可能进行的每一种计算都将涉及量子计算机，”Crépeau 说。 “因此，作为优秀的偏执密码学家，每当我们评估系统的安全性时，我们都希望确保我们的系统是安全的。”
编者注：Shafi Goldwasser 获得了西蒙斯基金会的资助，该基金会也资助了这项工作 编辑独立出版物. 西蒙斯基金会的资助决定对我们的报道没有影响。
