Two MIT professors have been named as the winners of the 2012  A.M. Turing Award for their pioneering work in the fields of cryptography and complexity theory.

The ACM A.M Turing Award is widely considered the "Nobel Prize in Computing," and carries a $250,000 prize, with financial support provided by Intel and Google. It is awarded annually and the latest recipients are Shafi Goldwasser and Silvio Micali who jointly developed new mechanisms for how information is encrypted and secured and also made fundamental advances in the theory of computational complexity.

According to the ACM press release:

Working together, they pioneered the field of provable security, which laid the mathematical foundations that made modern cryptography possible. By formalizing the concept that cryptographic security had to be computational rather than absolute, they created mathematical structures that turned cryptography from an art into a science. Their work addresses important practical problems such as the protection of data from being viewed or modified, providing a secure means of communications and transactions over the Internet. Their advances led to the notion of interactive and probabilistic proofs and had a profound impact on computational complexity, an area that focuses on classifying computational problems according to their inherent difficulty.

Shafi Goldwasser (left) and Silvio Micali (right
Photo: CSAIL/MIT

Goldwasser and Micali began collaborating as graduate students at the University of California at Berkeley in 1980. While exploring the idea of how to securely play a game of poker over the phone, they devised a scheme for encrypting and ensuring the security of single bits of data, and this work led to a paper in 1982, titled “Probabilistic Encryption,” which laid the framework for modern cryptography.

Another of Goldwasser and Micali’s significant contributions is their 1985 paper, with Charles Rackoff, titled “The Knowledge Complexity of Interactive Proof Systems.” It introduced knowledge complexity, a concept that deals with hiding information from an adversary, and is a quantifiable measure of how much “useful information” could be extracted. The paper initiated the idea of “zero-knowledge” proofs, described as a striking new philosophical idea that provided the essential language for speaking about security of cryptographic protocols by controlling the leakage of knowledge.

Commenting  on the award, Goldwasser says:

“I am very proud to have won the Turing Award. Our work was very unconventional at the time. We were graduate students and let our imagination run free, from using randomized methods to encrypt single bits to enlarging the classical definition of a proof to allow a small error to setting new goals for security. Winning the award is further testimony to the fact that the cryptographic and complexity theoretic community embraced these ideas in the last 30 years.”

Micali adds:

“I am honored by this recognition and thankful to the computer science community, As graduate students, we took some serious risks and faced a few rejections, but also received precious encouragement from exceptional mentors. I am also proud to see how far others have advanced our initial work.”

ACM President Vint Cerf said the practical impact of the ideas promulgated by Goldwasser and Micali is tangible:

“The encryption schemes running in today’s browsers meet their notions of security.  The method of encrypting credit card numbers when shopping on the Internet also meets their test.  We are indebted to these recipients for their innovative approaches to ensuring security in the digital age.”