内容来源：https://www.quantamagazine.org/how-unknowable-math-can-help-hide-secrets-20260511/

内容总结：

不可思议的数学如何帮助隐藏秘密

数学家发现“不可知性”的惊人联系

数学家用大部分时间思考可知之物，但不可知之物同样引人入胜。近日，计算机科学家拉胡尔·伊兰戈发现了两种看似毫不相干的“不可知性”之间的惊人联系，为密码学开辟了全新方向。

从哥德尔不完备定理到零知识证明

最著名的不可知性例子来自逻辑学家库尔特·哥德尔于1931年提出的“不完备定理”。该定理表明，对于任何合理的数学公理体系，都无法证明这些公理最终不会导致矛盾。这一发现动摇了数学家对数学体系自洽性的绝对信心。

五十多年后，密码学家创造出一种革命性的证明方法——“零知识证明”。这种技术能够在完全不透露具体信息的情况下，让任何人相信某个命题为真。这听起来似乎不可能，但通过证明者与验证者之间的互动，这一方法得以实现。

破解长期存在的难题

1994年，密码学家奥德·戈德赖希和亚伊尔·奥伦证明了一个定理：完全非交互式的零知识证明是不可能的。这一结论让许多密码学家感到绝望。

然而，当时还是麻省理工学院研究生的伊兰戈发现，可以通过利用数学本身“难以证明”的特性来绕过这一限制。他提出的“有效零知识”概念，巧妙绕过了传统定义中的不可能性。

巧妙的概念转换

伊兰戈的核心洞察是：一个证明即使没有模拟器（传统零知识证明的必要条件），只要没人能证明它没有模拟器，就同样有效。

他通过在待证明陈述中添加一个额外假设来实现这一目标：“假设在标准数学公理中不存在有效的矛盾。”这个假设被普遍认为是真的，但如果为假，则整个数学体系都将崩溃。关键在于，这个假设本身极难证明——即使原则上可以证明，所需的证明长度也远超实际可能性。

现实意义与未来展望

“这种‘有效零知识’在现实场景中几乎总是足够好用，”加州大学洛杉矶分校密码学家阿米特·萨海表示。

这一发现不仅解决了长期存在的理论难题，还暗示了证明复杂度理论这一深奥领域可能为密码学带来更多突破。约翰霍普金斯大学的阿比谢克·杰恩说：“有时你只需要给人看门缝里透出的一丝光亮。”

中文翻译：

未知数学如何助力秘密隐藏
引言
数学家多数时间都在思考可知之事，但未知之物同样引人入胜。
最著名的例子或许来自逻辑学家库尔特·哥德尔的一个定理。哥德尔的重大成果——他于1931年发表的两条“不完备性定理”之一——证明：对于任何一套合理的数学基本假设（即公理），都不可能证明这些公理最终不会导致矛盾。尽管数学家们仍像往常一样继续研究，但他们再也无法确信自己的规则是自洽的。

在哥德尔定理问世50多年后，密码学家设计出一种全新的证明方法，其中未知性扮演了截然不同的角色。基于这种技术（称为零知识证明）的证明，即使面对最怀疑的听众，也能让他们相信某个陈述为真，而无需揭示其为何为真。

这两种源于不同时代、不同领域的未知性，长期以来被认为毫无关联。如今，计算机科学家拉胡尔·伊兰戈在它们之间建立了一种惊人的联系。还在读研究生时，他便设计出一种新型零知识证明，其保密性源于数学的根本局限。伊兰戈的方法绕过了研究人员曾认为无法克服的零知识证明的局限性，拓展了此类证明的可能性边界。这项研究还促使研究人员探索数理逻辑与密码学之间其他耐人寻味的联系。

“我第一次看到拉胡尔的论文时，心里想：‘不，这绝不可能，’”加州大学洛杉矶分校的密码学家阿米特·萨海说。“这真是一个令人难以置信的新方向。”

色盲
零知识证明源于计算复杂性理论，这是计算机科学中研究数学问题难度的子领域。在一个经典问题中，你拿到三支彩色铅笔和一张分为多个区域的空白地图。你能在不给相邻区域涂相同颜色的情况下给地图上色吗？

