How Unknowable Math Can Help Hide Secrets

Kristina Armitage/ Quanta Magazine

克里斯蒂娜·阿米蒂奇/广达杂志

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.

哥德尔的著名成果——他于 1931 年发表的两个“不完备性定理”之一——确定，对于任何一组合理的基本数学假设（称为公理），不可能证明这些公理最终不会导致矛盾。

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.

哥德尔定理诞生 50 多年后，密码学家设计了一种全新的证明方法，其中不可知性扮演了非常不同的角色。

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.

现在，计算机科学家拉胡尔·伊兰戈 (Rahul Ilango) 在它们之间建立了惊人的联系。

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.

Ilango 的方法克服了研究人员长期以来认为无法克服的零知识证明的局限性，突破了此类证明的界限。

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.

“当我第一次看到拉胡尔的论文时，我想，‘不，没有办法，’”加州大学洛杉矶分校的密码学家阿米特·萨海 (Amit Sahai) 说。

“This is just an incredibly cool new direction.”

“这只是一个非常酷的新方向。”

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.

像这样的问题，其解决方案可能很难找到，但总是很容易验证，称为 NP 问题。

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.

由密码学家 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 于 1985 年发明的零知识证明没有这个缺点。

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.

使用零知识证明，任何知道 NP 问题解决方案的人都可以在不透露解决方案的情况下证明它 - 事实上，无需透露任何其他信息。

Shafi Goldwasser (left), Silvio Micali (right), and Charles Rackoff devised a way to prove that a statement is true without revealing anything about why.

Shafi Goldwasser（左）、Silvio Micali（右）和 Charles Rackoff 设计了一种方法来证明某个陈述是真实的，而无需透露任何原因。

“It’s a very counterintuitive notion,” said Tom Gur , a computer scientist at the University of Cambridge.

“这是一个非常违反直觉的想法，”剑桥大学计算机科学家汤姆·古尔（Tom Gur）说。

“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.

Goldwasser 和她的同事通过将数学证明重新想象为两方之间的相互作用，实现了这一惊人的特性。

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 .

1994年，密码学家Oded Goldreich和Yair Oren证明了一个定理，证实了这一直觉。

Their result established that it’s impossible to construct a completely noninteractive proof that meets Goldwasser, Micali, and Rackoff’s definition of zero knowledge.

他们的结果表明，不可能构建一个完全非交互式的证明来满足 Goldwasser、Micali 和 Rackoff 的零知识定义。

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.

“人们只是说，‘算了，这不会发生，’”约翰·霍普金斯大学和 NTT Research 的密码学家 Abhishek Jain 说。

“How can you overcome an impossibility?”

“你怎样才能克服不可能的事情呢？”

Ilango’s new result shows how — by harnessing a different kind of impossibility.

Ilango 的新结果展示了如何利用另一种不可能。

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.

2023 年夏天，伊兰戈在麻省理工学院研究生院读完第三年，他对复杂性理论中一个名为“证明复杂性”的神秘子领域越来越感兴趣。

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.

出于所有实际目的，这些本质上难以证明的陈述与哥德尔确定的无法证明的陈述一样不可知。

Kurt Gödel showed that certain mathematical statements are true but unprovable.

库尔特·哥德尔表明，某些数学陈述是正确的，但无法证明。

Alfred Eisenstaedt/Public Domain

阿尔弗雷德·艾森斯塔特/公共领域

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.

为什么我们不能证明这一点？”IBM 复杂性理论家 Marco Carmosino 说道。

“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.

2024 年，在经历了几次失败之后，Ilango 确定了密码学中的一项特定任务，可以作为他的方法的测试平台。

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.

但伊兰戈意识到，定义“零知识”的方法可能不止一种，而且不可能的结果仅适用于最初的定义。

It is pretty mind-bending.

这真是令人费解。

The first time you see it, you’re like, ‘Wait, what?’

当你第一次看到它时，你会想，“等等，什么？”

Amit Sahai, University of California, Los Angeles

阿米特·萨海，加州大学洛杉矶分校

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.

Goldreich 和 Oren 的不可能结果实际上说明的是，非交互式证明不能有模拟器，因此，根据定义，它们不可能是零知识。

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.

Ilango 希望利用证明复杂性来定义零知识的新概念——他称之为“有效的”零知识——它不会受到旧的不可能结果的影响，但仍然与普通零知识一样有用。

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.

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

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.

换句话说，如果一个漏洞存在，但无法证明它存在，那么就没有办法利用它。

As a graduate student, Rahul Ilango invented a new type of zero-knowledge proof by exploiting the limits of mathematics.

作为一名研究生，Rahul Ilango 通过利用数学的局限性发明了一种新型的零知识证明。

This is the basic idea behind Ilango’s new result.

这就是 Ilango 新结果背后的基本理念。

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.

为了获得有效的零知识，Ilango 相反想要表明，保证他的证明没有模拟器是极其困难的。

(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.

为了了解 Ilango 是如何实现这一目标的，让我们回到三色示例。

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.

如果您知道如何为地图着色，您可以写下“这张地图可以是三色​​的”这一陈述的非交互式证明。但由于 1994 年不可能的结果，该证明不可能有模拟器，因此它不可能是零知识。

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.

使用 Ilango 的新方法，你首先需要重写你想要证明的陈述，现在添加一个额外的假设：“这张图可以是三色​​的——假设没有有效的方法来找到数学标准公理中的矛盾。”这个额外的假设通常被认为是理所当然的。

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.

对于许多计算机科学家来说，Ilango 结果的更广泛影响与结果本身一样令人兴奋。

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.”

“有时候，你只需要向人们展示门上的一条轻微裂缝。”

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。