基于哥德尔不完备性定理的密码学突破——无需交互的零知识证明

一项哥德尔不完全性（不完备性）定理在密码学中的应用：面向 NP 问题、无交互、无预置且具备完美可靠性的有效零知识证明。（文末有对论文作者拉胡尔・伊兰戈 Rahul Ilango 的采访供参考）

图源：Sebastian Moldoveanu，Canva

作者：IAS（普林斯顿高等研究院）2026-4

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

拉胡尔・伊兰戈（Rahul Ilango）在密码学领域发表了一项重大概念性进展，放宽了零知识证明的协议要求 https://eprint.iacr.org/2025/1296 。

他提出的 “有效” 零知识证明，在实际应用中匹配零知识证明的安全保障，同时无需交互过程。

为消除这种来回验证的必要性，伊兰戈从一个出人意料的灵感来源着手：哥德尔不完备性定理，现代数理逻辑中最伟大也最令人震惊的发现之一。

保障信息安全

在线验证往往会泄露超出必要范围的信息。比如你使用邮箱账号登录其他应用，该邮箱平台就会确切知晓你使用的其他平台，进而收集你的行为与偏好数据。又比如你向贷款机构提交信用报告以申请贷款，他们会获取你多年的详细财务信息。

零知识证明可实现在线验证，且完全不泄露敏感信息。这种密码学技术让发送方向接收方证明自己掌握关键信息，或能证明某件事为真，却无需透露该信息或事实的具体细节。

理论概述常以数独谜题为例加以说明。零知识证明能让一方向另一方证明谜题有解，同时对解法严格保密。接收方仅能获知谜题可解，却永远无法得知真实答案。正如《科学美国人》近期一篇关于伊兰戈此项成果的文章所断言：“零知识证明是密码学中最接近魔法的技术。” https://www.scientificamerican.com/article/how-effectively-zero-knowledge-proofs-could-transform-cryptography/

实际应用更凸显了这一方法的价值。

软件可在完全不访问、不存储用户凭证的情况下保障其安全；零知识证明是核心技术，让软件能验证你知晓密码或个人识别码，却无需你传输这些信息。

区块链技术中的金融交易借助零知识证明确认交易有效性，无需收集精确交易数据，在无中央机构或可信第三方的情况下兼顾隐私与准确性。

数字身份验证能确认用户身份，比如证明是某地区居民或达到特定年龄，却无需暴露地址、出生日期等核心个人信息。

实现这一功能，零知识证明依赖交互式协议。发送方（即 “证明者”）与接收方（即 “验证者”）通信，验证者发出挑战，证明者以只有掌握秘密信息才能做出的方式回应，验证者再发出新挑战，证明者继续应答。

这一过程持续至达到安全阈值。验证者始终无法获取秘密信息，而通过交互，证明者能证明信息真实，或让验证者识别出证明者在说谎。

从零知识到有效零知识

在伊兰戈取得突破之前，数学家认为非交互式零知识证明是不可能实现的，尽管这一构想颇具研究价值。

能否设计一种安全协议，无需证明者与验证者之间的验证对话，就能在不泄露任何信息的前提下验证事实？

“这是一个引人入胜的理论谜题，” 伊兰戈表示，“与此同时，已有确凿结论证明这无法实现。学界普遍认为，零知识证明必须做出两项核心妥协：放弃非交互性与完美可靠性。理论上，我们都接受，不存在不含挑战 - 应答环节的安全零知识证明。”

但伊兰戈并不认同这种既定的不可能结论。“在网络通信中使用交互是合理的，服务器与客户端时刻都在通信，” 他说，“但零知识证明通过交互依赖概率的方式，与数千年来数学证明的核心概念截然不同。我想要一种不依赖交互的零知识证明。”

在这篇论文中，伊兰戈首次提出了这种证明。他的成果 —— 被其称为 “经典意义上不可能实现的密码学理想成果”—— 推出了无需交互的零知识证明版本。