这个问题可能极其困难。但如果有人给你看一张已上色的地图，你可以检查每条边界，看是否满足有效解。像这样答案难找但易验证的问题被称为NP问题。它们在密码学中很有用，因为这些难找易验的解可以作为秘密密码。任何真正知道解的人都能轻松证明这一点。

但这种简单的密码系统只有在知道解的人愿意揭示它时才有效。1985年由密码学家莎菲·戈德瓦塞尔、西尔维奥·米卡利和查尔斯·拉克夫发明的零知识证明则没有这一缺陷。利用零知识证明，任何知道NP问题解的人都可以在不泄露解的情况下证明它——事实上，不泄露任何其他信息。

“这是一个非常反直觉的概念，”剑桥大学的计算机科学家汤姆·古尔说。“直到你看到一个例子，它听起来就像是不可能的事。”

戈德瓦塞尔和她的同事们通过将数学证明重新构想为两方之间的互动，实现了这一引人注目的特性。例如，在三色问题的零知识证明中，有一个“证明者”想证明自己知道一个解。他秘密给地图上色，然后覆盖每个区域，只露出边界。另一方“验证者”选择一条边界，证明者随后揭开两侧的区域。

双方重复这一过程多次。每轮开始前，证明者秘密更改配色方案，以防验证者从不同轮次拼凑出信息片段。如果证明者对每次挑战都显示两种不同的颜色，验证者最终会相信证明者知道一个有效的着色方案。如果证明者在虚张声势，验证者在足够多次猜测后几乎肯定会发现着色中的破绽。

零知识证明的互动性使其与普通数学证明截然不同——普通证明可以写在教科书里，无需验证者任何输入。直观上，互动性似乎是零知识证明的必要元素。一个单纯递交书面文件的证明者，无法阻止验证者检查全部内容并了解证明者所知的一切。证明者可以对文件加密以防验证者获知过多信息，但这样一来，验证者就无法确认证明是否有效，因为他们无法质询证明者。

1994年，密码学家奥德·戈德赖希和耶尔·奥伦证明了一个定理，证实了这一直觉。他们的结果表明，不可能构造出完全非互动的证明，同时满足戈德瓦塞尔、米卡利和拉克夫对零知识的定义。这对曾寄希望于零知识证明能与普通证明别无二致的密码学家来说是个坏消息。

“人们只能说：‘算了，这事成不了，’”约翰霍普金斯大学和NTT Research的密码学家阿比谢克·贾因说。“你怎么可能克服一个不可能性？”

伊兰戈的新成果展示了如何做到——通过利用另一种不可能性。

不可能的任务
2023年夏天，在麻省理工学院研究生第三年结束时，伊兰戈对复杂性理论中一个名为“证明复杂性”的冷僻子领域越来越感兴趣。大多数复杂性理论家研究像三色问题这样的问题有多难（在这类问题中，即找到有效着色需要多少步骤）。相比之下，在证明复杂性中，研究人员分析的是证明关于这些问题的陈述的难度——比如“没有方法能正确给这张特定地图上色”这样的陈述。他们通过衡量给定陈述的最简单可能证明的长度来评估这种难度。

在数学中，有些陈述既无法被证明为真，也无法被证明为假。（这是哥德尔另一条不完备性定理。）然而，其他一些陈述原则上可以证明，但证明过程可能长得永远无法写完。出于所有实际目的，这些本质上难以证明的陈述与哥德尔指出的不可证明的陈述同样不可知。

研究人员通常为了研究本身而探讨这类难以证明的陈述，以更好地理解数学证明的极限。但伊兰戈怀疑这些陈述也可能在密码学中有应用。现代密码学的几乎所有技术都基于解决特定问题的难度，比如给地图着色的问题。伊兰戈想，他是否可以转而利用证明特定陈述的难度？这样做或许能让他发明出新的密码技术。

“我们发现自己不断撞上‘为什么我们无法证明这个？为什么我们无法证明那个？’这些墙，”IBM的复杂性理论家马可·卡莫西诺说。“我们能否从这种困难中获益？”

