★置頂zzllrr小樂公眾號，追蹤《小樂數(shù)學(xué)科普》系列報道！

一項哥德爾不完全性（不完備性）定理在密碼學(xué)中的應(yīng)用：面向 NP 問題、無交互、無預(yù)置且具備完美可靠性的有效零知識證明。（文末有對論文作者拉胡爾?伊蘭戈 Rahul Ilango 的采訪供參考）

圖源：Sebastian Moldoveanu，Canva

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

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2026-5-12

求喜歡

拉胡爾?伊蘭戈（Rahul Ilango）在密碼學(xué)領(lǐng)域發(fā)表了一項重大概念性進展，放寬了零知識證明的協(xié)議要求 https://eprint.iacr.org/2025/1296 。

他提出的 “有效” 零知識證明，在實際應(yīng)用中匹配零知識證明的安全保障，同時無需交互過程。

為消除這種來回驗證的必要性，伊蘭戈從一個出人意料的靈感來源著手：哥德爾不完備性定理，現(xiàn)代數(shù)理邏輯中最偉大也最令人震驚的發(fā)現(xiàn)之一。

保障信息安全

在線驗證往往會泄露超出必要范圍的信息。比如你使用郵箱賬號登錄其他應(yīng)用，該郵箱平臺就會確切知曉你使用的其他平臺，進而收集你的行為與偏好數(shù)據(jù)。又比如你向貸款機構(gòu)提交信用報告以申請貸款，他們會獲取你多年的詳細財務(wù)信息。

零知識證明可實現(xiàn)在線驗證，且完全不泄露敏感信息。這種密碼學(xué)技術(shù)讓發(fā)送方向接收方證明自己掌握關(guān)鍵信息，或能證明某件事為真，卻無需透露該信息或事實的具體細節(jié)。

理論概述常以數(shù)獨謎題為例加以說明。零知識證明能讓一方向另一方證明謎題有解，同時對解法嚴(yán)格保密。接收方僅能獲知謎題可解，卻永遠無法得知真實答案。正如《科學(xué)美國人》近期一篇關(guān)于伊蘭戈此項成果的文章所斷言：“零知識證明是密碼學(xué)中最接近魔法的技術(shù)。” https://www.scientificamerican.com/article/how-effectively-zero-knowledge-proofs-could-transform-cryptography/

實際應(yīng)用更凸顯了這一方法的價值。

軟件可在完全不訪問、不存儲用戶憑證的情況下保障其安全；零知識證明是核心技術(shù)，讓軟件能驗證你知曉密碼或個人識別碼，卻無需你傳輸這些信息。

區(qū)塊鏈技術(shù)中的金融交易借助零知識證明確認(rèn)交易有效性，無需收集精確交易數(shù)據(jù)，在無中央機構(gòu)或可信第三方的情況下兼顧隱私與準(zhǔn)確性。

數(shù)字身份驗證能確認(rèn)用戶身份，比如證明是某地區(qū)居民或達到特定年齡，卻無需暴露地址、出生日期等核心個人信息。

實現(xiàn)這一功能，零知識證明依賴交互式協(xié)議。發(fā)送方（即 “證明者”）與接收方（即 “驗證者”）通信，驗證者發(fā)出挑戰(zhàn)，證明者以只有掌握秘密信息才能做出的方式回應(yīng)，驗證者再發(fā)出新挑戰(zhàn)，證明者繼續(xù)應(yīng)答。

這一過程持續(xù)至達到安全閾值。驗證者始終無法獲取秘密信息，而通過交互，證明者能證明信息真實，或讓驗證者識別出證明者在說謊。

從零知識到有效零知識

在伊蘭戈取得突破之前，數(shù)學(xué)家認(rèn)為非交互式零知識證明是不可能實現(xiàn)的，盡管這一構(gòu)想頗具研究價值。

