Security and Encoding in Fully Homomorphic Encryption - Rachel Player, Sorbonne Université

Explore the intricacies of Fully Homomorphic Encryption (FHE) in this 45-minute talk by Rachel Player from Sorbonne Université. Delve into the security aspects of lattice-based cryptography, focusing on Ring Learning with Errors (Ring-LWE) problem-based FHE schemes. Examine the selection of secure Ring-LWE parameters and compare differing estimates used in NIST post-quantum cryptography process submissions. Investigate the impact of encoding raw data into plaintext space on efficiency, and learn about a Fan-Vercauteren FHE scheme variant that offers a convenient plaintext space for encoding and enables higher-depth circuit evaluation. Gain insights into topics such as the Learning with Errors problem, Bounded Distance Decoding, security arguments for the FV scheme, algorithms for solving LWE, and the NIST post-quantum standardization process.

Intro
What is homomorphic encryption?
Achieving homomorphic encryption
Applications of homomorphic encryption
Is homomorphic encryption practical?
The Learning with Errors problem (LWE)
LWE parameters
The Bounded Distance Decoding (BDD) problem
The Ring-LWE problem
Security argument for the FV scheme?
Algorithms for solving LWE
NIST post-quantum standardisation process
Estimating NTRU-based schemes in the LWE estimator
Estimating cost of Lattice reduction
Implementing the SVP oracle
Translating asymptotics into concrete cost
Cost models used in NIST proposal
Need to ensure correctness of decoding
Examples: binary and balanced base-B encoding
Other choices for comparison
Maximal depth and noise