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

一位研究生近期利用數(shù)學(xué)證明的復(fù)雜性，在密碼學(xué)領(lǐng)域創(chuàng)造出了一種強(qiáng)有力的新工具。另請參閱：

圖源：Kristina Armitage/Quanta Magazine

作者：Ben Brubaker（量子雜志記者）2026-5-11

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

求喜歡

引言

數(shù)學(xué)家們大部分時(shí)間都在思考那些可知的事物。但不可知的事物同樣極具吸引力。

最著名的例子或許來自邏輯學(xué)家?guī)鞝柼?哥德爾（Kurt G?del）的一條定理。哥德爾這項(xiàng)廣為人知的成果 —— 他在 1931 年發(fā)表的兩條 “不完備性定理” 之一 —— 確立了：對于任何一套合理的數(shù)學(xué)基本假設(shè)（即公理），都無法證明這套公理最終不會(huì)引發(fā)矛盾。盡管數(shù)學(xué)家們的研究工作大體照舊，但他們再也無法確定自己所遵循的規(guī)則是自洽的。

哥德爾定理問世五十多年后，密碼學(xué)家們設(shè)計(jì)出一種全新的證明方法，其中不可知性扮演了截然不同的角色。基于這種技術(shù)的證明被稱為零知識證明，它能讓即便最多疑的聽眾相信某條陳述（命題）為真，卻不透露該陳述為何為真。

這兩種不可知性分別誕生于數(shù)十年間、分屬不同領(lǐng)域，長期以來被認(rèn)為毫無關(guān)聯(lián)。如今，計(jì)算機(jī)科學(xué)家拉胡爾?伊蘭戈（Rahul Ilango）發(fā)現(xiàn)了二者之間驚人的聯(lián)系 https://eprint.iacr.org/2025/1296 。還在攻讀研究生期間，他就設(shè)計(jì)出一種新型零知識證明，其保密性源于數(shù)學(xué)的根本局限。伊蘭戈的方法突破了研究人員長期認(rèn)為無法逾越的零知識證明限制，拓展了這類證明的可能性邊界。這項(xiàng)工作還推動(dòng)研究者探索數(shù)理邏輯與密碼學(xué)之間其他引人入勝的關(guān)聯(lián)。

“我第一次看到拉胡爾的論文時(shí)，心想‘不可能，這絕對做不到’，” 加州大學(xué)洛杉磯分校的密碼學(xué)家阿米特?薩海（Amit Sahai）說，“這是一個(gè)無比精妙的全新方向。”

色盲問題

零知識證明起源于計(jì)算復(fù)雜性理論 —— 計(jì)算機(jī)科學(xué)中研究數(shù)學(xué)問題難度的分支領(lǐng)域。以一個(gè)經(jīng)典問題為例：給你三支彩色鉛筆和一張劃分出多個(gè)區(qū)域的空白地圖，你能否給地圖上色，且保證相鄰區(qū)域顏色不同？

這個(gè)問題可能極其難解。但如果有人給你展示一張上好色的地圖，你掃一眼每條邊界就能驗(yàn)證這是否是有效解。這類解可能很難找到、卻極易驗(yàn)證的問題被稱為 NP 問題。它們在密碼學(xué)中十分有用，因?yàn)檫@種 “難尋易驗(yàn)” 的解可以充當(dāng)秘密密碼。真正知道解的人能輕松證明自己知曉。

但這種簡單的密碼系統(tǒng)僅在知曉解的人愿意公開解的前提下有效。1985 年，密碼學(xué)家莎菲?戈德瓦塞爾（Shafi Goldwasser）、西爾維奧?米卡利（Silvio Micali）和查爾斯?拉克夫（Charles Rackoff）發(fā)明的零知識證明不存在這一缺陷。借助零知識證明，任何知道 NP 問題解的人都能證明自己知曉，卻無需公開解 —— 事實(shí)上，無需透露任何其他信息。

莎菲?戈德瓦塞爾（Shafi Goldwasser）（左）、西爾維奧?米卡利（Silvio Micali）（右）與查爾斯?拉克夫（Charles Rackoff）設(shè)計(jì)出一種方法，能夠證明某一命題為真，同時(shí)完全不透露其成立的緣由。

圖源：美國計(jì)算機(jī)協(xié)會(huì)ACM，2013年

“這是一個(gè)非常反直覺的概念，” 劍橋大學(xué)計(jì)算機(jī)科學(xué)家湯姆?古爾（Tom Gur）說，“在看到實(shí)例之前，這聽起來像是不可能的事。”