能否設(shè)計一種安全協(xié)議，無需證明者與驗證者之間的驗證對話，就能在不泄露任何信息的前提下驗證事實？

“這是一個引人入勝的理論謎題，” 伊蘭戈表示，“與此同時，已有確鑿結(jié)論證明這無法實現(xiàn)。學(xué)界普遍認(rèn)為，零知識證明必須做出兩項核心妥協(xié)：放棄非交互性與完美可靠性。理論上，我們都接受，不存在不含挑戰(zhàn) - 應(yīng)答環(huán)節(jié)的安全零知識證明。”

但伊蘭戈并不認(rèn)同這種既定的不可能結(jié)論。“在網(wǎng)絡(luò)通信中使用交互是合理的，服務(wù)器與客戶端時刻都在通信，” 他說，“但零知識證明通過交互依賴概率的方式，與數(shù)千年來數(shù)學(xué)證明的核心概念截然不同。我想要一種不依賴交互的零知識證明。”

在這篇論文中，伊蘭戈首次提出了這種證明。他的成果 —— 被其稱為 “經(jīng)典意義上不可能實現(xiàn)的密碼學(xué)理想成果”—— 推出了無需交互的零知識證明版本。

這項成果被命名為 “有效零知識證明”，伊蘭戈的設(shè)計靈感來自高等研究院長期教員庫爾特?哥德爾（Kurt G?del），他在1931年提出的不完備性定理撼動了現(xiàn)代數(shù)學(xué)的實證主義抱負(fù)，在我們理解世界的幾乎所有方式中都留下了難以捉摸的鴻溝。

簡而言之，哥德爾的研究表明，存在絕對真理，而我們永遠無法為其提供證明。任何構(gòu)建完整、可完全驗證的數(shù)學(xué)體系的嘗試都是徒勞的。

無法證明某件事，是否能派上用場？

伊蘭戈的證明將這一原理創(chuàng)造性地應(yīng)用于密碼學(xué)。

數(shù)學(xué)家為零知識證明中的交互協(xié)議建模時，會使用模擬器，模擬證明者與驗證者之間假設(shè)但完全合理的對話過程。

伊蘭戈全新的有效零知識證明摒棄了模擬器。他證明，只需證明 “無法證明模擬器不存在” 就足夠了。

這種方法沒有直接證明某件事的可能性，而是借助哥德爾在邏輯學(xué)領(lǐng)域的深遠貢獻，讓 “不存在” 具備數(shù)學(xué)意義。模擬器無需真實存在，只要無法證明其不存在，就足以滿足幾乎所有應(yīng)用場景。

這一邏輯上的巧妙轉(zhuǎn)變，繞開了傳統(tǒng)零知識證明對交互的需求，在數(shù)十年來零知識證明的不可能結(jié)論中打開了一道優(yōu)雅的突破口。

不可能的夢想

伊蘭戈最初只是直覺認(rèn)為哥德爾定理能以全新方式發(fā)揮作用，如今這一想法已發(fā)展為一系列宏大的研究項目。

“我們已經(jīng)在探索如何攻克密碼學(xué)領(lǐng)域的其他不可能結(jié)論，” 伊蘭戈說。

例如，醫(yī)療領(lǐng)域的安全多方計算應(yīng)用是伊蘭戈當(dāng)前的研究方向之一。如果一家機器學(xué)習(xí)公司希望在不侵犯隱私、不違反健康保險流通與責(zé)任法案的前提下，用患者數(shù)據(jù)訓(xùn)練模型，就需要一種能將身份與數(shù)據(jù)分離的安全方法。該領(lǐng)域的密碼學(xué)突破有望打造出隱私保護、合法合規(guī)且值得信賴的機器學(xué)習(xí)模型，為醫(yī)療研究與診療帶來挽救生命的進步。

在攻克密碼學(xué)領(lǐng)域這類 “理想成果” 的過程中，伊蘭戈始終滿懷熱情，致力于從過往理論中發(fā)掘新潛力，將其推向未來。