2024年，经历了几次失败的尝试后，伊兰戈确定了密码学中一项具体任务，可作为其方法的试验场。他想构建非互动的零知识证明。三十年前，戈德赖希和奥伦已经证明此类证明是不可能的。但伊兰戈意识到， “零知识”可能有不止一种定义方式——而那个不可能性结果只适用于最初的定义。

要理解那个定义，可以把自己想象成地图着色例子中的验证者。即使在和证明者互动之前，你也可以预测（或模拟）一个有效证明会是什么样子：每一轮，无论你选择哪条边界，证明者总会显示两种不同颜色的区域。用密码学家的术语来说，这个证明有一个“模拟器”，这就是证明是零知识的意义所在。

“如果你我要进行一场对话，但我在事前就能预测出你要说的一切，那你大概会同意，和你交谈我学不到任何东西，”伊兰戈说。

戈德赖希和奥伦的不可能性结果实际上说的是：非互动证明不可能有模拟器，因此根据定义，它们不可能是零知识的。伊兰戈希望利用证明复杂性来定义一种新的零知识概念——他称之为“有效”零知识——这种概念不受旧不可能性结果的约束，但和普通零知识一样有用。

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

举证责任
想象你即将购买一把号称牢不可破的锁。你阅读包装上的细则，期望找到锁是安全的保证，却发现坦然承认这把锁并不安全，接着是一个承诺：尽管它不安全，但没人能证明它不安全。

起初，这听起来像是一种故意反常地推销无用产品的方式。但如果这把锁真的兑现了这个不寻常的承诺，它实际上和一把可证明牢不可破的锁一样安全。要理解原因，想象你找到了开锁的方法。那么这把被打开的锁本身就可以作为它不安全的证明——但如果包装上的承诺是正确的，这样的证明是不可能的。换句话说，如果漏洞存在，但无法证明它存在，那就没法利用它。

这就是伊兰戈新成果的基本思想。传统上，要证明一个证明是零知识的，你需要展示它有一个模拟器。（在我们的比喻中，这相当于证明这把锁是牢不可破的。）但这同时也意味着这个证明必须是互动的。为了获得有效零知识，伊兰戈转而希望证明：要保证他的证明没有模拟器是极其困难的。（也就是说，没有办法证明这把锁是可以被打开的。）

如果他能做到这一点，就能在巧妙绕过互动性要求的同时，获得零知识的所有好处。“实际上很难想象任何现实生活中的情况，这种有效零知识会不够用，”萨海说。

要理解伊兰戈如何做到这一点，让我们回到三色问题的例子。如果你知道如何给地图上色，你可以写下对陈述“这张地图可以用三种颜色着色”的非互动证明。但由于1994年的不可能性结果，这个证明不可能有模拟器，因此不可能是零知识的。

使用伊兰戈的新方法，你会先改写你想证明的陈述，添加一个额外的假设：“这张地图可以用三种颜色着色——假设没有有效方法能在标准数学公理中找到矛盾。”这个额外假设通常被视作理所当然。如果它是假的，那么数学就充满了矛盾，没有证明是可信的。如果它是真的（研究人员普遍相信如此），那么伊兰戈的新陈述本质上与原陈述等价。

但这个假设也被认为实际上不可能证明：它原则上或许可证明，但任何证明都会长到永远无法写下。这使得它成为证明复杂性研究者喜欢研究的那种哥德尔式断言。

这也意味着证明的读者无法完全排除该假设为假的可能性——这具有重要意义。特别是，它意味着我们可能生活在一个可能的世界中。在第一个世界中，假设确实为真，我们回到原点：你写下一个非互动证明，证明你的地图可以用三种颜色着色，但这个证明没有模拟器，因此不可能是零知识的。但在第二个世界中，假设为假，我们不能再相信数学是一致的。无法区分正确证明与错误证明；关键在于，在这个奇异领域里，戈德赖希和奥伦的不可能性结果不再适用。任何证明——无论有效无效、互动还是非互动——都可以有一个模拟器。