这项成果被命名为 “有效零知识证明”，伊兰戈的设计灵感来自高等研究院长期教员库尔特・哥德尔（Kurt Gödel），他在1931年提出的不完备性定理撼动了现代数学的实证主义抱负，在我们理解世界的几乎所有方式中都留下了难以捉摸的鸿沟。

简而言之，哥德尔的研究表明，存在绝对真理，而我们永远无法为其提供证明。任何构建完整、可完全验证的数学体系的尝试都是徒劳的。

无法证明某件事，是否能派上用场？

伊兰戈的证明将这一原理创造性地应用于密码学。

数学家为零知识证明中的交互协议建模时，会使用模拟器，模拟证明者与验证者之间假设但完全合理的对话过程。

伊兰戈全新的有效零知识证明摒弃了模拟器。他证明，只需证明 “无法证明模拟器不存在” 就足够了。

这种方法没有直接证明某件事的可能性，而是借助哥德尔在逻辑学领域的深远贡献，让 “不存在” 具备数学意义。模拟器无需真实存在，只要无法证明其不存在，就足以满足几乎所有应用场景。

这一逻辑上的巧妙转变，绕开了传统零知识证明对交互的需求，在数十年来零知识证明的不可能结论中打开了一道优雅的突破口。

不可能的梦想

伊兰戈最初只是直觉认为哥德尔定理能以全新方式发挥作用，如今这一想法已发展为一系列宏大的研究项目。

“我们已经在探索如何攻克密码学领域的其他不可能结论，” 伊兰戈说。

例如，医疗领域的安全多方计算应用是伊兰戈当前的研究方向之一。如果一家机器学习公司希望在不侵犯隐私、不违反健康保险流通与责任法案的前提下，用患者数据训练模型，就需要一种能将身份与数据分离的安全方法。该领域的密码学突破有望打造出隐私保护、合法合规且值得信赖的机器学习模型，为医疗研究与诊疗带来挽救生命的进步。

在攻克密码学领域这类 “理想成果” 的过程中，伊兰戈始终满怀热情，致力于从过往理论中发掘新潜力，将其推向未来。

“能在普林斯顿高等研究院继续这项研究，我倍感鼓舞。这里是哥德尔本人取得诸多重大成果的地方，如今也汇聚了顶尖数学家共同攻克这些难题，” 伊兰戈说。

附录1：IAS采访Rahul Ilango

Rahul Ilango（拉胡尔・伊兰戈）

IAS普林斯顿高等研究院博士后研究员、MIT博士

图源：IAS

拉胡尔・伊兰戈（Rahul Ilango），数学学院成员，研究计算复杂度理论，该理论量化解决计算任务所需的资源，如时间与硬件。伊兰戈尤其关注连接复杂度理论与其他领域的问题，例如密码学与证明复杂度。他在麻省理工学院取得博士学位，博士导师为瑞安・威廉姆斯（Ryan Williams），后者是 2025–26 年度冯・诺依曼研究员。

请用简短的话介绍你的研究

我以前有一段很长的介绍，后来我发现领域外的人根本听不懂！所以现在我会这么说：我试图让算法变得更快，或者证明它们无法变得更快。其实我基本不做前一半 —— 这几乎是为后一半做铺垫。大多数时候，我都在论证：事实上，这个问题不可能更快解决，这已经是最快的方式。

你在高等研究院期间的研究重点是什么？

这里有很多有趣的人，也有很多有趣的问题值得解决！我有几个特别感兴趣的具体问题，但只要能和有趣的人一起研究有趣的问题，这就是我的目标。

在很多领域，真相并非绝对明确。你可以声称某件事是真的，但它没有绝对的真实性。但在数学中，我们拥有确凿的真理，这让我感到很满足。这也给我们设下了限制：我们只能提出有确切答案的问题。但数学的好处在于，其他领域会担心，如果你不严肃对待研究，你的研究就不严肃。但因为数学有确凿的真理，人们反而可以很轻松随性。我很喜欢这种文化。我不知道所有数学领域都是如此，但理论计算机科学领域的氛围确实非常包容。

