Shafi Goldwasser

Shafi Goldwasser has made fundamental contributions to cryptography, computational complexity, computational number theory and probabilistic algorithms.  Her career includes many landmark papers which have initiated entire subfields of computer science.  These include creating the theoretical foundations of modern cryptography, the introduction of zero-knowledge interactive proofs, the introduction of multi-prover proofs (later known as probabilistically checkable proofs), discovering the connection between probabilistically checkable proofs and the intractability of approximation problems, showing how to use the theory of elliptic curves to distinguish primes from composites, and launching combinatorial property testing.

Shafi was born in 1959 in New York City. Her parents were Israeli, and her joint American/Israeli citizenship presaged the two countries that would play such an important role in her research. Her family returned to Israel where Shafi attended grade school in Tel Aviv. In high school she was especially interested in physics, mathematics and literature. After her schooling she returned to the U.S. and became an undergraduate in the mathematics department at Carnegie Mellon University. Soon, however, she became interested in programming (which she had never done before) and computer science. One computer science course that she especially remembers, taught by Jon Bentley, was an algorithms and discrete math course that she loved. She also worked on the CM* project at CMU, a 50-processor multiprocessor system. Shafi next had a summer internship at the RAND Corporation in Los Angeles. She loved living on Venice Beach, but her seduction by California wasn’t complete until she drove up the coast road one weekend and entered Berkeley for the first time.

Shafi enrolled in graduate school in Computer Science at the University of California, Berkeley, without knowing what she wanted to study. Her master's work was with Michael Powell and David Patterson, studying the optimal instruction set for the RISC architecture. But she soon met a group of enthusiastic young theoretical computer scientists – including Eric Bach, Faith Ellen, Mike Luby, Jeff Shallit, Vijay Vazirani and her Turing Award co-recipient Silvio Micali – and she began to see that her interests lay in theoretical areas.

What closed the deal for her was a number theory course by another Turing Award recipient, Manuel Blum. Subjects such as primality testing, quadratic residues, quadratic non-residues, RSA, and coin-tossing really excited her. She happily attended the first Crypto conference in Santa Barbara and met the three authors of the RSA cryptographic system, themselves later Turing Award recipients: Ron Rivest, Adi Shamir and Len Adleman.

The first problem Shafi began working on with Micali was how to hide partial information in “mental poker”. Their solution [1] was an essentially perfect way of encrypting a single bit (against a computationally limited adversary), and they invented a “hybrid” technique to show that independently encrypting individual bits causes the whole message to be secure. In their example, encryption security was provably based on a quadratic residuosity assumption. They were the first to give a rigorous definition of semantic security for a public-key encryption system, and showed that it was equivalent to a number of other intuitive formulations of security. Julius Caesar may have used cryptography, but now we were finally beginning to understand it.

Upon graduating from Berkeley in 1984, Shafi went to the Massachusetts Institute of Technology, first as a postdoc, and then as a faculty member. She became the RSA Professor of Electrical Engineering and Computer Science in 1997. In 1992 she began a parallel career as a Professor of Computer Science and Applied Mathematics at the Weizmann Institute of Science in Israel. Shafi, with her husband and computer scientist Nir Shavit and their two sons, somehow divide their time between the two institutes, spending about three years at a time in each country.

It was an exciting time when Shafi came to M.I.T. She joined a group with similar research interests: Micali had arrived, and Benny Chor, Oded Goldreich, Ron Rivest and Mike Sipser were there. With Goldreich and Micali [4], Shafi investigated whether the notion of a pseudorandom number generator could be generalized so that one could generate exponentially many bits (or equivalently, a function) pseudorandomly. What would it even mean to do this? This definition was in itself important, and it is why we understand today what it means for a block cipher such as AES to be secure. They also showed how to provably transform a pseudorandom number generator into a pseudorandom function generator. These ideas had applications to the (then) new field of Learning Theory, providing examples of things that cannot be learned.

Shafi, with Micali (and later Rackoff) [6], had been thinking for a while about expanding the traditional notion of “proof” to an interactive process in which  a "prover" can convince a probabilistic "verifier" of the correctness of  a mathematical proposition with overwhelming probability if and only if the proposition is correct. They called this interactive process an "interactive proof" (a name suggested by Mike Sipser). They wondered if one could  prove some non-trivial statement (for example, membership of a string in a hard language) without giving away any knowledge whatsoever about why it was true. They defined that the verifier receives no knowledge  from the prover if the verifier  could simulate on his own the probability distribution that he obtains in interacting with the prover.The idea that “no knowledge” means simulatability was a very important contribution. They also gave the first example of these “zero knowledge interactive proofs” using quadratic residuosity. This paper won the first ACM SIGACT Gödel Prize. This zero-knowledge work led to a huge research program in the community that continues to this day, including results showing that (subject to an assumption such as the existence of one-way functions) a group of distrusting parties can compute a function of all their inputs without learning any knowledge about other people’s inputs beyond that which follows from the value of the function.