“能在普林斯頓高等研究院繼續(xù)這項研究，我倍感鼓舞。這里是哥德爾本人取得諸多重大成果的地方，如今也匯聚了頂尖數(shù)學(xué)家共同攻克這些難題，” 伊蘭戈說。

附錄1：IAS采訪Rahul Ilango

Rahul Ilango（拉胡爾?伊蘭戈）

IAS普林斯頓高等研究院博士后研究員、MIT博士

圖源：IAS

拉胡爾?伊蘭戈（Rahul Ilango），數(shù)學(xué)學(xué)院成員，研究計算復(fù)雜度理論，該理論量化解決計算任務(wù)所需的資源，如時間與硬件。伊蘭戈尤其關(guān)注連接復(fù)雜度理論與其他領(lǐng)域的問題，例如密碼學(xué)與證明復(fù)雜度。他在麻省理工學(xué)院取得博士學(xué)位，博士導(dǎo)師為瑞安?威廉姆斯（Ryan Williams），后者是 2025–26 年度馮?諾依曼研究員。

請用簡短的話介紹你的研究

我以前有一段很長的介紹，后來我發(fā)現(xiàn)領(lǐng)域外的人根本聽不懂！所以現(xiàn)在我會這么說：我試圖讓算法變得更快，或者證明它們無法變得更快。其實我基本不做前一半 —— 這幾乎是為后一半做鋪墊。大多數(shù)時候，我都在論證：事實上，這個問題不可能更快解決，這已經(jīng)是最快的方式。

你在高等研究院期間的研究重點是什么？

這里有很多有趣的人，也有很多有趣的問題值得解決！我有幾個特別感興趣的具體問題，但只要能和有趣的人一起研究有趣的問題，這就是我的目標(biāo)。

在很多領(lǐng)域，真相并非絕對明確。你可以聲稱某件事是真的，但它沒有絕對的真實性。但在數(shù)學(xué)中，我們擁有確鑿的真理，這讓我感到很滿足。這也給我們設(shè)下了限制：我們只能提出有確切答案的問題。但數(shù)學(xué)的好處在于，其他領(lǐng)域會擔(dān)心，如果你不嚴(yán)肅對待研究，你的研究就不嚴(yán)肅。但因為數(shù)學(xué)有確鑿的真理，人們反而可以很輕松隨性。我很喜歡這種文化。我不知道所有數(shù)學(xué)領(lǐng)域都是如此，但理論計算機科學(xué)領(lǐng)域的氛圍確實非常包容。

奧爾?扎米爾（Or Zamir）與拉胡爾在飛鏢游戲的黑板上寫下的（有誤的）數(shù)學(xué)推導(dǎo)

圖源：Rahul Ilango

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

有一次，我和奧爾?扎米爾（Or Zamir，2021–22年度成員、2022–23年度訪問學(xué)者，數(shù)學(xué)學(xué)院）在酒吧玩飛鏢。我們突然有了個想法，但身邊沒有黑板 —— 不過我們看到了飛鏢計分板，上面還有一點粉筆痕跡。于是我們就在上面開始演算數(shù)學(xué)。我們覺得這事挺好笑的，要把公式擠在計分板的狹小空間里。而且還是在酒吧里做數(shù)學(xué)！真是一群書呆子。

我當(dāng)時拍了張照片，前幾天翻到這張照片，看了看我們當(dāng)時算的內(nèi)容，才發(fā)現(xiàn)全算錯了。我們犯了一個高中代數(shù)級別的簡單錯誤。我們還以為自己在飛鏢板上做了什么高深的研究，其實根本不是。

你對研究有什么迷信或小竅門嗎？

有一種大家常用的方法，算是一種自我催眠。每當(dāng)你試圖證明某個結(jié)論時，你都要全心全意說服自己：“這是對的，而且證明起來應(yīng)該很簡單。” 你必須完全進入這種心態(tài)。

