不可知的数学如何助力隐藏秘密——译自Quanta Magazine量子杂志|定理|密码学|数学|数理|计算机|量子杂志|隐藏秘密

★置顶zzllrr小乐公众号，追踪《小乐数学科普》系列报道！

一位研究生近期利用数学证明的复杂性，在密码学领域创造出了一种强有力的新工具。另请参阅：

图源：Kristina Armitage/Quanta Magazine

作者：Ben Brubaker（量子杂志记者）2026-5-11

译者：zzllrr小乐（数学科普公众号）2026-5-14

求喜欢

引言

数学家们大部分时间都在思考那些可知的事物。但不可知的事物同样极具吸引力。

最著名的例子或许来自逻辑学家库尔特・哥德尔（Kurt Gödel）的一条定理。哥德尔这项广为人知的成果 —— 他在 1931 年发表的两条 “不完备性定理” 之一 —— 确立了：对于任何一套合理的数学基本假设（即公理），都无法证明这套公理最终不会引发矛盾。尽管数学家们的研究工作大体照旧，但他们再也无法确定自己所遵循的规则是自洽的。

哥德尔定理问世五十多年后，密码学家们设计出一种全新的证明方法，其中不可知性扮演了截然不同的角色。基于这种技术的证明被称为零知识证明，它能让即便最多疑的听众相信某条陈述（命题）为真，却不透露该陈述为何为真。

这两种不可知性分别诞生于数十年间、分属不同领域，长期以来被认为毫无关联。如今，计算机科学家拉胡尔・伊兰戈（Rahul Ilango）发现了二者之间惊人的联系 https://eprint.iacr.org/2025/1296 。还在攻读研究生期间，他就设计出一种新型零知识证明，其保密性源于数学的根本局限。伊兰戈的方法突破了研究人员长期认为无法逾越的零知识证明限制，拓展了这类证明的可能性边界。这项工作还推动研究者探索数理逻辑与密码学之间其他引人入胜的关联。

“我第一次看到拉胡尔的论文时，心想‘不可能，这绝对做不到’，” 加州大学洛杉矶分校的密码学家阿米特・萨海（Amit Sahai）说，“这是一个无比精妙的全新方向。”

色盲问题

零知识证明起源于计算复杂性理论 —— 计算机科学中研究数学问题难度的分支领域。以一个经典问题为例：给你三支彩色铅笔和一张划分出多个区域的空白地图，你能否给地图上色，且保证相邻区域颜色不同？

这个问题可能极其难解。但如果有人给你展示一张上好色的地图，你扫一眼每条边界就能验证这是否是有效解。这类解可能很难找到、却极易验证的问题被称为 NP 问题。它们在密码学中十分有用，因为这种 “难寻易验” 的解可以充当秘密密码。真正知道解的人能轻松证明自己知晓。

但这种简单的密码系统仅在知晓解的人愿意公开解的前提下有效。1985 年，密码学家莎菲・戈德瓦塞尔（Shafi Goldwasser）、西尔维奥・米卡利（Silvio Micali）和查尔斯・拉克夫（Charles Rackoff）发明的零知识证明不存在这一缺陷。借助零知识证明，任何知道 NP 问题解的人都能证明自己知晓，却无需公开解 —— 事实上，无需透露任何其他信息。

莎菲・戈德瓦塞尔（Shafi Goldwasser）（左）、西尔维奥・米卡利（Silvio Micali）（右）与查尔斯・拉克夫（Charles Rackoff）设计出一种方法，能够证明某一命题为真，同时完全不透露其成立的缘由。

图源：美国计算机协会ACM，2013年

“这是一个非常反直觉的概念，” 剑桥大学计算机科学家汤姆・古尔（Tom Gur）说，“在看到实例之前，这听起来像是不可能的事。”

戈德瓦塞尔及其同事通过将数学证明重新构想为两方之间的交互，实现了这一惊人特性。以地图三色问题的零知识证明为例：存在一个 “证明者”，想要证明自己知道解。证明者秘密给地图上色，然后遮盖每个区域，只露出边界。另一方 “验证者” 挑选一条边界，证明者随即揭开边界两侧区域的遮盖。

双方会重复这个过程很多次。每一轮开始前，证明者都会秘密更换配色方案，防止验证者从不同轮次中拼凑出信息。如果证明者对每一次挑战都揭露出两种不同颜色，验证者最终会确信证明者掌握有效上色方案。如果证明者在虚张声势，经过足够多次尝试后，验证者几乎肯定能发现上色方案的漏洞。

零知识证明

某些地图可以填充为三种颜色，且相邻区域不得共用同一颜色。通过一种零知识证明方法，“验证者”能够使“验证人”确信，给定的一张地图确实可以以这种方式进行着色，而无需透露具体的着色方法。

1、证明者在地图上秘密涂色，然后覆盖每个区域以隐藏颜色。

