Homomorphic encryption: a mathematical survey

Abstract

If the first thing that comes to mind when you hear the word “encryption” is the Enigma machine, you might think that encryption is complicated and mathematically uninteresting. In fact, many modern encryption systems are quite simple from a mathematical point of view, especially encryption systems that are homomorphic. In these systems, the starting point is a homomorphism that respects some binary operation(s), such as $+$ or $\times$. Depicting this homomorphism with a rectangular commutative diagram, the objects on the top level of the diagram are called ciphertexts, and the objects on the bottom level are called messages or plaintexts. The downward arrows in the diagram are the homomorphism, which we call decryption. The rightward arrows are the operation(s). Decryption commutes with the operations. To the commutative diagram we add one extra ingredient, computational complexity. Specifically, we need for it to be easy (in the sense of polynomial-time) for anyone to compute the rightward arrows in the diagram, but hard to learn how to compute the downward (decryption) arrows except with some special information that we will call a “secret key.” In short, homomorphic encryption is simply a homomorphism that has been “hardened” in the complexity-theoretic sense. Homomorphic encryption allows anyone to compute on encrypted data, without needing (or being able) to decrypt, has many exciting applications. Fully homomorphic encryption (FHE) systems, which allow a rich (functionally complete) set of operations, were finally discovered in 2009. But all of the FHE systems that we have discovered so far follow the same blueprint, and we still wonder whether there are other ways to build FHE. This survey presents homomorphic encryption from a mathematical point of view, illustrating with several examples how to start from a homomorphism and harden it to make it suitable for cryptography, pointing out pitfalls and attacks to avoid, laying out the current blueprint for FHE, and (I hope) serving as an inspiration and useful guide in the development of new approaches to FHE.