戈德瓦塞爾及其同事通過將數(shù)學(xué)證明重新構(gòu)想為兩方之間的交互，實(shí)現(xiàn)了這一驚人特性。以地圖三色問題的零知識證明為例：存在一個(gè) “證明者”，想要證明自己知道解。證明者秘密給地圖上色，然后遮蓋每個(gè)區(qū)域，只露出邊界。另一方 “驗(yàn)證者” 挑選一條邊界，證明者隨即揭開邊界兩側(cè)區(qū)域的遮蓋。

雙方會(huì)重復(fù)這個(gè)過程很多次。每一輪開始前，證明者都會(huì)秘密更換配色方案，防止驗(yàn)證者從不同輪次中拼湊出信息。如果證明者對每一次挑戰(zhàn)都揭露出兩種不同顏色，驗(yàn)證者最終會(huì)確信證明者掌握有效上色方案。如果證明者在虛張聲勢，經(jīng)過足夠多次嘗試后，驗(yàn)證者幾乎肯定能發(fā)現(xiàn)上色方案的漏洞。

零知識證明

某些地圖可以填充為三種顏色，且相鄰區(qū)域不得共用同一顏色。通過一種零知識證明方法，“驗(yàn)證者”能夠使“驗(yàn)證人”確信，給定的一張地圖確實(shí)可以以這種方式進(jìn)行著色，而無需透露具體的著色方法。

1、證明者在地圖上秘密涂色，然后覆蓋每個(gè)區(qū)域以隱藏顏色。

2、 驗(yàn)證者指向一個(gè)邊界，證明者揭示兩側(cè)的區(qū)域。

3、 驗(yàn)證者指向一個(gè)邊界，證明者揭示兩側(cè)的區(qū)域。

4、 驗(yàn)證者再次指向一個(gè)邊界，證明者揭示了兩側(cè)的兩個(gè)區(qū)域。

重復(fù)這一過程多次。若未發(fā)現(xiàn)任何錯(cuò)誤，驗(yàn)證者便可確信著色方案是無效的，但并不會(huì)獲取到其他任何信息。若存在錯(cuò)誤，驗(yàn)證者幾乎可以肯定能夠發(fā)現(xiàn)它。

圖源：Mark Belan / Quanta Magazine

零知識證明的交互性使其與普通數(shù)學(xué)證明截然不同 —— 普通證明可以寫在教科書里，無需驗(yàn)證者參與。直觀來看，交互性似乎是零知識證明的核心要素。直接提交書面證明的證明者，無法阻止驗(yàn)證者通讀全文、獲知自己掌握的所有信息。證明者可以加密這份文件以避免驗(yàn)證者獲取過多信息，但那樣一來驗(yàn)證者就無法確認(rèn)證明是否有效，因?yàn)樗麄儫o法向證明者質(zhì)詢。

1994年，密碼學(xué)家奧德?戈德賴希（Oded Goldreich）和亞伊爾?奧倫（Yair Oren）證明了一條定理，證實(shí)了這一直覺 https://link.springer.com/article/10.1007/BF00195207 。他們的研究結(jié)果表明：完全非交互式、且符合戈德瓦塞爾、米卡利與拉克夫所定義的零知識證明是不可能構(gòu)建的。這對那些仍抱有希望、想要打造與普通證明完全一致的零知識證明的密碼學(xué)家來說是個(gè)壞消息。

“人們當(dāng)時(shí)都說‘算了吧，這不可能實(shí)現(xiàn)’，” 約翰斯?霍普金斯大學(xué)暨日本電報(bào)電話公司研究所的密碼學(xué)家阿比謝克?賈因（Abhishek Jain）說，“要怎么突破這種不可能？”

伊蘭戈的新成果給出了答案 —— 借助另一種 “不可能”。

不可能的任務(wù)

2023年夏天，在麻省理工學(xué)院研究生三年級結(jié)束時(shí)，伊蘭戈對復(fù)雜性理論中一個(gè)晦澀的分支 ——證明復(fù)雜性產(chǎn)生了越來越濃厚的興趣。大多數(shù)復(fù)雜性理論研究者研究的是三色問題這類問題的難度（本例中即找到有效上色方案所需的步驟數(shù)）。與之相對，證明復(fù)雜性領(lǐng)域的研究者分析的是證明這些問題相關(guān)陳述的難度 （詳情參閱：以及）—— 比如 “這張?zhí)囟ǖ貓D無法正確上色” 這類陳述。他們通過衡量給定陳述的最簡證明長度來評估這種難度。

在數(shù)學(xué)中，有些陳述既無法被證明為真，也無法被證明為假。（這是哥德爾的另一條不完備性定理。）而另一些陳述原則上可證，但證明過程長到永遠(yuǎn)無法寫完。從實(shí)際應(yīng)用角度看，這些本質(zhì)上難以證明的陳述，和哥德爾提出的不可證陳述一樣，都屬于不可知范疇。

