Fully Homomorphic Encryption: Advanced Techniques and Optimizations - Session 2

Explore a comprehensive session from Eurocrypt 2023 focused on Fully Homomorphic Encryption (FHE). Delve into the current state of the art, limitations, and tradeoffs of FHE technology. Examine the bootstrapping framework, technical barriers for SIMD, and a new mathematical framework for addressing challenges. Learn about instantiations of tensor fields/rings, homomorphic computation structures, and applications to FHEW-like algorithms. Investigate error growth in batch FHEW, parameter selection for rings, and comparative results. Discover optimizations through recursive Nussbaumer transforms and DFT-based polynomial multiplications. Gain insights into cutting-edge research and advancements in the field of fully homomorphic encryption.

Intro
Fully Homomorphic Encryption
Noise Grows with Computation
Need to Clean Noise
Bootstrapping Framework [Gentry]
Current State of the Art
Limitations and Tradeoffs
Fundamental Question
Recap of (R)LWE and RGSW
Recap of FHEW-like Bootstrapping
Technical Barriers for SIMD
New Mathematical Framework
Final Solution - Reuse Rings
Instantiations of Tensor Fields/Rings
Summary
Homomorphic Comp of the Framework
Overall Computation Structure
Application to FHEW-like Algorithms
Error Growth for Batch FHEW
Parameters of the Rings
Results and Comparison
High Level Question
(Recursive) Nussbaumer Transform [MS18]
DFT-based Polynomial Multiplications [MS18]
Optimization by Recursion
FHEW with Nussbaumer Transform