2、验证者指向一个边界，证明者揭示两侧的区域。

3、验证者指向一个边界，证明者揭示两侧的区域。

4、验证者再次指向一个边界，证明者揭示了两侧的两个区域。

重复这一过程多次。若未发现任何错误，验证者便可确信着色方案是无效的，但并不会获取到其他任何信息。若存在错误，验证者几乎可以肯定能够发现它。

图源：Mark Belan / Quanta Magazine

零知识证明的交互性使其与普通数学证明截然不同 —— 普通证明可以写在教科书里，无需验证者参与。直观来看，交互性似乎是零知识证明的核心要素。直接提交书面证明的证明者，无法阻止验证者通读全文、获知自己掌握的所有信息。证明者可以加密这份文件以避免验证者获取过多信息，但那样一来验证者就无法确认证明是否有效，因为他们无法向证明者质询。

1994年，密码学家奥德・戈德赖希（Oded Goldreich）和亚伊尔・奥伦（Yair Oren）证明了一条定理，证实了这一直觉 https://link.springer.com/article/10.1007/BF00195207 。他们的研究结果表明：完全非交互式、且符合戈德瓦塞尔、米卡利与拉克夫所定义的零知识证明是不可能构建的。这对那些仍抱有希望、想要打造与普通证明完全一致的零知识证明的密码学家来说是个坏消息。

“人们当时都说‘算了吧，这不可能实现’，” 约翰斯・霍普金斯大学暨日本电报电话公司研究所的密码学家阿比谢克・贾因（Abhishek Jain）说，“要怎么突破这种不可能？”

伊兰戈的新成果给出了答案 —— 借助另一种 “不可能”。

不可能的任务

2023年夏天，在麻省理工学院研究生三年级结束时，伊兰戈对复杂性理论中一个晦涩的分支 ——证明复杂性产生了越来越浓厚的兴趣。大多数复杂性理论研究者研究的是三色问题这类问题的难度（本例中即找到有效上色方案所需的步骤数）。与之相对，证明复杂性领域的研究者分析的是证明这些问题相关陈述的难度（详情参阅：以及）—— 比如 “这张特定地图无法正确上色” 这类陈述。他们通过衡量给定陈述的最简证明长度来评估这种难度。

在数学中，有些陈述既无法被证明为真，也无法被证明为假。（这是哥德尔的另一条不完备性定理。）而另一些陈述原则上可证，但证明过程长到永远无法写完。从实际应用角度看，这些本质上难以证明的陈述，和哥德尔提出的不可证陈述一样，都属于不可知范畴。

库尔特・哥德尔（Kurt Gödel）证明了部分数学命题为真，却无法被证明。

图源：Alfred Eisenstaedt

研究人员通常出于研究本身的目的探究这类难证陈述，以更好地理解数学证明的边界。但伊兰戈猜想，这类陈述或许在密码学中也有应用价值。现代密码学几乎所有技术都基于解决特定问题的难度，比如地图上色相关问题。伊兰戈思考：如果转而利用证明特定陈述的难度，会怎样？这样做或许能让他设计出全新的密码学技术。

“我们总会不断撞上这些壁垒：‘为什么我们证明不了这个？为什么证明不了那个？’”IBM公司的复杂性理论学家马尔科・卡尔莫西诺（Marco Carmosino）说，“我们能否从这种难度中获益？”

2024年，经过几次失败的尝试后，伊兰戈找到了一项适合作为其方法试验场的密码学任务。他想要构建非交互式的零知识证明。三十年前，戈德赖希和奥伦已经证明这类证明不可能存在。但伊兰戈意识到，“零知识” 的定义或许不止一种 —— 而那条不可能性结论仅适用于最初的定义。

这相当颠覆认知。第一次看到时，你会想 “等等，这怎么可能？” —— 阿米特・萨海（Amit Sahai），加州大学洛杉矶分校UCLA

要理解这个定义，不妨代入地图上色案例中的验证者视角。即便在和证明者交互之前，你也能预测或模拟出有效证明的完整样子：每一轮中，无论你选择哪条边界，证明者总会揭露出两个颜色不同的区域。用密码学家的行话来说，这种证明具备 “模拟器”，而这正是该证明属于零知识证明的含义。

“如果我和你要进行一段对话，但我能提前预测你要说的所有内容，那你大概会认同，和你交谈我不会学到任何东西，” 伊兰戈说。

戈德赖希和奥伦的不可能性结论实际表明：非交互式证明无法拥有模拟器，因此按定义，它们不可能是零知识证明。伊兰戈希望借助证明复杂性定义一种全新的零知识概念 —— 他称之为 “有效” 零知识 —— 这种概念不受旧不可能性结论的约束，却和普通零知识证明同样实用。

他新定义的核心是一个简单的洞见：只要没人能察觉，证明没有模拟器也没关系。

