(Communicated by the Weizmann Institute)

ACM, the Association for Computing Machinery, today announced that Prof. Shafi Goldwasser of the Weizmann Institute's Computer Science and Applied Mathematics Department, and the Massachusetts Institute of Technology Computer Science and Artificial Intelligence Lab, will receive the ACM A.M. Turing Award. She receives the Award together with Prof. Silvio Micali of MIT "for transformative work that laid the complexity-theoretic foundations for the science of cryptography, and in the process pioneered new methods for efficient verification of mathematical proofs in complexity theory."

The ACM Turing Award, widely considered the highest prize in the field of computing (there is no Nobel Prize in the field) carries a $250,000 prize, with financial support provided by Intel Corporation and Google Inc. ACM will present the 2012 A.M. Turing Award at its annual Awards Banquet on June 15, 2013 in San Francisco, California.
 
Probabilistic encryption

In their 1982 paper on "Probabilistic Encryption," Goldwasser and Micali laid the rigorous foundations for modern cryptography. The work is universally credited in changing cryptography from an "art" to a "science".

This paper pioneered several themes which are today considered basic to the field. These include the introduction of formal security definitions that are now the gold standard for security; the introduction of randomized methods for encryption which can satisfy stringent security requirements that could not be satisfied by previous deterministic encryption schemes; and the methodology of "reductionist proofs," which shows how to translate the slightest attack on security into a fast algorithm for solving such hard classical mathematical problems as factoring integers. These proofs are a double edged sword, in that they show that one of two things must be true: Either we have a super secure encryption scheme, or we have new algorithms for factoring integers.

The 1982 paper also introduced the "simulation paradigm," in which the security of a system is established by showing that an enemy could have simulated, on his own, any information he obtained during the employment of a cryptographic system, and thus this cryptographic system represents no risk. The simulation paradigm has become the most general method for proving security in cryptography, going beyond privacy to define and prove security of authentication methods, security of software protection schemes and security of cryptographic protocols that involve many participants, for example electronic elections and auctions.

Zero-knowledge interactive proofs

In another influential paper, published in 1985 with Rackoff, Goldwasser and Micali introduced the concept of "zero-knowledge interactive proofs."

An example of a zero-knowledge interactive proof would be an ATM machine that would not need you to enter your PIN number, but would only need to verify that you, yourself know it. Zero-knowledge proofs can also enable users working on the Internet who may not trust each other to compute joint functions on their secret data.

In contrast to classical mathematical proofs, which can always be written down, an interactive proof is a sort of conversation. One side - the "prover" - tries to convince the other - the "verifier" - that he knows the proof of a mathematical statement. The verifier must ask the prover a series of questions, which are randomly chosen depending on the prover's previous answers and the mathematical statement to be proved. If the prover does not know the proof, the overwhelming probability is that the verifier will be able to catch him out by his mistakes. Because the verifier can be convinced that the proof exists, without learning the proof itself, such proofs are truly "zero-knowledge proofs."

When Goldwasser, Micali and Rackoff published their paper, its relevance to cryptography was immediately apparent. For example, it suggested an identification system that can be used safely over the internet. The idea is that an individual user will know a proof for her own special theorem, which will be her password. To identify herself, the user can interact with a verifier (an ATM machine for example) to give that verifier a zero-knowledge proof of her special theorem.

Interactive proofs are not only a cryptographic tool; they have had a major impact on complexity theory. What seemed to be obvious for cryptographic purposes - that randomization and interaction must be used - has turned out to be widely applicable to complexity theory in general. It enables faster verification of proofs than classical mathematics and even gives mathematicians the ability to prove that some mathematical statements are not correct, by proving "non existence" of classical proofs.

In a further series of works by Goldwasser, Micali and others, interactive proofs were extended to include interactions between a verifier and multiple provers, which ultimately led to surprising new ways to prove NP-completeness results for approximation problems. This is an active area of research today. Prof. Shafi Goldwasser's research is supported by Walmart.

Practical impact

ACM President Vint Cerf said the practical impact of the ideas put forward 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."

Alfred Spector, Vice President of Research and Special Initiatives at Google Inc., said Goldwasser and Micali developed cryptographic algorithms that are designed around computational hardness assumptions, making such algorithms hard to break in practice. "In the computer era, these advances in cryptography have transcended the cryptography of Alan Turing's code-breaking era. They now have applications for ATM cards, computer passwords and electronic commerce as well as preserving the secrecy of participant data such as electronic voting. These are monumental achievements that have changed how we live and work."

Prof. Shafi Goldwasser is the third member of the Weizmann Institute faculty to receive the Award. The others are Profs. Amir Pnueli (1996) and Adi Shamir (2002).

Goldwasser is recipient of the National Science Foundation Presidential Young Investigator Award, she also won the ACM Grace Murray Hopper Award for outstanding young computer professional. She has twice won the Gödel Prize presented jointly by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS). She was elected to the American Academy of Arts and Science, the National Academy of Sciences, and the National Academy of Engineering. She was recognized by the ACM Council on Women in Computing (ACM-W) as the Athena Lecturer, and received the IEEE Piore Award and the Franklin Institute's Benjamin Franklin Medal in Computer and Cognitive science.

A graduate of Carnegie Mellon University with a B.A. degree in mathematics, she received M.S. and Ph.D. degrees in computer science from the University of California, Berkeley. She joined the Weizmann Institute in 1993 as a full professor. She is the third woman to receive a Turing Award since the Awards' inception in 1966.