How Unknowable Math Can Help Hide Secrets
Kristina Armitage/Quanta Magazine
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.
Shafi Goldwasser (left), Silvio Micali (right), and Charles Rackoff devised a way to prove that a statement is true without revealing anything about why.
©ACM, 2013
“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.
Mark Belan/Quanta Magazine
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.
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. “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.”
