The Beginnings of Zero-Knowledge

Wired runs this video series where topic expert explain concepts to five levels of difficulty, typically a child, teen, undergrad, grad student and expert. UCLA professor Amit Sahai took this on for zero-knowledge. 

I'd recommend the whole thing but I'd like to focus on the last segment with USC Professor Shanghua Teng (starts at 17:05). Amit nicely summed up the importance of the paper.

What was such a beautiful insight is that the idea of zero-knowledge being something that you can already predict. If you can already predict the answer, then you must not be gaining any knowledge by that interaction. This insight of being able to predict the future accurately, and that being an evidence of a lack of new knowledge.

Like Shanghua I was also assigned the seminal zero-knowledge paper by Goldwasser-Micali-Rackoff from my advisor. In many ways the original STOC paper was rough. The definitions were buggy, the examples uninspiring. Supposedly the paper didn't even get accepted into a conference in its first try. And yet as you read the paper you realize the potential, the beauty of not one but two new models that would go on to change both cryptography and complexity forever.

In the fall of 1985 when I started graduate school I took a cryptography class from Manuel Blum. Much of that class was spent on protocols that would convince you that, for example, a number was the product of three primes. By the spring of 1986, Goldreich, Micali and Wigderson distributed their paper showing, among other things, all NP problems has zero-knowledge proofs, making many of the protocols discussed in Blum's course a few months earlier trivial corollaries.

But it wasn't just zero-knowledge. Goldwasser, Micali and Rackoff (and independently Babai and Moran) developed the notion of interactive proof, a proof system with statistical confidence, a model that would lead to probabilistically checkable proofs and helping us understand the limits of approximation.

I owe most of my early research to the models developed in the GMR paper and glad that Amit has found a way to share these ideas so well.