An Algebraic Perspective on the BGV and BFV Homomorphic Encryption Schemes

This thesis presents theoretical and implementation aspects of efficient homomorphic function evaluation in the context of Homomorphic Encryption (HE). Our main focus is on the BFV/BGV family of HE schemes, which consists of the BFV, BGV, CLPX/GBFV and dBFV schemes. One of its key features is the fact that the plaintext space of these schemes has a very rich algebraic structure. Therefore, we successfully apply algebraic methods to investigate and improve homomorphic function evaluation in this context.

In Chapter 3 of this thesis, we present the HE software library Fheanor, which we developed to address the lack of research-focused software in the HE community. Indeed, previous libraries are primarily designed for application developers, and usually hide the mathematical and cryptographic structure of the implemented HE schemes from the user. As opposed to that, the approach of Fheanor is to expose an API that reflects the algebraic structure of the schemes in question, while still hiding implementation detail. As a result, Fheanor is better suited for building prototypes and experimenting with new ideas in the HE space.

Chapter 4 presents multiple new approaches for the arithmetisation problem, that is the problem of expressing a desired function as a sequence of basic arithmetic operations. Firstly, we explore a new method for computational arithmetisation using a SAT solver, and apply it to the so-called digit extraction polynomials, which play an important role in all BFV/BGV-style schemes. Furthermore, we revisit the well-known fact that the computational model of BFV/BGV-style schemes can be extended to allow the use of Galois automorphisms. Based on this, we present different techniques that can exploit the Galois structure to achieve faster polynomial evaluation than was possible in the classical model.

Chapter 5 goes beyond classical arithmetisation, and investigates the recently proposed concept of Algebraic (Somewhat) Homomorphic Encryption (ASHE). ASHE schemes form a subset of HE schemes, and additionally require homomorphic arithmetic operations to be directly realised by the corresponding arithmetic operations on ciphertexts. We show that this very strong property limits the performance of ASHE schemes, and based on this, investigate ways to improve performance of existing ASHE schemes by relaxing the ASHE condition.

Finally, Chapter 6 is concerned with Doubly-Efficient Private Information Retrieval (DEPIR), which is the main application of ASHE. The first theoretical instantiation of DEPIR was proposed by Lin, Mook and Wichs in 2023, however it was believed to involve astronomical runtime costs in practice. We present various optimisations to their construction, including some based on our results from Chapter 5. While we conclude that DEPIR is currently not yet practical, our progress reduces the concrete costs to a point that is manageable on modern hardware. This allows us to present and evaluate the first implementation of DEPIR.