不可知的数学可帮助隐藏秘密

# 不可知的数学如何帮助隐藏秘密 | Quanta Magazine 来源：https://www.quantamagazine.org/how-unknowable-math-can-help-hide-secrets-20260511/ ## 引言 数学家大部分时间都在思考可知的事情。但不可知的事物同样引人入胜。 最著名的例子或许来自逻辑学家库尔特·哥德尔的一个定理。哥德尔的著名成果——他于1931年发表的两个“不完备定理”之一——确立了这样一个事实：对于任何一组合理的数学基本假设（称为公理），都无法证明这些公理不会最终导致矛盾。尽管数学家们的研究方式与之前大致相同，但他们再也不能确信自己的规则是自洽的。 哥德尔定理发表50多年后，密码学家设计出了一种全新的证明方法，其中不可知性扮演了截然不同的角色。基于这种技术（称为**零知识证明**）的证明，能够说服最怀疑的受众相信某个陈述为真，而不必揭示其为何为真。 这两种源自不同时代、不同领域的不可知性，长期以来被认为毫无关联。如今，计算机科学家**Rahul Ilango**在两者之间**建立了一种惊人的联系**。当时还是研究生的他，设计出了一种新型零知识证明，其中保密性源于数学的根本局限。Ilango的方法绕过了研究者长期以来认为无法克服的零知识证明局限性，将这类证明的可能性推向了新的边界。这项工作也促使研究者探索数学逻辑与密码学之间其他有趣的关联。 “当我第一次看到Rahul的论文时，我的第一反应是：‘不，这不可能，’加州大学洛杉矶分校的密码学家**Amit Sahai**说，‘这真是一个令人难以置信的酷炫新方向。’” ## **色盲** 零知识证明源于计算复杂性理论——计算机科学中研究数学问题难易程度的分支。一个经典问题是：给你三支彩色铅笔和一张划分成许多区域的空白地图。你能在不给相邻区域涂上相同颜色的情况下为地图着色吗？ 这个问题可能极其困难。但如果有人给你一张着色好的地图，你可以检查每条边界，看它是否是一个有效的解决方案。这类问题——解决方案可能难以找到，但总是容易验证——被称为NP问题。它们在密码学中很有用，因为这些难以找到、易于验证的解决方案可以作为秘密密码。任何真正知道解决方案的人都能轻易证明它。 但这个简单的密码系统只有在知道解决方案的人愿意透露它时才有效。**零知识证明**由密码学家**Shafi Goldwasser**、**Silvio Micali**和**Charles Rackoff**于**1985年发明**，没有这个缺点。使用零知识证明，任何知道NP问题解决方案的人都可以在不泄露解决方案的情况下证明它——事实上，不泄露任何其他信息。  Shafi Goldwasser（左）、Silvio Micali（右）和 Charles Rackoff 设计了一种方法，可以在不透露任何信息的情况下证明某个陈述为真。 ©ACM，2013 “这是一个非常反直觉的概念，”剑桥大学的计算机科学家**Tom Gur**说，“在看到例子之前，它听起来像是某种不可能的事情。” Goldwasser和她的同事们通过将数学证明重新构想为两方之间的互动，实现了这一引人注目的特性。例如，在三着色问题的零知识证明中，有一个“证明者”，他想证明自己知道一个解决方案。他秘密地为地图着色，然后覆盖每个区域，只露出边界。另一方，“验证者”，选择一条边界。然后证明者揭开边界两侧的区域。 两方多次重复这个过程。在每一轮之前，证明者秘密地改变配色方案，以防止验证者从不同轮次中拼凑出信息。如果证明者每次都能根据挑战揭示出两种不同的颜色，验证者最终会相信证明者知道一个有效的着色方案。如果证明者是在虚张声势，验证者在足够的猜测后几乎肯定会发现着色中的缺陷。 零知识证明的互动特性使它们与普通的数学证明截然不同。普通数学证明可以写在教科书里，无需验证者的任何输入。直观上，互动似乎是零知识证明的必要元素。一个仅仅交出书面文件的证明者无法阻止验证者检查全部内容并了解证明者所知道的一切。证明者可以加密文件以防止验证者了解太多，但这样一来，验证者就无法确认证明是否有效，因为他们无法质问证明者。 1994年，密码学家**Oded Goldreich**和Yair Oren证明了一个定理，**证实了这种直觉**。他们的结果表明，不可能构造出完全满足Goldwasser、Micali和Rackoff定义的零知识的非交互式证明。这对那些还抱有希望、期待能有与普通证明别无二致的零知识证明的密码学家来说是个坏消息。 “人们只是说，‘算了，这不可能发生，’”约翰霍普金斯大学和NTT Research的密码学家**Abhishek Jain**说，“你怎么能克服不可能性呢？” Ilango的新结果表明了如何克服——通过利用另一种不可能性。 ## **不可能任务** 2023年夏天，在麻省理工学院研究生学习的第三年结束时，Ilango对复杂性理论中一个深奥的子领域——证明复杂性——越来越感兴趣。大多数复杂性理论家研究诸如三着色这样的问题有多难（在这种情况下，即找到有效着色需要多少步骤）。相比之下，在证明复杂性中，研究者则分析**证明关于这些问题的陈述**的难度——例如“没有办法给这张特定的地图正确着色”这样的陈述。他们通过衡量给定陈述的最简单证明的长度来评估这种难度。 在数学中，有些陈述无法被证明是真还是假。（这是哥德尔的另一个不完备定理。）然而，其他陈述在原则上可能是可证明的，但只有通过长到永远无法写下来的证明才行。实际上，这些本质上难以证明的陈述与哥德尔所指出的那些不可证明的陈述同样不可知。 一位戴着圆形眼镜的黑白照片男子。 库尔特·哥德尔证明了某些数学陈述是真的但不可证明。 Alfred Eisenstaedt/公有领域 研究者通常为了这些难以证明的陈述本身而研究它们，以便更好地理解数学证明的局限性。但Ilango怀疑这些陈述也可能在密码学中有应用。现代密码学中几乎所有的技术都依赖于解决特定问题的难度，比如关于地图着色的问题。Ilango想知道，如果他能利用证明特定陈述的难度呢？这样做或许能让他调出新的密码学技术。 “我们发现自己不断地撞上这些墙：‘为什么我们不能证明这个？为什么我们不能证明那个？’”IBM的复杂性理论家**Marco Carmosino**说，“我们能否从这种困难中受益？” 2024年，在几次失败的启动后，Ilango确定了密码学中一个特定的任务，可以作为他方法的试验场。他想构建非交互式的零知识证明。三十年前，Goldreich和Oren已经证明这类证明是不可能的。但Ilango意识到，“零知识”这个定义可能不止一种方式——而且不可能结果只适用于最初的定义。 要理解那个定义，请把自己放在地图着色例子中验证者的位置上。即使在与你互动之前，你也可以预测（或模拟）出有效的证明看起来会是什么样：每一轮，无论你选择哪条边界，证明者总是会揭示两个不同颜色的区域。用密码学家的术语来说，这个证明有一个“模拟器”，这就是证明为零知识的意义所在。 “如果你和我将要进行一场对话，但我能提前预测你将要说的一切，那么你大概会同意，通过和你交谈我不会学到任何东西，”Ilango说。 Goldreich和Oren的不可能结果实际上说的是，非交互式证明不能有模拟器，因此根据定义，它们不可能是零知识的。Ilango希望利用证明复杂性来定义一个新的零知识概念——他称之为“有效的”零知识——这个新概念将不受旧的不可能结果的限制，但仍然和普通的零知识一样有用。 他新定义的核心是一个简单的洞见：一个证明没有模拟器是可以接受的，只要没有人能看出来。 ## **证明的负担** 想象一下你正要买一把著名的牢不可破的锁。你阅读包装上的细则，期望找到锁是安全的保证。相反，你发现了一个坦率的承认：这把锁不安全，紧接着是一个承诺：尽管它不安全，但没有人能证明它不安全。 起初，这听起来像是故意用反常的方式推销一件无用的产品。但如果这把锁真的履行了这个不寻常的承诺，那它实际上和那把可证明牢不可破的锁一样安全。为了理解原因，想象你找到了一种破坏这把锁的方法。那么这把被破坏的锁本身就可以被看作是一个证明，证明它不安全——但如果包装上的承诺是正确的，这样的证明是不可能的。换句话说，如果存在一个漏洞，但不可能证明它存在，那么就没有办法利用它。 这就是Ilango新结果背后的基本思想。传统上，为了证明一个证明是零知识的，你会想表明它有一个模拟器。（在我们的比喻中，这相当于证明锁是牢不可破的。）但这同时也意味着证明必须是交互式的。为了获得有效的零知识，Ilango转而想要表明，很难保证他的证明**没有**模拟器。（也就是说，没有办法证明这把锁是可破坏的。） 如果他能表明这一点，他就能获得零知识的所有好处，同时巧妙地绕过对交互性的要求。“实际上很难想到任何现实生活中的情况，这种有效的零知识不够好，”Sahai说。 为了理解Ilango如何做到这一点，让我们回到三着色的例子。如果你知道如何给地图着色，你可以为“这张地图可以三着色”这一陈述写下一个非交互式证明。但由于1994年的不可能结果，这个证明不能有模拟器，因此不可能是零知识的。 利用Ilango的新方法，你会首先重写你想证明的陈述，现在添加一个额外的假设：“这张地图可以三着色——前提是假设没有有效的方法能在数学标准公理中找到矛盾。”这个额外的假设通常被视为理所当然。如果它是假的，那么数学就充满了矛盾，没有证明是可信的。如果它是真的（研究者普遍相信这一点），那么Ilango的新陈述就与原始陈述基本等价。 但这个假设也被认为是**实际上不可能证明的**：它在原则上可能是可证明的，但任何证明都会长到永远无法写下来。这使其成为那种哥德尔式的断言，证明复杂性研究者喜欢研究这类问题。 这也意味着证明的读者不能完全排除该假设是假的的可能性——这具有重要意义。特别地，这意味着我们可能生活在两个可能的世界中。在第一个世界中，该假设确实为真，我们又回到了起点：你写了一个非交互式证明，表明你的地图可以三着色，但这个证明不能有模拟器，因此不能是零知识的。但在第二个世界中，该假设是假的，我们不能再相信数学是一致的。这时不可能区分正确和错误的证明；关键的是，在这个离奇领域中，Goldreich和Oren的不可能结果不再适用。任何证明——无论有效还是无效，交互式还是非交互式——都可以有一个模拟器。 这个不太可能的第二个世界在某种程度上起到了漏洞的作用。读者无法确切知道自己生活在哪个世界中——尽管几乎肯定是第一个世界，其中数学仍然是安全的。这反过来意味着他们实际上不能肯定这个证明没有模拟器。尽管没有交互性，该证明仍然可以是有效的零知识。Ilango成功地避开了这个存在了几十年的不可能结果。 其中涉及的数学障眼法甚至可能让经验丰富的研究者都感到惊讶，但逻辑是成立的。“这相当令人费解，”Sahai承认，“第一次看到它时，你会想，‘等等，什么？’” 对许多计算机科学家来说，Ilango结果的更广泛影响与其结果本身一样令人兴奋。几十年来，证明复杂性研究者一直在研究深奥的问题，这些问题似乎与数学逻辑的联系比与计算机科学的任何其他领域都更紧密。这项新工作表明，这个著名的困难领域并不像看起来那么遥远。Ilango现在已经是新泽西州普林斯顿高等研究院的博士后研究员，他和其他人已经开始探索证明复杂性的思想如何可能帮助他们实现其他长期被认为不可能的密码学构造。 “我认为这不会是一个孤立的结果，”Jain说，“有时候，你只需要向人们展示门上的一个小裂缝。”