The 2022 Gödel Prize

The 2022 Gödel Prize is awarded to the following papers

- Zvika Brakerski, Vinod Vaikuntanathan: Efficient Fully Homomorphic Encryption from (Standard) LWE. FOCS 2011: 97-106. SIAM Journal of Computing 43(2): 831-871 (2014)

- Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: (Leveled) fully homomorphic encryption without bootstrapping. ITCS 2012: 309-325. ACM Transactions on Computation Theory 6(3): 13:1-13:36 (2014)

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 College London)

- Nikhil Bansal (University of Michigan),

- Irit Dinur (Weizmann Institute)

- Anca Muscholl (University of Bordeaux)

- Ronitt Rubinfeld (Massachusetts Institute of Technology)

- David Zuckerman (University of Texas at Austin).