证明的负担

想象你要买一把号称牢不可破的锁。你阅读包装上的小字说明，本以为会看到锁具安全的保证，结果却看到直白的承认：这把锁并不安全，随后附带一句承诺：即便它不安全，也没人能证明它不安全。

乍听之下，这像是故意歪曲宣传无用产品。但如果这把锁真的兑现了这个不同寻常的承诺，它实际上和可证明牢不可破的锁一样安全。原因如下：假设你找到了破解这把锁的方法，那么被破解的锁本身就构成了它不安全的证明 —— 但如果包装上的承诺属实，这样的证明是不可能存在的。换句话说，如果存在漏洞，却不可能证明该漏洞存在，那就没人能利用这个漏洞。

还在攻读研究生时，拉胡尔・伊兰戈就借助数学的局限性发明了一种新型零知识证明。

图源：詹妮弗・克鲁帕（Jennifer Krupa）

这是伊兰戈新成果背后的核心思路。传统上，要证明一份证明是零知识的，需要证明它具备模拟器。（用我们的比喻来说，这等同于证明锁具牢不可破。）但这也意味着证明必须是交互式的。而要实现有效零知识，伊兰戈转而证明：要确保他的证明没有模拟器是极其困难的。（也就是说，没人能证明这把锁可被破解。）

只要能证明这一点，他就能获得零知识的全部优势，同时巧妙绕开交互性要求。“在现实生活中，几乎所有场景下这种有效零知识都足够用了，” 萨海说。

要理解伊兰戈是如何做到的，我们回到地图三色案例。如果你知道如何给地图上色，就能写下一条非交互式证明，证明 “这张地图可以三色填充”。但受 1994 年不可能性结论的限制，这份证明无法拥有模拟器，因此不属于零知识证明。

运用伊兰戈的新方法，你需要先改写要证明的陈述，新增一条额外假设：“这张地图可以三色填充 —— 假设标准数学公理中不存在能被高效找到的矛盾。” 这条额外假设通常被视为理所当然。如果它不成立，数学就充满矛盾，没有任何证明可信。如果它成立（研究人员普遍如此认为），伊兰戈的新陈述本质上就和原陈述等价。

但这条假设也被认为实际上无法证明 https://www.cambridge.org/core/product/identifier/S0022481200041748/type/journal_article：原则上它或许可证，但任何证明都长到永远无法写完。这正是证明复杂性领域研究者热衷研究的哥德尔式断言。

这也意味着阅读证明的人无法完全排除假设不成立的可能 —— 这一点至关重要。具体来说，我们可能身处两种可能的世界。第一种世界中，假设确实成立，我们就回到了原点：你写下了一份非交互式证明，证明你的地图可以三色填充，但这份证明没有模拟器，因此不属于零知识证明。而第二种世界中，假设不成立，我们再也无法相信数学的自洽性，正确与错误的证明将无法区分；关键在于，在这个怪异的领域中，戈德赖希和奥伦的不可能性结论不再适用。任何证明 —— 无论有效或无效、交互或非交互 —— 都可以拥有模拟器。

这个看似不可能的第二种世界相当于一种漏洞。阅读者无法确定自己身处哪个世界 —— 尽管几乎可以肯定是数学保持自洽的第一种世界。这反过来意味着，他们无法真正确定这份证明没有模拟器。即便没有交互性，这份证明依然可以是有效零知识的。伊兰戈成功突破了这个存在数十年的不可能性结论。

其中涉及的数学巧思甚至会让资深研究者再三审视，但逻辑完全成立。“这相当颠覆认知，” 萨海坦言，“第一次看到时，你会想‘等等，这怎么可能？’”

对许多计算机科学家来说，伊兰戈这项成果的广泛意义和成果本身同样令人振奋。数十年来，证明复杂性研究者探究的深奥问题，似乎与数理逻辑的关联远甚于计算机科学其他领域。这项新成果表明，这个以难度著称的领域并非看上去那么遥不可及。如今任职于新泽西州普林斯顿高等研究院的博士后研究员伊兰戈，以及其他研究者，已经开始探索证明复杂性的思想如何助力实现其他长期被认为不可能的密码学构造。

“我认为这不会是一个孤立的成果，” 贾因说，“有时候，你只需要向人们展示门上的一道微小缝隙。”

参考资料

https://www.quantamagazine.org/how-unknowable-math-can-help-hide-secrets-20260511/

https://eprint.iacr.org/2025/1296

https://www.quantamagazine.org/how-to-prove-you-know-a-secret-without-giving-it-away-20221011/

https://www.quantamagazine.org/how-godels-proof-works-20200714/

https://link.springer.com/article/10.1007/BF00195207

https://www.cambridge.org/core/product/identifier/S0022481200041748/type/journal_article

小乐数学科普近期文章

·开放 · 友好 · 多元 · 普适 · 守拙·