Sharing the Gödel Prize was a paper by László Babai and Shlomo Moran that gave a different notion of interactive proof, where the randomness of the verifier is only from public coins. An example in Shafi's paper on zero knowledge clearly seemed to require private coins, but Shafi and Michael Sipser [7] later proved that the two notions are equivalent. This involved using public coins to do interactive proofs showing lower bounds on the sizes of sets.

Around this time, Shafi returned to her love of number theory. After hearing a talk by René Schoof about counting the number of points on elliptic curves, she and Joe Kilian [3] showed that for most primes, it is possible to use elliptic curves to construct a normal, non-interactive proof that the number is indeed prime. This meant that when a “prime” is chosen for a cryptographic algorithm such as RSA, one can be absolutely certain that the number really is prime. (It was only much later that we learned of a polynomial-time algorithm for primality testing.)

Shafi then started asking a number of questions concerning what kinds of security can be achieved without computational complexity assumptions. This led to a model for multi-party computation where, instead of an assumption, one changes the physical model so that every pair of parties has a secure channel between them. Shafi, with Michael Ben-Or and Avi Wigderson, showed [8] that with sufficiently many honest parties, function evaluation in this setting can be done securely. The construction uses a form of algebraic “verifiable secret sharing”, a variant on an idea first proposed [2] by Goldwasser, Baruch Awerbuch, Benny Chor, and Micali.

Another outcome of this research was a variant of interactive proofs where the prover is replaced by two or more provers who cannot talk with each other. Shafi, with Ben-Or, Kilian and Wigderson, showed [9] that two provers are sufficient, and that all of NP can be proven with zero knowledge in this model without any assumptions. This inspired many extremely important results by other people. We can't explain all that development here, so we will cut to Shafi's next big contribution.

Shafi, with Feige, Lovasz, Safra and Szegedy, by examining the power of multi-prover proofs, discovered [10] that the existence of these proofs (with certain parameters) implies a hardness of approximation result for certain NP-complete languages. Specifically, they showed that if the size of a maximum clique in a graph can be approximated within a constant factor, then all of NP can be accepted in nearly polynomial time. This result inspired decades of results about PCPs (probabilistically checkable proofs, an alternative characterization of multi-prover proofs) and hardness of approximation. This paper earned Shafi her second Gödel Prize, shared with two papers that prove nearly optimal parameters for PCPs. One of the most important contributors to this area is Johan Håstad, who years earlier had been the very first of Shafi's many amazing graduate students.

With Mihir Bellare, Carsten Lund and Alexander Russell, Shafi produced [11] one of the first works showing how to fine-tune some of the PCP parameters, leading to improved results on hardness of approximation. The theme of approximation enters her work in a number of other ways as well. One computational problem, which quantum computers have not to date been able to attack and on which public-key cryptography can be based, is approximating the shortest vector size in an integer lattice.  Shafi and Goldreich [12] showed an especially succinct interactive proof for this approximation problem, thus demonstrating it is unlikely to be NP-hard.

On the algorithmic side, with Goldreich and Dana Ron, Shafi introduced the subject of “property testing” for combinatorial properties [13].  Given an object (such as a graph) for which either a given property holds or the object is far from any other object for which the property holds, we want to (probabilistically) determine which is the case by examining the object in only a small  number of locations. In [13] property-testers are devised which need to examine only a constant number of edges in a graph for several NP-complete properties such as 3-coloring, max-cut, and other graph partition problems..

Interactive proofs also play a major role in her recent research about how a user can delegate computation to a very fast but untrusted “cloud” computer. This is one of the most important research areas in cryptography today. Shafi, with Yael Tauman Kalai and Guy Rothblum, introduced [15] one practical formulation of this question, and showed how to efficiently delegate the computation of small-depth functions.

Shafi has recently explored different models for how to achieve “code obfuscation”. For example, with Tauman Kalai and Rothblum she proposed [16] the model of "one-time program" which obfuscates a program so that it can be executed only for a prescribed number of executions, assuming a special kind of universal secure hardware.  In recent work [18] with Tauman Kalai, Vinod Vaikuntanathan, Raluca Ada Popa, and Nickolai Zeldovich on “functional encryption,” Shafi introduced yet another new paradigm for general function obfuscation called “token-based obfuscation."

Another recent area of research [17] is protection against “side-channel attacks”, where an adversary is able to get information (for example, by measuring processor power consumption) that is not part of the stream of bits specified by a protocol. Shafi, with Adi Akavia and Vaikuntanathan, had the first results showing how to do public-key encryption in a way that remains secure even if the secret memory containing the secret key is partially leaked. This was the beginning of an intensive research effort by the cryptographic community to define and achieve leakage resilience for cryptographic primitives and protocols.

Two other interesting facts about Shafi: Since her husband Nir Shavit has also won a Gödel Prize, her household total of three may be a record. And recently, Shafi has become a fan and practitioner of “Playback Theater”, an improvisational interactive group experience.

Author: Charles Rackoff