A graduate student recently harnessed the complexity of mathematical proofs to create a powerful new tool in cryptography.

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



...read more at quantamagazine.org