2022 Gödel Prize awarded to post-quantum cryptographic schemes
On May 21, the Association for Computing Machinery (ACM) Interest Group on Algorithms and Computation Theory (SIGACT) announced that the 2022 Gödel Prize has been awarded to Craig Gentry, Zvika Brakerski and Vinod Vaikuntanathan for their transformative contributions to cryptography.
The Gödel Prize is the most prestigious award in the field of theoretical computing. It is named in honor of Kurt Gödel, a pioneer of logic and computer science. The winning paper of the Gödel Prize must have a seminal and significant contribution to the field of theoretical computing; at the same time, it must be formally published in an academic journal within 14 years before the award.
The 2022 Gödel Prize is awarded to the following two papers:
https://ieeexplore.ieee.org/document/6108154
https://dl.acm.org/doi/10.1145/2090236.2090262
The aforementioned papers make a transformative contribution to cryptography by constructing efficient fully homomorphic encryption (FHE) schemes.
Simply put, a cryptosystem that supports arbitrary computations on ciphertext is called fully homomorphic encryption (FHE). By definition:
If f(A)+f(B)=f(A+B) is satisfied, we call this encryption function additive homomorphism;
If f(A)×f(B)=f(A×B) is satisfied, we call this encryption function multiplicative homomorphism.
If an encryption function f only satisfies the addition homomorphism, it can only perform addition and subtraction operations;
If an encryption function f only satisfies the multiplication homomorphism, it can only perform multiplication and division operations;
If an encryption function satisfies both additive homomorphism and multiplication homomorphism, it is called fully homomorphic encryption.
In the FHE scheme, data encryption is no different from standard encryption schemes. Furthermore, FHE provides the ability to perform computations on encrypted data and generate encrypted results without the need for decryption or any keys. This capability enables us to securely outsource expensive computations to untrusted servers and securely perform collaborative computations between multiple entities.
In 1978, Rivest, Adleman and Dertouzos proposed the concept of fully homomorphic encryption (called "privacy homomorphism") in their work. However, building an FHE scheme capable of arbitrary computations on encrypted data remains an open problem for the next three decades. The first homomorphic encryption method satisfying additive and multiplicative homomorphisms was proposed by Craig Gentry in 2009.
In 2009, Craig Gentry constructed the first FHE scheme based on the ideal lattice hypothesis. A lattice is a mathematical structure, a high-dimensional geometric structure composed of points called a "lattice" that becomes increasingly difficult to solve as the number of dimensions increases. Lattice-based algorithms are currently the leading candidates for developing post-quantum cryptography that are resistant to quantum computing attacks.
This pioneering contribution holds great promise in terms of both the nature of efficiency and safety assurance, but it also has some limitations.
In 2011, Brakerski and Vaikuntanathan proposed a new FHE scheme based on the lattice encryption assumption, which is called Learning Fault Tolerant (LWE). Oded Regev, the proponent of LWE, won the 2018 Gödel Prize. Since there is no efficient quantum solution algorithm for the LWE problem, encryption schemes based on the LWE assumption are considered quantum-resistant.
In 2012, Brakerski, Gentry and Vaikuntanathan formally proposed the BGV FHE scheme. The scheme is a graded scheme and is based on better lattice assumptions than 2009 Gentry. Generally, we refer to the BGV scheme as the second-generation FHE scheme.
In 2013, Gentry, together with Sahai and Waters, proposed the third-generation FHE scheme, the GSW scheme. The GSW scheme is still based on the LWE lattice cipher assumption (but slightly better) and uses bootstrapping to make it a true FHE scheme (capable of evaluating a function F of arbitrary size).
The Gödel Prize committee said the papers have had a huge impact on both theoretical and applied research, from the construction of advanced cryptographic primitives, to the implementation of FHE, and the design of post-quantum encryption candidates.
According to the report "Post-Quantum Cryptography - Future Security Storm Hotspot" released by Photon Box, post-quantum cryptography (PQC) will gradually evolve to more advanced applications such as fully homomorphic encryption. "Traditional encryption algorithms can only protect the static security of data during storage and transmission. After the data is encrypted, the only effective operation that can be done on the ciphertext is decryption. Homomorphic encryption allows the ciphertext to be decrypted without a decryption key. Carry out meaningful computing operations, and finally output encrypted computing results, and the entire computing process does not reveal any valid information of the original data and computing results. With the continuous development of PQC technology, homomorphic encryption is expected to be gradually realized. ."
About the winners:
Craig Gentry
In May, Craig Gentry became CTO of TripleBlind, a provider of privacy-enhancing computing solutions. Gentry has been engaged in cryptography research for more than 20 years, won the MacArthur Award for constructing the first fully homomorphic encryption system, and became a member of the International Association for Cryptography Research.
Before joining TripleBlind, Gentry was a research scientist at the Algorand Foundation, IBM Research, and DoCoMo USA Labs. He has a Ph.D. BS in Computer Science from Stanford University, J.D. from Harvard Law School, and BA in Mathematics from Duke University.
Zvika Brakerski
Associate Professor, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Israel. Currently mainly engaged in cryptography and quantum computing. Dual Bachelor of Science from the Faculty of Engineering and Computer Science, Tel Aviv University, Master of Science from the Faculty of Engineering, Tel Aviv University, Ph.D. from the Weizmann Institute of Science (2011). He then spent two years as a postdoctoral researcher in the Department of Computer Science at Stanford University.
Vinod Vaikuntanathan
Cryptographer, professor in the MIT Department of Electrical Engineering and Computer Science (MITEECS), and co-founder of Duality Technologies. He is the co-inventor of most modern fully homomorphic encryption systems and many other lattice-based (post-quantum secure) cryptographic primitives. Bachelor of Science from Indian Institute of Technology, Master of Science and Ph.D. from MIT.
The 2022 Gödel Prize list:
https://sigact.org/prizes/g%C3%B6del/citation2022.html