奥尔・扎米尔（Or Zamir）与拉胡尔在飞镖游戏的黑板上写下的（有误的）数学推导

图源：Rahul Ilango

你做研究的最不寻常的地方是哪里？

有一次，我和奥尔・扎米尔（Or Zamir，2021–22年度成员、2022–23年度访问学者，数学学院）在酒吧玩飞镖。我们突然有了个想法，但身边没有黑板 —— 不过我们看到了飞镖计分板，上面还有一点粉笔痕迹。于是我们就在上面开始演算数学。我们觉得这事挺好笑的，要把公式挤在计分板的狭小空间里。而且还是在酒吧里做数学！真是一群书呆子。

我当时拍了张照片，前几天翻到这张照片，看了看我们当时算的内容，才发现全算错了。我们犯了一个高中代数级别的简单错误。我们还以为自己在飞镖板上做了什么高深的研究，其实根本不是。

你对研究有什么迷信或小窍门吗？

有一种大家常用的方法，算是一种自我催眠。每当你试图证明某个结论时，你都要全心全意说服自己：“这是对的，而且证明起来应该很简单。” 你必须完全进入这种心态。

这不是我的窍门 —— 我是从阿迪・萨莫尔（Adi Shamir，密码学专家，图灵奖、沃尔夫奖得主，详情参阅小乐数学科普：2024年Wolf沃尔夫奖数学奖得主出炉：诺加·阿隆（Noga Alon）、阿迪·萨莫尔（Adi Shamir））那里听来的，我觉得甚至可以追溯到曼纽尔・布鲁姆（Manuel Blum）。有时候你面对一个难题，会觉得无从下手。但如果有人在你耳边悄悄说：“嘿，我可以告诉你一个让这道题变简单的办法。”

这种 “存在简单解法” 的心理暗示，会在心理上帮你推进研究。

你可能在试图证明某件事是对的，或是错的。早上你会觉得，这显然是对的，肯定没错。到了下午，你又会觉得，这显然是错的，绝对如此。无论哪种情况，你都必须完全相信它。

有没有高等研究院的学者（无论过去还是现在）对你的研究产生过影响？

我现在的很多研究，包括最近的一篇论文，都基于库尔特・哥德尔（Kurt Gödel）提出的一个非常精妙的概念。哥德尔是数学学院 1953–78 年度常任成员与教授，是1930年代起研究院的重要人物之一。他证明了一个惊人的结论：数学中存在一些真命题，我们永远无法证明。这对某些数学观点是致命一击，那些观点认为所有真命题都可以被证明。而事实并非如此！令人困扰的是，确实存在一些无法证明的真命题。

这听起来像是坏消息，对吧？但在我的研究中，它开始变成好消息。

我们可以用它来构建全新的、强大的密码系统。在密码学中，通常的目标是：你能轻松完成某件事，而对手无法轻松做到。某件事为真却无法被证明，这一点能赋予你对手没有的能力。

我将哥德尔的理论与阿维・维格森（Avi Wigderson，复杂度理论先驱、图灵奖得主，详情参阅：小乐数学科普：复杂性理论先驱艾维·维格森 Avi Wigderson荣获图灵奖——译自Quanta Magazine量子杂志）在零知识证明领域的研究相结合。维格森是数学学院赫伯特・H・马斯教授，他的研究令人惊叹：任何可以被证明的事情，实际上都可以在不泄露任何信息的情况下被证明。

受研究院学者启发完成研究后，你现在身处这里有什么感受？

这里有着相当辉煌的历史，亲身感受这段历史、漫步其中、想到这些伟人曾在这里工作，感觉有点不可思议。

有人告诉我一句攀岩界的说法：你无法选择结果，但你可以选择战斗。我在这里的责任是什么？就是思考问题，至于能否解决，我无法控制！

能否谈谈合作对你的研究意味着什么？

