GoKawiilThe 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?”
... continue reading