Mathematician finds way to hide secrets using impossibility

Mathematicians typically focus on what can be known and proven. But the unknowable has its own power. Two landmark discoveries in math—separated by decades and different fields—show how impossibility itself can be useful.

In 1931, logician Kurt Gödel published a theorem that shook mathematics. He proved that for any reasonable set of starting assumptions called axioms, you can never be certain those axioms won't eventually contradict themselves. Mathematicians realized they could never be fully sure their rules were self-consistent, yet they continued their work anyway.

More than 50 years later, cryptographers invented something called zero-knowledge proofs. These proofs let you convince someone that a statement is true without telling them why it is true or revealing any helpful information. The two ideas seemed completely unrelated—one about the limits of proof itself, the other about hiding secrets.

Then computer scientist Rahul Ilango made a striking discovery. While still a graduate student, he found a deep connection between these two types of unknowability. He created a new kind of zero-knowledge proof where secrecy comes directly from math's fundamental limits. The breakthrough got around obstacles that researchers thought were impossible to overcome and opened new doors for cryptography research.

Amit Sahai, a cryptographer at the University of California, Los Angeles, said: "When I first saw Rahul's paper, I was like, 'No, there's no way.' This is just an incredibly cool new direction."

Zero-knowledge proofs started with a simple problem from computer science. Imagine you have three colored pencils and a map divided into many regions. Can you color the map so that no two neighboring regions have the same color? This can be extremely difficult to solve. But once someone shows you a completed coloring, you can quickly check if it works by looking at each border. Problems like this—hard to solve but easy to verify—are called NP problems. Cryptographers use them because the hard-to-find solutions make good secret passwords.

The problem is that simple password systems only work if the person with the solution reveals it. In 1985, cryptographers Shafi Goldwasser, Silvio Micali, and Charles Rackoff invented zero-knowledge proofs to fix this. With a zero-knowledge proof, someone who knows the answer can prove they know it without revealing the answer or any other information.

Tom Gur, a computer scientist at the University of Cambridge, said: "It's a very counterintuitive notion. Until you see an example, it sounds like something which is impossible."

Goldwasser and her colleagues made this work by treating a proof as a conversation between two people. In the three-coloring example, a "prover" knows how to color the map. They secretly color it, then cover each region so only the borders show. The other person, the "verifier," picks a border. The prover uncovers the two regions on either side of it. They repeat this many times, with the prover secretly changing the color scheme before each round to keep the verifier from learning bits of information. If the prover reveals two different colors every time, the verifier becomes convinced the prover knows a valid coloring. If the prover is lying, the verifier will probably find a mistake eventually.

This interactive part seemed essential. A prover who just hands over a written proof can't stop the verifier from reading the whole thing and learning everything. They could encrypt it, but then the verifier couldn't check if it's correct. In 1994, cryptographers Oded Goldreich and Yair Oren proved something discouraging: it's impossible to create a completely noninteractive zero-knowledge proof. The dream of a written-down, noninteractive proof that still hides all secrets seemed dead.

Abhishek Jain, a cryptographer at Johns Hopkins University and NTT Research, said: "People just said, 'Forget it, it's not going to happen.' How can you overcome an impossibility?"

Ilango's breakthrough showed how—by using a different kind of impossibility. In the summer of 2023, near the end of his third year as a graduate student at the Massachusetts Institute of Technology, Ilango was studying proof complexity, a specialized area of computer science. Most researchers in complexity theory study how hard it is to solve problems like three-coloring. Proof complexity is different: researchers study how hard it is to prove statements about these problems.

Some mathematical statements can't be proven true or false at all. This is Gödel's other incompleteness theorem. Other statements might be provable in theory, but only with proofs so impossibly long they could never be written down. For practical purposes, these statements are as unknowable as the truly unprovable ones Gödel found. Researchers usually study these hard-to-prove statements to understand the limits of mathematics. But Ilango wondered: could they also be useful in cryptography?

