Goldwasser and Micali Receive 2012 ACM Turing Award

Shafi Goldwasser, RSA Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT) and a professor of Computer Science and Applied Mathematics at Weizmann Institute of Science (WIS) in Israel, and Silvio Micali, Ford Professor of Engineering at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), are the co-recipients of the 2012 ACM A.M. Turing Award.

The two are being honored for together inventing the concept of provable security, which laid the mathematical foundations that made modern cryptography possible. They proposed that cryptographic security had to be computational rather than absolute, and addressed important practical problems such as the protection of data from being viewed or modified. Their work provided a secure means of communications and transactions online. They also introduced interactive proofs, which had a profound impact on computational complexity, an area that focuses on classifying computational problems according to their inherent difficulty.

Widely considered the "Nobel Prize in Computing," the ACM Turing Award carries a $250,000 prize, with financial support provided by Intel Corporation and Google Inc. The award is named after British mathematician Alan M. Turing.

Asked the aspect of the contribution she is most proud of, Goldwasser said, "the notion of interactive proofs and switching from classical proofs to ones where there’s an infinitesimal probability of error–of accepting an argument that is incorrect. Interactive proofs completely change the paradigm of proof." Allowing explicit interaction between the author of a proof and the person checking it enables far more complicated statements to be verified than those in a written proof, she said. "That is of great relevance to many problems we face today in delegating computations to remote servers, for example, and in general in how we think of what a proof is."

Goldwasser also is head of the Theory of Computation Group, co-leader of the Cryptography and Information Security Group, and a member of the Complexity Theory Group within MIT CSAIL, and a member of the Foundations of Science Group at WIS.

Micali said he delights in understanding computation "through the negative, that is, adversarial computation. To learn about yourself, you must learn about your enemy, because he knows you better than you know yourself." Although it’s very hard to observe yourself, he elaborated, you can "by looking at the negative, like old photography technology, and then you can exit and look from the opposite side. Cryptography gives us a deeper understanding of computation by looking at its adversarial case. I’m very proud of turning negatives into positives."

ACM president Vint Cerf, a 2004 Turing Award recipient along with Robert E. Kahn for their pioneering work on internetworking, lauded the practical impact of Goldwasser and Micali’s ideas and noted society’s indebtedness to their innovative approaches to ensuring security in the digital age. "The encryption schemes running in today’s browsers meet their notions of security," he said, "The method of encrypting credit card numbers when shopping on the Internet also meets their test."

As graduate students in 1983 at the University of California, Berkeley, Goldwasser and Micali wrote the influential paper Probabilistic Encryption, in which they asked, "What is a secret?" and concluded that an adversary should be unable to gain partial information about a secret. Further, they defined security of encryption as a "game" involving adversaries. Their approach, known as the simulation paradigm, bypassed the traditional set of desired properties that define security, and led to the construction of a secure encryption scheme.

One of the most significant contributions of Goldwasser and Micali is their 1985 paper with Charles Rackoff, titled The Knowledge Complexity of Interactive Proof Systems, which introduced the notion of knowledge complexity. This concept deals with hiding information from an adversary, and is a quantifiable measure of how much "useful information" could be extracted. The paper proposed the concept of "zero-knowledge" proofs, in which a statistical argument establishes a fact without providing any additional information as to why it is true.

"I’m very honored and happy that people recognize the importance of our ideas, which were very unconventional when we started," said Goldwasser "We didn’t just solve problems that had been set up by others. These were unconventional ways to think about encryption, interaction, randomness, and proofs, and the fact that you can talk about proofs and verifying proofs that could be incorrect."

Noting that collaboration enriches scientists and acknowledging science as a social process, Micali said, "I’m very happy to get this prize with Shafi. I believe in the history of collaboration and that it’s recognized means a lot to me, not only for our friendship, but also to incentivize other people to join forces. Often we can solve problems better if we work together." He said his and Goldwasser’s "endless discussions and interactions" lead to their theory of interaction. "We made progress together, and the more interaction and the more collaboration the better."

It is fitting, then, that two people interacting accomplished such seminal work on interaction.