2012 Turing to Goldwasser and Micali

Shafi Goldwasser (MIT and Weizmann) and Silvio Micali (MIT) were announced as the 2012 Turing Award winners. I am so excited! On a personal note, my first research paper was a follow-up on their work (joint with Oded Goldreich on pseudorandom functions) and they kept on inspiring my research ever since (and I’m hardly alone in this). Goldwasser and Micali have played a major role in the development of modern cryptography (“from art to science”) which is a big scientific successes story. Their work was particularly influential in laying the foundations of cryptography, and in particular in discovering its tight connection to computational complexity (a connection with dramatic effect on both fields as well as on the theory of computing at large).

The first seminal idea produced by Goldwasser and Micali was that of Semantic Security, put forth in their 1982 paper. They addressed the question of how to say that an encryption scheme is secure and does not leak partial information about the encrypted messages. A few years later, Goldwasser, Micali and Rackoff defined zero-knowledge proof systems and made explicit the simulation paradigm which can be seen as an extension of the notion of semantic security. Zero-knowledge proof systems (whose full power was shown by Goldreich, Micali and Wigderson in 1986 and 1987) allow a party to prove to another party the validity of a statement without revealing any information beyond the validity of the statement (in particular, if Alice proves a statement to Bob in zero-knowledge it will not even help Bob prove the same statement to Charlie). The concept of simulation is of utmost importance and essentially all modern definitions of security either employ it or relate to it. These and subsequent works put interaction and randomness at the center stage of computer science.

In 1984 (the same year GGM defined and constructed pseudorandom functions), Goldwasser, Micali and Rivest defined the security of digital signature schemes, and again suggested the gold standard: signature schemes existentially secure against chosen message attack and showed how to obtain such security under plausible assumptions. In 1988 Ben-Or, Goldwasser, Kilian and Wigderson decided to investigate the necessity of hardness assumptions in order to obtain zero-knowledge protocols for NP. For this they extended the interactive proof model and considered two provers who are not allowed to talk to each other during the execution of the protocol. Discovering the power of interactive proofs was arguably the most important development of complexity theory over the last two decades with spectacular results such as IP=PSPACE, the PCP Theorem and the tight relationship with hardness of approximation. The first paper to make the connection between two-prover interactive proofs and hardness of approximation was the work by Feige, Goldwasser, Lovasz, Safra and Szegedy.

This short survey has ignored so many other prize-worthy papers of the authors such as Goldwasser and Kilian’s Primality Testing, Feldman and Micali’s Byzantine Agreement in constant number of rounds, Blum, Feldman and Micali’s work on non-interactive zero Goldreich, Goldwasser and Ron’s establishment of the flourishing field of combinatorial property testing, and many more I surely forgot.

There is much to admire in Goldwasser and Micali, and they embody much of what I love about the theory of computing as a field. For one, TOC is so dynamic and collaborative (and Goldwasser and Micali had absolutely outstanding collaborators, some of which are mentioned above). Another great ability of TOC (which is something I once heard Avi Wigderson articulate) is that many times TOC identifies the right level of abstraction. Semantic security and simulation is a prime example of that. And with the right level of abstraction, TOC at its best is creative and innovative. The ability to imagine the unimaginable (with zero-knowledge proofs being an astonishing example) and to turn it into the natural is something I admire the most about this year’s so worthy winners.