Shafrira Goldwasser, Ph.D.

Shafi Goldwasser has had tremendous impact on the development of cryptography and complexity theory. Starting with her thesis on “semantic security”, she laid the foundations of the theory of cryptography. She created rigorous definitions and constructions of well-known primitives such as encryption schemes (both public and private key versions) and digital signatures, and of new ones that she introduced, such as zero-knowledge interactive proof systems invented with Micali and Rackoff. Continuing her work on interactive proofs which allow a probabilistic polynomial time algorithm to verify mathematical proofs via interaction with a powerful prover, Shafi and her co-authors extended the notion of interactive proofs to two-prover systems. The original motivation was cryptographic, but they turned out to be of great significance in complexity theory, paving the way to the equivalent formulation of PCP (probabilistically checkable proofs). The expressive power of two-prover systems is huge (non-deterministic exponential time). furthermore, Shafi and her co-authors showed the connection between a scaled down variant of these systems and the hardness of approximation results for NP-hard problems, which led to the PCP theorem. On the algorithmic front, a problem of great significance is that of recognizing (and generating) prime numbers. Shafi and Kilian designed efficient probabilistic primality provers, which output short proofs of primality, based on the theory of elliptic curves. Together with Goldreich and Ron, Shafi originated the field of combinatorial property testing, devising a class of sub-linear algorithms to test properties in dense graphs.