庫爾特?哥德爾（Kurt G?del）證明了部分?jǐn)?shù)學(xué)命題為真，卻無法被證明。

圖源：Alfred Eisenstaedt

研究人員通常出于研究本身的目的探究這類難證陳述，以更好地理解數(shù)學(xué)證明的邊界。但伊蘭戈猜想，這類陳述或許在密碼學(xué)中也有應(yīng)用價(jià)值。現(xiàn)代密碼學(xué)幾乎所有技術(shù)都基于解決特定問題的難度，比如地圖上色相關(guān)問題。伊蘭戈思考：如果轉(zhuǎn)而利用證明特定陳述的難度，會(huì)怎樣？這樣做或許能讓他設(shè)計(jì)出全新的密碼學(xué)技術(shù)。

“我們總會(huì)不斷撞上這些壁壘：‘為什么我們證明不了這個(gè)？為什么證明不了那個(gè)？’”IBM公司的復(fù)雜性理論學(xué)家馬爾科?卡爾莫西諾（Marco Carmosino）說，“我們能否從這種難度中獲益？”

2024年，經(jīng)過幾次失敗的嘗試后，伊蘭戈找到了一項(xiàng)適合作為其方法試驗(yàn)場的密碼學(xué)任務(wù)。他想要構(gòu)建非交互式的零知識證明。三十年前，戈德賴希和奧倫已經(jīng)證明這類證明不可能存在。但伊蘭戈意識到，“零知識” 的定義或許不止一種 —— 而那條不可能性結(jié)論僅適用于最初的定義。

這相當(dāng)顛覆認(rèn)知。第一次看到時(shí)，你會(huì)想 “等等，這怎么可能？” —— 阿米特?薩海（Amit Sahai），加州大學(xué)洛杉磯分校UCLA

要理解這個(gè)定義，不妨代入地圖上色案例中的驗(yàn)證者視角。即便在和證明者交互之前，你也能預(yù)測或模擬出有效證明的完整樣子：每一輪中，無論你選擇哪條邊界，證明者總會(huì)揭露出兩個(gè)顏色不同的區(qū)域。用密碼學(xué)家的行話來說，這種證明具備 “模擬器”，而這正是該證明屬于零知識證明的含義。

“如果我和你要進(jìn)行一段對話，但我能提前預(yù)測你要說的所有內(nèi)容，那你大概會(huì)認(rèn)同，和你交談我不會(huì)學(xué)到任何東西，” 伊蘭戈說。

戈德賴希和奧倫的不可能性結(jié)論實(shí)際表明：非交互式證明無法擁有模擬器，因此按定義，它們不可能是零知識證明。伊蘭戈希望借助證明復(fù)雜性定義一種全新的零知識概念 —— 他稱之為 “有效” 零知識 —— 這種概念不受舊不可能性結(jié)論的約束，卻和普通零知識證明同樣實(shí)用。

他新定義的核心是一個(gè)簡單的洞見：只要沒人能察覺，證明沒有模擬器也沒關(guān)系。

證明的負(fù)擔(dān)

想象你要買一把號稱牢不可破的鎖。你閱讀包裝上的小字說明，本以為會(huì)看到鎖具安全的保證，結(jié)果卻看到直白的承認(rèn)：這把鎖并不安全，隨后附帶一句承諾：即便它不安全，也沒人能證明它不安全。

乍聽之下，這像是故意歪曲宣傳無用產(chǎn)品。但如果這把鎖真的兌現(xiàn)了這個(gè)不同尋常的承諾，它實(shí)際上和可證明牢不可破的鎖一樣安全。原因如下：假設(shè)你找到了破解這把鎖的方法，那么被破解的鎖本身就構(gòu)成了它不安全的證明 —— 但如果包裝上的承諾屬實(shí)，這樣的證明是不可能存在的。換句話說，如果存在漏洞，卻不可能證明該漏洞存在，那就沒人能利用這個(gè)漏洞。

還在攻讀研究生時(shí)，拉胡爾?伊蘭戈就借助數(shù)學(xué)的局限性發(fā)明了一種新型零知識證明。

圖源：詹妮弗?克魯帕（Jennifer Krupa）

這是伊蘭戈新成果背后的核心思路。傳統(tǒng)上，要證明一份證明是零知識的，需要證明它具備模擬器。（用我們的比喻來說，這等同于證明鎖具牢不可破。）但這也意味著證明必須是交互式的。而要實(shí)現(xiàn)有效零知識，伊蘭戈轉(zhuǎn)而證明：要確保他的證明沒有模擬器是極其困難的。（也就是說，沒人能證明這把鎖可被破解。）