這不是我的竅門 —— 我是從阿迪?薩莫爾（Adi Shamir，密碼學(xué)專家，圖靈獎、沃爾夫獎得主，詳情參閱）那里聽來的，我覺得甚至可以追溯到曼紐爾?布魯姆（Manuel Blum）。有時候你面對一個難題，會覺得無從下手。但如果有人在你耳邊悄悄說：“嘿，我可以告訴你一個讓這道題變簡單的辦法。”

這種 “存在簡單解法” 的心理暗示，會在心理上幫你推進研究。

你可能在試圖證明某件事是對的，或是錯的。早上你會覺得，這顯然是對的，肯定沒錯。到了下午，你又會覺得，這顯然是錯的，絕對如此。無論哪種情況，你都必須完全相信它。

有沒有高等研究院的學(xué)者（無論過去還是現(xiàn)在）對你的研究產(chǎn)生過影響？

我現(xiàn)在的很多研究，包括最近的一篇論文，都基于庫爾特?哥德爾（Kurt G?del）提出的一個非常精妙的概念。哥德爾是數(shù)學(xué)學(xué)院 1953–78 年度常任成員與教授，是1930年代起研究院的重要人物之一。他證明了一個驚人的結(jié)論：數(shù)學(xué)中存在一些真命題，我們永遠無法證明。這對某些數(shù)學(xué)觀點是致命一擊，那些觀點認(rèn)為所有真命題都可以被證明。而事實并非如此！令人困擾的是，確實存在一些無法證明的真命題。

這聽起來像是壞消息，對吧？但在我的研究中，它開始變成好消息。

我們可以用它來構(gòu)建全新的、強大的密碼系統(tǒng)。在密碼學(xué)中，通常的目標(biāo)是：你能輕松完成某件事，而對手無法輕松做到。某件事為真卻無法被證明，這一點能賦予你對手沒有的能力。

我將哥德爾的理論與阿維?維格森（Avi Wigderson，復(fù)雜度理論先驅(qū)、圖靈獎得主，詳情參閱：）在零知識證明領(lǐng)域的研究相結(jié)合。維格森是數(shù)學(xué)學(xué)院赫伯特?H?馬斯教授，他的研究令人驚嘆：任何可以被證明的事情，實際上都可以在不泄露任何信息的情況下被證明。

受研究院學(xué)者啟發(fā)完成研究后，你現(xiàn)在身處這里有什么感受？

這里有著相當(dāng)輝煌的歷史，親身感受這段歷史、漫步其中、想到這些偉人曾在這里工作，感覺有點不可思議。

有人告訴我一句攀巖界的說法：你無法選擇結(jié)果，但你可以選擇戰(zhàn)斗。我在這里的責(zé)任是什么？就是思考問題，至于能否解決，我無法控制！

能否談?wù)労献鲗δ愕难芯恳馕吨裁矗?/strong>

有一年夏天，我在谷歌實習(xí)，做的并不是我博士期間日常研究的內(nèi)容。因為是不同領(lǐng)域，我必須學(xué)習(xí)很多東西。當(dāng)時是五人團隊，我和那些精通我陌生領(lǐng)域知識的人交流，而我也懂他們不知道的內(nèi)容。

這段合作本身就很有學(xué)習(xí)價值，我們持續(xù)研究了一年多，而大部分時間里我們毫無進展。這更像是一種練習(xí)：你愿意花多長時間思考一個問題？

如果你享受思考問題的過程，那這件事就很有趣。

我剛讀博時，對密碼學(xué)并不太感興趣。后來和一群關(guān)注隱私問題的團隊合作，我們發(fā)現(xiàn)需要一些密碼學(xué)工具來解決問題。我最終學(xué)會了這些工具，我的研究工具箱一下子同時涵蓋了復(fù)雜度理論與密碼學(xué)。隨后，復(fù)雜度理論與密碼學(xué)的交叉領(lǐng)域涌現(xiàn)出各種有趣的問題，最終改變了我的博士研究方向。

