Crypto-Turing in 2012

Last week, the ACM announced the winners of the 2012 Turing award: Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography.

Goldwasser and Micali produced one of the most influential papers in computer science, “Probabilistic Encryption,” as graduate students in 1983, by introducing the question “What is a secret?” Their standards were very high: an adversary (third party) should not be able to gain any partial information about a secret. Their definition of the security of encryption as a “game” involving adversaries has become a trademark of modern cryptography. Their approach, known as the simulation paradigm, bypassed the traditional enumeration of desired properties that marked the definition of security, and led to the construction of a secure encryption scheme.

Probabilistic Encryption is still, 30 years later, a landmark paper. Here's how they describe "Semantic Security":

Informally, a system is semantically secure if whatever an eavesdropper can compute about the cleartext given the cyphertext, he can also compute without the cyphertext.

You can find Probabilistic Encryption, as well as Professor Goldwasser's other articles, on her MIT home page; Professor Micali's works are available from his home page as well.

When I was taking Dan Boneh's online Cryptography class last spring, I was fascinated by the "adversary game" approach as a foundational proof technique. Looking for written materials to reinforce Professor Boneh's superb lectures, I found that Goldwasser's Lecture Notes on Cryptography was the one essential text I needed. There are some very good works on Cryptography nowadays, but if you can successfully finish Boneh's class, and feel comfortable with the material in Goldwasser and Bellare's Lecture Notes, you can consider yourself quite well-grounded in modern cryptography.

Omer Reingold wrote a very nice short survey of the work of Goldwasser and Micali, describing why it is, truly, deserving of the Turing Award: 2012 Turing to Goldwasser and Micali.