你如何证明一个秘密？

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

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

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

让我们考虑一个经典的例子。 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 说。 “因此，作为优秀的偏执密码学家，每当我们评估系统的安全性时，我们都希望确保我们的系统是安全的。”

编者注：Shafi Goldwasser 获得了西蒙斯基金会的资助，该基金会也资助了这本编辑独立的出版物。西蒙斯基金会的资助决定对我们的报道没有影响。