A fully homomorphic encryption scheme

TLDR

Fully homomorphic encryption has numerous applications, such as enabling encrypted search engine queries, searching on encrypted data, and improving secure multiparty computation. We propose the first fully homomorphic encryption scheme, solving an old open problem. The scheme works by first constructing a somewhat homomorphic, bootstrappable encryption that supports its own decryption function, then using recursive self‑embedding to achieve full homomorphism, enabling efficient computation of any efficiently computable function on ciphertexts.

Abstract

We propose the first fully homomorphic encryption scheme, solving an old open problem. Such a scheme allows one to compute arbitrary functions over encrypted data without the decryption key—i.e., given encryptions E(m1), ..., E( mt) of m1, ..., m t, one can efficiently compute a compact ciphertext that encrypts f(m1, ..., m t) for any efficiently computable function f. Fully homomorphic encryption has numerous applications. For example, it enables encrypted search engine queries—i.e., a search engine can give you a succinct encrypted answer to your (boolean) query without even knowing what your query was. It also enables searching on encrypted data; you can store your encrypted data on a remote server, and later have the server retrieve only files that (when decrypted) satisfy some boolean constraint, even though the server cannot decrypt the files on its own. More broadly, it improves the efficiency of secure multiparty computation. In our solution, we begin by designing a somewhat homomorphic boostrappable encryption scheme that works when the function f is the scheme's own decryption function. We then show how, through recursive self-embedding, bootstrappable encryption gives fully homomorphic encryption.