Optimisations of Fully Homomorphic Encryption

Fully homomorphic encryption (FHE) is a class of encryption algorithms that support any computation on encrypted messages without revealing anything about these messages in unencrypted form except for their maximal size. Using FHE, a party that owns private data can securely outsource computations on this data to another party. Due to this functionality, FHE finds many applications both in practice (e.g. cloud computing) and in the design of new cryptographic algorithms.

Since the seminal work of Gentry in 2009, FHE has become an active research area that revolves around the question how to make FHE efficient. In the recent decade, various schemes and optimisations were proposed that gradually decreased the computational overhead of homomorphic function evaluation. Nevertheless, these schemes still remains impractical for general industrial applications.

In this thesis, we propose and analyse several optimisations for FHE schemes.

First, we demonstrate that the security of the most efficient FHE schemes can be compromised by switching from the RLWE problem to a slightly simpler computational problem. Second, we design several algorithms that efficiently encode real- and complex- valued data for FHE evaluation, thus reducing the computational overhead of homomorphic circuits. Third, we decrease the memory overhead of FHE by generalising the packing technique of Smart and Vercauteren. Using our algorithm, more plaintext messages can be packed into a single ciphertext in comparison to the previous methods.