Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE

This chapter delves into the advancements and optimizations of fully homomorphic encryption (FHE) schemes, with a particular emphasis on second-generation exact FHE. The text begins by discussing the historical progress and current state of FHE, highlighting the importance of efficiency and flexibility in these schemes. It then focuses on two key techniques: SIMD packing and bootstrapping. SIMD packing allows for the encryption of multiple values into a single ciphertext, enabling parallel homomorphic operations and significant efficiency gains. Bootstrapping, on the other hand, is crucial for reducing noise in ciphertexts, allowing for the evaluation of arbitrary functions. The chapter explores the limitations of cyclotomic number fields, which have been traditionally used in FHE, and introduces decomposition subfields as a promising alternative. These subfields offer optimal SIMD packing and efficient bootstrapping, addressing the inefficiencies and constraints of cyclotomic fields. The text also provides a detailed framework for implementing these techniques, including the construction of short, structured bases for abelian number rings and the definition of CRT bases for efficient ring arithmetic. Additionally, it discusses the application of these techniques to homomorphic encryption, highlighting their potential to enhance the performance and utility of FHE. The chapter concludes with a discussion on the broader implications of these advancements, suggesting that they will be useful for various applications in ring-based cryptography beyond FHE.