Foundations of FHE
Abstract: We will start with a high level introduction to fully homomorphic encryption (FHE), showing a general strategy to build homomorphic schemes that can evaluate circuits of bounded size, then we will understand the bootstrapping, which is the central operation in FHE, as it is responsible for transforming a “bounded” homomorphic scheme into a fully homomorphic one. Then, we will study FHE in more depth by first learning about the two main problems used to construct FHE, namely, the learning with errors and the ring learning with errors, then seeing one example of a scheme built on top of them, the BGV scheme. This will also allow us to understand the main operations and characteristics of current FHE schemes, such as modulus switching, key switching, and SIMD (single-instruction, multiple-data). Finally, we will briefly discuss several other existing schemes and understand when each one can be used.
Bio: Hilder Vitor Lima Pereira is a postdoctoral researcher at COSIC, KU Leuven, working mainly with fully homomorphic encryption (FHE), from theory to practice. On the theoretical side, he has proposed new homomorphic schemes and has studied how different hardness assumptions can be used to construct FHE. For example, he proposed the first FHE scheme based on the approximate-GCD problem (aka FHE over the integers) with bootstrapping running in less than one second, the first FHE scheme mixing the NTRU and the LWE problems, and the first practical amortized bootstrapping with sublinearly operations per refreshed message. On the practical side, he has been involved in implementing FHE schemes, in designing hardware accelerators for FHE and in applying FHE to practical problems, such as queries on encrypted databases and machine learning over encrypted data.