She is the co-inventor of zero-knowledge proofs, which probabilistically and interactively demonstrate the validity of an assertion without conveying any additional knowledge, and are a key tool in the design of cryptographic protocols. Her work in complexity theory includes the classification of approximation problems, showing that some problems in NP remain hard even when only an approximate solution is needed, and pioneering methods for delegating computations to untrusted servers. Her work in number theory includes the invention with Joe Kilian of primality proving using elliptic curves.