The 2022 Gödel Prize is awarded to the following papers:
The above papers made transformative contributions to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes.
In an FHE scheme, data is securely encrypted as in a standard encryption scheme. In addition, FHE provides capability to compute on the encrypted data and generate encrypted results, without decrypting or requiring any secret key. Such capability unlocks a vast array of applications that let us securely outsource expensive computations to untrusted servers, and securely perform collaborative computations among multiple entities.
The notion of fully homomorphic encryption was conceived (as “privacy homomorphisms”) in work by Rivest, Adleman and Dertouzos in 1978. Constructing an FHE scheme which enables arbitrary computations on encrypted data, however, remained an open question for the following three decades.
Prior to these papers, one of the authors, Craig Gentry, had presented (in proceedings form only) a construction of FHE in 2009. That groundbreaking contribution had great promise, but also some limitations, regarding both efficiency and the nature of the security guarantees. The above papers presented entirely new constructions of fully homomorphic encryption whose security relied only on the hardness of Regev's learning with errors (LWE) problem. They have led to a new generation of practically efficient FHE.
These papers have had enormous impact on both theoretical and applied research, ranging from the constructions of advanced cryptographic primitives, via worst-case to average-case reductions, to FHE implementation, and the design of post-quantum encryption candidates.
Award Committee:
Samson Abramsky (Chair, University of Oxford)
Nikhil Bansal (CWI Amsterdam)
Irit Dinur (Weizmann Institute)
Anca Muscholl (University of Bordeaux)
Ronitt Rubinfeld (Massachusetts Institute of Technology)
David Zuckerman (University of Texas at Austin)