Modern cryptography is built on the difficulty of solving specific problems, like map coloring. Ilango asked himself: what if he could exploit the difficulty of proving statements instead? That might open up new cryptographic techniques. Marco Carmosino, a complexity theorist at IBM, put it this way: "We find ourselves constantly slamming into these walls of 'Why can't we prove this? Why can't we prove that?' Can we benefit from that kind of hardness?"

In 2024, after some false starts, Ilango found the perfect test case: building a noninteractive zero-knowledge proof. Thirty years earlier, Goldreich and Oren had proven these were impossible. But Ilango realized there might be more than one way to define "zero knowledge." The impossibility result only applied to the original definition.

To understand that definition, think about what the verifier sees in the map-coloring proof. Before the prover even starts, the verifier could predict exactly what will happen in a valid proof. Each round, the prover will reveal two different colors, no matter which border is chosen. In cryptography terms, the proof has a "simulator." That's what makes it zero knowledge. Ilango said: "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."

Goldreich and Oren's 1994 result said that noninteractive proofs can't have simulators, so they can't be zero knowledge by that definition. Ilango decided to invent a new definition he called "effective" zero knowledge. It wouldn't be subject to the old impossibility result but would be just as useful. His key insight was simple: it's fine if a proof doesn't have a simulator, as long as nobody can prove it doesn't.

Consider a lock that's famous for being unbreakable. You read the fine print expecting a guarantee of security. Instead you find an unusual promise: "This lock is not actually secure. But it's impossible to prove that it's not secure." At first this sounds ridiculous. Yet if the promise is true, the lock is exactly as safe as one that's provably unbreakable. If someone could break the lock, the broken lock itself would be proof that it's not secure. But if it's impossible to prove the lock is breakable, then nobody can take advantage of any weakness. A vulnerability that can't be proven doesn't matter.

This is the core of Ilango's innovation. Normally, to show a proof is zero knowledge, you prove it has a simulator. In the lock example, that's like proving the lock is unbreakable. But that requires interactivity. For effective zero knowledge, Ilango instead proved that it's extremely hard to prove the proof doesn't have a simulator. He got all the benefits of zero knowledge while avoiding the need for interactivity. Sahai said: "It is actually really hard to think of any real-life situation where this effective zero knowledge wouldn't be good enough."

In the three-coloring example, if you know how to color the map, you can write down a noninteractive proof that the map can be colored with three colors. But because of the 1994 impossibility result, that proof can't have a simulator and so it can't be zero knowledge by the traditional definition. Using Ilango's approach, you rewrite your statement: "This map can be three-colored—assuming there's no efficient way to find a contradiction in the standard axioms of mathematics." This extra assumption is usually taken for granted. If it's false, mathematics is full of contradictions and no proof matters. If it's true, as everyone believes, the new statement is essentially the same as the original one.

But the assumption is thought to be effectively impossible to prove. It might be provable in principle, but any proof would be impossibly long. This is exactly the type of statement proof complexity researchers love to study. It also means that someone reading the proof can't completely rule out the possibility that the assumption is false. This creates two possible worlds. In the first world, the assumption is true, and you're back where you started: a noninteractive proof with no simulator and no zero knowledge. In the second world, the assumption is false, mathematics is broken, and Goldreich and Oren's impossibility result no longer applies. Any proof can have a simulator.

The second world is extremely unlikely but not impossible to rule out. Because readers can't know for certain which world they live in, they can't be sure the proof has no simulator. The proof can still be effectively zero knowledge even though it's not interactive. Ilango had sidestepped the decades-old impossibility result with a mathematical loophole. Sahai admitted: "It is pretty mind-bending. The first time you see it, you're like, 'Wait, what?'"

The implications excite computer scientists as much as the result itself. For decades, proof complexity researchers studied questions that seemed more connected to mathematical logic than to practical computer science. Ilango's work suggests the field is far more relevant than it appeared. Ilango, now a postdoctoral researcher at the Institute for Advanced Study in Princeton, New Jersey, and other researchers are already exploring how proof complexity ideas might enable other cryptographic techniques long thought impossible.

Jain said: "I don't think it will be an isolated result. Sometimes, you just need to show people a slight crack in the door."