有一年夏天，我在谷歌实习，做的并不是我博士期间日常研究的内容。因为是不同领域，我必须学习很多东西。当时是五人团队，我和那些精通我陌生领域知识的人交流，而我也懂他们不知道的内容。

这段合作本身就很有学习价值，我们持续研究了一年多，而大部分时间里我们毫无进展。这更像是一种练习：你愿意花多长时间思考一个问题？

如果你享受思考问题的过程，那这件事就很有趣。

我刚读博时，对密码学并不太感兴趣。后来和一群关注隐私问题的团队合作，我们发现需要一些密码学工具来解决问题。我最终学会了这些工具，我的研究工具箱一下子同时涵盖了复杂度理论与密码学。随后，复杂度理论与密码学的交叉领域涌现出各种有趣的问题，最终改变了我的博士研究方向。

附录2：论文摘要

https://eprint.iacr.org/2025/1296 （论文完整版PDF可下载）

零知识证明可以证明某个事实（例如一道数独谜题存在解法）为真，而反直觉的是，除此之外不泄露任何其他信息（比如具体的解法是什么）。这种极强的安全保障在密码学应用中极具价值，但也需要付出相应代价。戈德里奇（Goldreich）与奥伦（Oren）在1994年《密码学期刊》上给出的经典不可能结论表明：零知识证明必然要牺牲传统数学证明的两项基本性质 —— 即完美可靠性（不存在虚假命题的有效证明）与非交互性（证明可通过单次消息完成传输）。

与这一不可能结论相反，本文证明：同时具备完美可靠性与无交互性的零知识证明，在有效意义上是可以实现的。我们通过定义并构造一种全新且具备强适用性的零知识证明松弛版本来达成这一结果。直观来讲，经典零知识证明的定义要求存在一个名为模拟器的对象；而本文新定义仅要求：无法从特定逻辑层面排除模拟器存在的可能性。基于这一定义，我们证明：经典零知识证明中所有可证伪的安全性质，都可以在无交互、无预置设置、且保持完美可靠性的前提下实现。这使得现有文献中几乎所有经典零知识证明应用，都可以剔除交互流程与预置设置；所需付出的代价相对轻微：这类应用的安全范式由基于模拟转为基于博弈。

本文的构造基于库肯德尔（Kuykendall）与詹德里（Zhandry）2020年理论密码学会议的研究工作，依赖两项学界长期研究且已被广泛认可的核心假设，同时我们证明这两项假设也是必要条件。第一项假设是非交互证人不可区分证明的存在性，该假设可由密码学标准前提推导得出。第二项是克拉伊切克（Krajícek）与普德拉格（Pudlák）1989年提出的猜想：不存在最优证明系统。该猜想是证明复杂度领域的核心猜想之一，也是希尔伯特第二问题不可判定性在有限层面的自然对应，进而也与哥德尔不完备性定理一脉相承。本文核心思路是利用上述假设构造一组证明者与验证者：系统中实际并不存在模拟器，但模拟器不存在这一命题，在任意强逻辑公理体系下都是不可证明的逻辑独立命题。数学标准公理体系 ZFC 便是这类逻辑体系之一。

参考资料

https://mathinstitutes.org/highlights/a-cryptography-breakthrough-rooted-in-godels-incompleteness-theorem

https://www.ias.edu/ideas/how-prove-anything-qa-rahul-ilango

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

https://www.scientificamerican.com/article/how-effectively-zero-knowledge-proofs-could-transform-cryptography/

Goldreich, Oded, Silvio Micali, and Avi Wigderson. “Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems.” Journal of the ACM, vol. 38, no. 3, 1991, pp. 691–729. https://doi.org/10.1145/116825.116852

Goldreich, Oded, and Yair Oren. “Definitions and Properties of Zero-Knowledge Proof Systems.” Journal of Cryptology, vol. 7, no. 1, 1994, pp. 1–32. https://doi.org/10.1007/BF00195207

Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. “The Knowledge Complexity of Interactive Proof-Systems.” Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC ’85), ACM, 1985, pp. 291–304. https://doi.org/10.1145/22145.22178