Turing Award to the Institute’s Prof. Shafi Goldwasser

Prof. Shafi Goldwasser, who is at both the Weizmann Institute and MIT, will receive the 2012 A.M. Turing Award, together with Prof. Silvio Micali of MIT. Goldwasser is only the third woman to receive the Award since its inception in 1966, and she is the third faculty member of the Weizmann Institute to receive what is considered to be the “Nobel Prize in computing.”

Goldwasser and Micali’s work in the 1980s laid the foundations of modern cryptography – the science that, among other things, keeps your electronic transactions secure.

The basis of their work is a series of riffs on the concepts of probability and proof. For example, in their seminal “zero-knowledge interactive proofs” paper, they changed, forever, the paradigm of a mathematical proof that must be written down, step-by-step, page after page. Instead, they suggested that a proof can come out of a conversation between two parties – a “prover” and a “verifier.”

Laszlo Lovasz describes it thus:

It sounds paradoxical, but there is a scheme which allows the customer to convince the bank that he knows the password – without giving the slightest hint as to what the password is! ….The most interesting aspect of this scheme is that it extends the notion of a proof, thought (at least in classical mathematics) to be well established for more than 2000 years. In the classical sense, a proof is written down entirely by the author (whom we call the Prover), and then it is verified by the reader (whom we call the Verifier). Here, there is interaction between the Prover and the Verifier: The action taken by the Prover depends on the “questions” of the Verifier.

In other words, by asking a series of questions, each one randomly based on the answer to the previous question, the verifier can ascertain whether the prover has the mathematical proof -- without actually learning anything about the proof, itself. Obviously, using a method like this can keep your password from being stolen, but it can also be used by people working together online who want to jointly compute functions without giving away their data.

In fact, Goldwasser and Micali’s work has major implications for the entire field of mathematics known as complexity theory. Lovasz imagines using the method to referee an “exponentially long paper”:

There is a way to write down a proof so that a referee can check the correctness of a theorem by reading only a tiny fraction of it. The proof becomes longer than necessary, but not much longer. The number of characters the referee has to read is only around the logarithm of the original proof length!

Just as important, says Goldwasser, you can use such methods to establish that a mathematical statement is not correct, by proving "non existence" of classical proofs.