这个不太可能的第二个世界起到了一种漏洞的作用。读者无法确切知道自己生活在哪个世界——尽管几乎肯定是第一个世界，在那里数学仍然是安全的。这反过来意味着他们实际上无法确信这个证明没有模拟器。这个证明仍然可以是有效的零知识，尽管没有互动性。伊兰戈成功避开了那个存在数十年的不可能性结果。

其中涉及的数学巧思甚至会让经验丰富的研究者再三审视，但逻辑是成立的。“这相当烧脑，”萨海承认。“第一次看到它时，你会想：‘等等，什么？’”

对许多计算机科学家而言，伊兰戈成果更广泛的意义与其成果本身一样令人兴奋。几十年来，证明复杂性研究者一直在研究那些似乎与数理逻辑关系更密切、而非与计算机科学其他领域更相关的深奥问题。这项新研究表明，这个出了名困难的领域并不像看起来那么遥远。伊兰戈（现为新泽西州普林斯顿高等研究院的博士后研究员）和其他人已经开始探索如何利用证明复杂性的思想来实现其他长期被认为不可能的密码学构造。

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

英文来源：

How Unknowable Math Can Help Hide Secrets
Introduction
Mathematicians spend most of their time thinking about what’s knowable. But the unknowable can be just as compelling.
Perhaps the most famous example comes from a theorem by the logician Kurt Gödel. Gödel’s celebrated result — one of two “incompleteness theorems” he published in 1931 — established that for any reasonable set of basic mathematical assumptions, called axioms, it’s impossible to prove that the axioms won’t eventually lead to contradictions. Though mathematicians continued their research much as they had before, they would never again be certain that their rules were self-consistent.
More than 50 years after Gödel’s theorem, cryptographers devised a radical new proof method in which unknowability played a very different role. Proofs based on this technique, called zero-knowledge proofs, can convince even the most skeptical audience that a statement is true without revealing why it’s true.
These two flavors of unknowability, which originated decades apart and in different fields, were long considered completely unrelated. Now the computer scientist Rahul Ilango has established a striking connection between them. While still a graduate student, he devised a new type of zero-knowledge proof in which secrecy stems from the fundamental limits of math. Ilango’s approach gets around limitations of zero-knowledge proofs that researchers have long thought insurmountable, pushing the boundaries of what such a proof can be. The work has also spurred researchers to explore other intriguing links between mathematical logic and cryptography.
“When I first saw Rahul’s paper, I was like, ‘No, there’s no way,’” said Amit Sahai, a cryptographer at the University of California, Los Angeles. “This is just an incredibly cool new direction.”
Color Blindness
Zero-knowledge proofs have their roots in computational complexity theory, the subfield of computer science that studies the difficulty of mathematical problems. In one classic problem, you’re given three colored pencils and a blank map divided into many regions. Can you color in the map without assigning the same color to two neighboring regions?
This problem can be fiendishly hard. But if someone shows you a colored map, you can glance at each border to check whether it’s a valid solution. Problems like this, whose solutions may be hard to find but are always easy to verify, are called NP problems. They’re useful in cryptography because those hard-to-find, easy-to-check solutions can serve as secret passwords. Anyone who actually knows the solution can easily prove it.
But this simple password system only works if the person who knows the solution is willing to reveal it. Zero-knowledge proofs, invented in 1985 by the cryptographers Shafi Goldwasser, Silvio Micali, and Charles Rackoff, don’t have this drawback. Using a zero-knowledge proof, anyone who knows a solution to an NP problem can prove it without revealing the solution — indeed, without revealing any other information whatsoever.
“It’s a very counterintuitive notion,” said Tom Gur, a computer scientist at the University of Cambridge. “Until you see an example, it sounds like something which is impossible.”
Goldwasser and her colleagues achieved this striking property by reimagining mathematical proof as an interaction between two parties. In a zero-knowledge proof for the three-coloring problem, for instance, there’s a “prover,” who wants to show that they know a solution. They secretly color the map, then cover each region so that only the borders are visible. The other party, the “verifier,” chooses a border. The prover then uncovers the regions on either side.
The two players repeat this process many times. Before each round, the prover secretly changes the color scheme, to prevent the verifier from piecing together bits of information from different rounds. If the prover reveals two different colors in response to every challenge, the verifier will eventually be convinced that the prover knows a valid coloring. If the prover is bluffing, the verifier will almost certainly find a flaw in the coloring after enough guesses.
The interactive character of zero-knowledge proofs makes them strikingly different from ordinary mathematical proofs, which can be written down in a textbook without any input from a verifier. Intuitively, interactivity seems like an essential element of a zero-knowledge proof. A prover who simply hands over a written document can’t stop the verifier from examining the whole thing and learning everything the prover knows. The prover could encrypt that document to prevent the verifier from learning too much, but in that case the verifier won’t be able to confirm that the proof is valid, since they can’t interrogate the prover.
In 1994, the cryptographers Oded Goldreich and Yair Oren proved a theorem that confirmed this intuition. Their result established that it’s impossible to construct a completely noninteractive proof that meets Goldwasser, Micali, and Rackoff’s definition of zero knowledge. It was bad news for cryptographers who’d held out hope for zero-knowledge proofs that were otherwise identical to ordinary ones.
“People just said, ‘Forget it, it’s not going to happen,’” said Abhishek Jain, a cryptographer at Johns Hopkins University and NTT Research. “How can you overcome an impossibility?”
Ilango’s new result shows how — by harnessing a different kind of impossibility.
Mission Impossible
In the summer of 2023, at the end of his third year of graduate school at the Massachusetts Institute of Technology, Ilango was growing increasingly interested in an arcane subfield of complexity theory called proof complexity. Most complexity theorists study how hard problems like three-coloring are (in this case, how many steps are needed to find a valid coloring). In proof complexity, by contrast, researchers analyze the difficulty of proving statements about these problems — statements like “There’s no way to properly color this specific map.” They gauge this difficulty by measuring the length of the simplest possible proof of a given statement.
In math, some statements cannot be proved either true or false. (This is Gödel’s other incompleteness theorem.) Other statements, however, might be provable in principle, but only with proofs that are too long to ever write down. For all practical purposes, these intrinsically hard-to-prove statements are just as unknowable as the unprovable statements that Gödel identified.
Researchers usually study such hard-to-prove statements for their own sake, to better understand the limits of mathematical proof. But Ilango suspected that these statements might also have applications in cryptography. Nearly all techniques in modern cryptography are based on the difficulty of solving specific problems, like ones about coloring maps. What if, Ilango wondered, he could exploit the difficulty of proving specific statements instead? Doing so might allow him to concoct new cryptographic techniques.
“We find ourselves constantly slamming into these walls of ‘Why can’t we prove this? Why can’t we prove that?’” said Marco Carmosino, a complexity theorist at IBM. “Can we benefit from that kind of hardness?”
In 2024, after a few false starts, Ilango identified a specific task in cryptography that could serve as a test bed for his approach. He wanted to build zero-knowledge proofs that weren’t interactive. Thirty years earlier, Goldreich and Oren had established that such proofs are impossible. But Ilango realized that there might be more than one way to define “zero knowledge” — and that the impossibility result only applied to the original definition.
To understand that definition, put yourself in the position of the verifier in the map-coloring example. Even before you interact with the prover, you can predict, or simulate, exactly what a valid proof will look like: Each round, the prover will always reveal two differently colored regions, no matter which border you choose. In cryptographers’ lingo, this proof has a “simulator,” and that’s what it means for the proof to be zero knowledge.
“If you and I were going to have a conversation, but I could predict in advance everything that you were going to say, then you’d probably agree that I’m not going to learn anything by talking to you,” Ilango said.
What Goldreich and Oren’s impossibility result actually said was that noninteractive proofs can’t have simulators, and therefore, by definition, they can’t be zero knowledge. Ilango hoped to use proof complexity to define a new notion of zero knowledge — what he called “effective” zero knowledge — that would not be subject to the old impossibility result but would still be just as useful as ordinary zero knowledge.
At the heart of his new definition was a simple insight: It’s OK if a proof doesn’t have a simulator, as long as nobody can tell.
Burden of Proof
Imagine you’re about to buy a lock that’s famously unbreakable. You read the fine print on the package, expecting to find a guarantee that the lock is secure. Instead you find a frank admission that the lock is not secure, followed by a promise: Even though it’s not secure, no one can prove that it’s not secure.
At first, this may sound like a willfully perverse way to market a useless product. But if the lock lives up to that unusual promise, it’s actually exactly as safe as one that’s provably unbreakable. To see why, imagine that you found a way to break the lock. Then the broken lock itself would count as a proof that it wasn’t secure — but if the promise on the packaging is correct, such a proof is impossible. In other words, if a vulnerability exists, but it’s impossible to prove that it exists, then there’s no way to take advantage of it.
This is the basic idea behind Ilango’s new result. Traditionally, to demonstrate that a proof is zero knowledge, you would want to show that it has a simulator. (In our metaphor, this would be equivalent to proving that the lock is unbreakable.) But that would also mean that the proof has to be interactive. To get effective zero knowledge, Ilango instead wanted to show that it’s extremely difficult to guarantee that his proof doesn’t have a simulator. (That is, there’s no way to prove that the lock is breakable.)
If he could show this, he would get all the benefits of zero knowledge while cleverly getting around the requirement of interactivity. “It is actually really hard to think of any real-life situation where this effective zero knowledge wouldn’t be good enough,” Sahai said.
To understand how Ilango pulled this off, let’s return to the three-coloring example. If you know how to color the map, you can write down a noninteractive proof of the statement “This map can be three-colored.” But because of the 1994 impossibility result, that proof can’t have a simulator, and so it can’t be zero knowledge.
Using Ilango’s new approach, you’d instead start by rewriting the statement you want to prove, now adding an extra assumption: “This map can be three-colored — assuming that there’s no efficient way to find a contradiction in the standard axioms of mathematics.” This additional assumption is usually taken for granted. If it’s false, then math is rife with contradictions, and no proof is trustworthy. If it’s true, as researchers universally believe, then Ilango’s new statement is essentially equivalent to the original one.
But the assumption is also thought to be effectively impossible to prove: It’s likely provable in principle, but any proof would be way too long to ever write down. That makes it the sort of Gödel-type assertion that researchers in proof complexity love to study.
It also means that a reader of the proof can’t entirely rule out the possibility that the assumption is false — which has important implications. In particular, it means that there are two possible worlds in which we might live. In the first, the assumption is indeed true, and we’re right back where we started: You’ve written a noninteractive proof that your map can be three-colored, but this proof can’t have a simulator and therefore can’t be zero knowledge. But in the second world, the assumption is false, and we can no longer trust that mathematics is consistent. It’s impossible to distinguish between correct and incorrect proofs; crucially, in this bizarro realm, Goldreich and Oren’s impossibility result no longer applies. Any proof — valid or invalid, interactive or noninteractive — can have a simulator.
This unlikely second world acts as a loophole of sorts. A reader can’t know for certain which world they live in — even though it’s almost certainly the first one, where mathematics remains safe. That, in turn, means that they can’t actually be sure that the proof has no simulator. The proof can still be effectively zero knowledge, even though there’s no interactivity. Ilango had successfully evaded the decades-old impossibility result.
The mathematical sleight of hand involved can make even a seasoned researcher do a double take, but the logic checks out. “It is pretty mind-bending,” Sahai admitted. “The first time you see it, you’re like, ‘Wait, what?’”
To many computer scientists, the broader implications of Ilango’s result are as exciting as the result itself. For decades, proof complexity researchers have studied esoteric questions that seem more closely linked to mathematical logic than to any other area of computer science. The new work suggests that this famously difficult field isn’t as remote as it seems. Ilango, now a postdoctoral researcher at the Institute for Advanced Study in Princeton, New Jersey, and others are already beginning to explore how ideas from proof complexity might help them realize other cryptographic constructions long thought impossible.
“I don’t think it will be an isolated result,” Jain said. “Sometimes, you just need to show people a slight crack in the door.”