只要能證明這一點(diǎn)，他就能獲得零知識的全部優(yōu)勢，同時(shí)巧妙繞開交互性要求。“在現(xiàn)實(shí)生活中，幾乎所有場景下這種有效零知識都足夠用了，” 薩海說。

要理解伊蘭戈是如何做到的，我們回到地圖三色案例。如果你知道如何給地圖上色，就能寫下一條非交互式證明，證明 “這張地圖可以三色填充”。但受 1994 年不可能性結(jié)論的限制，這份證明無法擁有模擬器，因此不屬于零知識證明。

運(yùn)用伊蘭戈的新方法，你需要先改寫要證明的陳述，新增一條額外假設(shè)：“這張地圖可以三色填充 —— 假設(shè)標(biāo)準(zhǔn)數(shù)學(xué)公理中不存在能被高效找到的矛盾。” 這條額外假設(shè)通常被視為理所當(dāng)然。如果它不成立，數(shù)學(xué)就充滿矛盾，沒有任何證明可信。如果它成立（研究人員普遍如此認(rèn)為），伊蘭戈的新陳述本質(zhì)上就和原陳述等價(jià)。

但這條假設(shè)也被認(rèn)為實(shí)際上無法證明 https://www.cambridge.org/core/product/identifier/S0022481200041748/type/journal_article：原則上它或許可證，但任何證明都長到永遠(yuǎn)無法寫完。這正是證明復(fù)雜性領(lǐng)域研究者熱衷研究的哥德爾式斷言。

這也意味著閱讀證明的人無法完全排除假設(shè)不成立的可能 —— 這一點(diǎn)至關(guān)重要。具體來說，我們可能身處兩種可能的世界。第一種世界中，假設(shè)確實(shí)成立，我們就回到了原點(diǎn)：你寫下了一份非交互式證明，證明你的地圖可以三色填充，但這份證明沒有模擬器，因此不屬于零知識證明。而第二種世界中，假設(shè)不成立，我們再也無法相信數(shù)學(xué)的自洽性，正確與錯(cuò)誤的證明將無法區(qū)分；關(guān)鍵在于，在這個(gè)怪異的領(lǐng)域中，戈德賴希和奧倫的不可能性結(jié)論不再適用。任何證明 —— 無論有效或無效、交互或非交互 —— 都可以擁有模擬器。

這個(gè)看似不可能的第二種世界相當(dāng)于一種漏洞。閱讀者無法確定自己身處哪個(gè)世界 —— 盡管幾乎可以肯定是數(shù)學(xué)保持自洽的第一種世界。這反過來意味著，他們無法真正確定這份證明沒有模擬器。即便沒有交互性，這份證明依然可以是有效零知識的。伊蘭戈成功突破了這個(gè)存在數(shù)十年的不可能性結(jié)論。

其中涉及的數(shù)學(xué)巧思甚至?xí)屬Y深研究者再三審視，但邏輯完全成立。“這相當(dāng)顛覆認(rèn)知，” 薩海坦言，“第一次看到時(shí)，你會(huì)想‘等等，這怎么可能？’”

對許多計(jì)算機(jī)科學(xué)家來說，伊蘭戈這項(xiàng)成果的廣泛意義和成果本身同樣令人振奮。數(shù)十年來，證明復(fù)雜性研究者探究的深?yuàn)W問題，似乎與數(shù)理邏輯的關(guān)聯(lián)遠(yuǎn)甚于計(jì)算機(jī)科學(xué)其他領(lǐng)域。這項(xiàng)新成果表明，這個(gè)以難度著稱的領(lǐng)域并非看上去那么遙不可及。如今任職于新澤西州普林斯頓高等研究院的博士后研究員伊蘭戈，以及其他研究者，已經(jīng)開始探索證明復(fù)雜性的思想如何助力實(shí)現(xiàn)其他長期被認(rèn)為不可能的密碼學(xué)構(gòu)造。

“我認(rèn)為這不會(huì)是一個(gè)孤立的成果，” 賈因說，“有時(shí)候，你只需要向人們展示門上的一道微小縫隙。”

參考資料

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

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

版權(quán)聲明：本文首發(fā)于微信公眾號“zzllrr小樂”的專欄《小樂數(shù)學(xué)科普》。歡迎個(gè)人轉(zhuǎn)發(fā)。如需轉(zhuǎn)載，請?jiān)凇皕zllrr小樂”公眾號后臺(tái)回復(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é)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

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

查看原始文章出處

點(diǎn)擊底部一起捐

助力騰訊公益

點(diǎn)擊zzllrr小樂

公眾號主頁

右上角

置頂★加星

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