附錄2：論文摘要

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

零知識證明可以證明某個事實（例如一道數(shù)獨謎題存在解法）為真，而反直覺的是，除此之外不泄露任何其他信息（比如具體的解法是什么）。這種極強的安全保障在密碼學(xué)應(yīng)用中極具價值，但也需要付出相應(yīng)代價。戈德里奇（Goldreich）與奧倫（Oren）在1994年《密碼學(xué)期刊》上給出的經(jīng)典不可能結(jié)論表明：零知識證明必然要犧牲傳統(tǒng)數(shù)學(xué)證明的兩項基本性質(zhì) —— 即完美可靠性（不存在虛假命題的有效證明）與非交互性（證明可通過單次消息完成傳輸）。

與這一不可能結(jié)論相反，本文證明：同時具備完美可靠性與無交互性的零知識證明，在有效意義上是可以實現(xiàn)的。我們通過定義并構(gòu)造一種全新且具備強適用性的零知識證明松弛版本來達成這一結(jié)果。直觀來講，經(jīng)典零知識證明的定義要求存在一個名為模擬器的對象；而本文新定義僅要求：無法從特定邏輯層面排除模擬器存在的可能性。基于這一定義，我們證明：經(jīng)典零知識證明中所有可證偽的安全性質(zhì)，都可以在無交互、無預(yù)置設(shè)置、且保持完美可靠性的前提下實現(xiàn)。這使得現(xiàn)有文獻中幾乎所有經(jīng)典零知識證明應(yīng)用，都可以剔除交互流程與預(yù)置設(shè)置；所需付出的代價相對輕微：這類應(yīng)用的安全范式由基于模擬轉(zhuǎn)為基于博弈。

本文的構(gòu)造基于庫肯德爾（Kuykendall）與詹德里（Zhandry）2020年理論密碼學(xué)會議的研究工作，依賴兩項學(xué)界長期研究且已被廣泛認(rèn)可的核心假設(shè)，同時我們證明這兩項假設(shè)也是必要條件。第一項假設(shè)是非交互證人不可區(qū)分證明的存在性，該假設(shè)可由密碼學(xué)標(biāo)準(zhǔn)前提推導(dǎo)得出。第二項是克拉伊切克（Krajícek）與普德拉格（Pudlák）1989年提出的猜想：不存在最優(yōu)證明系統(tǒng)。該猜想是證明復(fù)雜度領(lǐng)域的核心猜想之一，也是希爾伯特第二問題不可判定性在有限層面的自然對應(yīng)，進而也與哥德爾不完備性定理一脈相承。本文核心思路是利用上述假設(shè)構(gòu)造一組證明者與驗證者：系統(tǒng)中實際并不存在模擬器，但模擬器不存在這一命題，在任意強邏輯公理體系下都是不可證明的邏輯獨立命題。數(shù)學(xué)標(biāo)準(zhǔn)公理體系 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

小樂數(shù)學(xué)科普近期文章

版權(quán)聲明：本文首發(fā)于微信公眾號“zzllrr小樂”的專欄《小樂數(shù)學(xué)科普》。歡迎個人轉(zhuǎn)發(fā)。如需轉(zhuǎn)載，請在“zzllrr小樂”公眾號后臺回復(fù)“轉(zhuǎn)載”，還可通過公眾號菜單、發(fā)送郵件到zzllrr@gmail.com與我們?nèi)〉寐?lián)系。相關(guān)圖文音視頻內(nèi)容默認(rèn)遵守CC BY-NC 4.0知識共享協(xié)議，未獲作者和譯者授權(quán)，禁止用于營銷宣傳和商業(yè)目的。

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點擊底部一起捐

助力騰訊公益

點擊zzllrr小樂

公眾號主頁

右上角

置頂★加星

數(shù)學(xué)科普不迷路！