想象一下，你有一些有用的知识——也许是秘方，或者密码的关键。你能在不透露任何信息的情况下向朋友证明你有这方面的知识吗？计算机科学家在 30 多年前证明，如果你使用所谓的零知识证明，你可以做到。

为了简单地理解这个想法，假设您想向您的朋友展示您知道如何通过迷宫，但不透露有关路径的任何细节。您可以在限定时间内简单地穿越迷宫，而您的朋友则被禁止观看。（时间限制是必要的，因为只要有足够的时间，任何人最终都可以通过反复试验找到出路。）你的朋友会知道你可以做到，但他们不知道怎么做。

零知识证明对处理秘密信息的密码学家很有帮助，也对计算复杂性研究人员有帮助，后者处理对不同问题的难度进行分类。“许多现代密码学都依赖于复杂性假设——假设某些问题很难解决，因此这两个世界之间一直存在一些联系，”麦吉尔大学计算机科学家Claude Crépeau说。“但是这些证明创造了一个完整的联系世界。”

零知识证明属于称为交互式证明的类别，因此要了解前者的工作原理，有助于理解后者。计算机科学家Shafi Goldwasser 、Silvio Micali 和 Charles Rackoff 在 1985 年的一篇论文中首次描述了交互式证明的工作方式类似于审讯：在一系列消息中，一方（证明者）试图说服另一方（验证者）一个给定的陈述是真实的。交互式证明必须满足两个属性。首先，一个真实的陈述总是最终会说服一个诚实的验证者。其次，如果给定的陈述是错误的，那么任何证明者——即使是一个假装拥有某些知识的人——都无法说服验证者，除非概率很小。

交互式证明本质上是概率性的。证明者仅仅靠运气就可以正确回答一两个问题，因此需要足够多的挑战，证明者必须正确完成所有挑战，验证者才能确信证明者确实知道该陈述是正确的。

当 Micali 和 Goldwasser（当时是加州大学伯克利分校的研究生）对通过网络玩扑克的逻辑感到困惑时，产生了这种互动的想法。所有玩家如何验证当他们中的一个人从虚拟套牌中获得一张牌时，结果是随机的？交互式证明可以引领潮流。但是，玩家如何才能验证整个协议——全套规则——被正确遵循，同时又不暴露每个玩家的手牌呢？

为了实现这一目标，Micali 和 Goldwasser 在交互式证明所需的两个属性中添加了第三个属性：证明不应该揭示任何知识本身，只揭示陈述的真实性。“有一个通过协议的概念，在协议的最后，你相信扑克玩家除了他们应该知道的之外，什么都不知道，”Goldwasser 说。

让我们考虑一个经典的例子。Alice 想向 Bob 证明某个图G——由边（线）连接的顶点（点）的唯一集合——具有“哈密顿循环”。这意味着该图有一条路径，该路径只访问每个点一次，并在它开始的同一个点处结束。爱丽丝可以通过简单地向鲍勃展示这样做的路径来做到这一点，但当然他也会知道路径。

下面是爱丽丝如何在不向鲍勃展示的情况下让鲍勃相信她知道存在这样一条路径的方法。首先，她绘制了一个新图H，它看起来不像G，但在关键方面相似：它具有相同数量的顶点，以相同的方式连接。（如果G真的有一个哈密顿圈，那么这种相似性意味着H也会。）然后，在用胶带覆盖 H 中的每一条边之后，她将 H 锁在一个盒子里，然后把盒子交给 Bob。这可以防止他直接看到它，但也可以防止她改变它。然后 Bob 做出选择：要么他可以要求 Alice 证明H确实与G相似，或者他可以让她向他展示H中的哈密顿循环。假设H确实与G足够相似，并且她确实知道路径，这两个请求对 Alice 来说应该很容易。

当然，即使 Alice 不知道G中的哈密顿循环，她也可以尝试通过绘制与G不相似的图或提交她不知道路径的图来欺骗 Bob。但是在他们玩了多轮之后，爱丽丝每次都欺骗鲍勃的机会变得微乎其微。如果她一切都正确，最终 Bob 将确信 Alice 知道图G中的哈密顿循环，而 Bob 从未见过它。

在首次描述此类证明的最初论文之后，Micali 和两位数学家——Oded Goldreich 和 Avi Wigderson——发现了一个具有深远影响的意想不到的结果。它与难度大致相同的一类主要问题有关，称为 NP。这些问题很难解决，但它们的解决方案很容易验证。三位研究人员发现，如果真正安全的加密是可能的，那么 NP 中每个问题的解决方案也可以用零知识证明来证明。这项研究帮助研究人员构想出零知识证明的变体，它们甚至不需要安全加密。这些被称为多证明者交互式证明。

并且在 1988 年，Micali 和其他人表明，如果证明者和验证者共享一串随机比特，则不需要交互。这在理论上意味着零知识证明不必是交互式的，这意味着不需要两方之间的持续通信。这将使它们对研究人员更有用，但直到 21 世纪之交之后，这种证明才开始流行。

“在 2000 年代后期，我们开始看到构建零知识证明的有效技术的发展，”约翰霍普金斯大学的密码学家Matthew D. Green说。“我们意识到，'等一下，实际上可能有一种方法可以在实践中使用它。'”

现在，证明者可以向验证者发送一条消息，而无需双方都在线，研究人员可以创建一个非常简短的证明，即使是非常复杂的问题也可以快速验证。这导致了一些实际用途，例如能够在加密货币交易后快速验证区块链，同时隐藏交易细节。2016 年，一群物理学家展示了零知识证明如何有助于核裁军：在不透露其核弹头设计的任何秘密的情况下，一个国家现在可以向核检查员证明弹头是活跃的还是不活跃的。

最近，量子计算的进步迫使 Crépeau 对过去的研究进行压力测试，以确保零知识协议仍然可行。2021 年，他帮助证明了即使涉及量子计算机，多证明者交互式证明也确实保持其保密性，但实现相同级别的安全性会使协议速度慢得多。他说，这一发现是个好消息，但随着技术的进步，将会出现新的担忧。

“我们未来可能进行的每一种计算都将涉及量子计算机，”Crépeau 说。“因此，作为优秀的偏执密码学家，每当我们评估系统的安全性时，我们都希望确保我们的系统是安全的。”