Abstract
This lecture continued the study of fully homomorphic encryption begun in the previous lecture. After a reminder of the approach introduced by Gentry in 2009, which combines weakly homomorphic encryption and bootstrap procedure, we studied three directions to make this approach more usable.
The first direction is the use of weakly homomorphic ciphers based on the LWE (Learning With Errors)problem and its RLWE and GLWE variants. The LWE problem, introduced by Regev in 2005, is a generalization of the LPN (Learning Parity with Noise) problem, well known in coding theory and statistical learning theory, as well as the CVP (Closest Vector Problem) problem on Euclidean networks. LWE makes it possible to construct elegant, post-quantum, weakly homomorphic encryption schemes for addition and multiplication by a constant.
The second direction is to improve the homomorphic multiplication operation so that it introduces less noise into the results. We have detailed the BGV approach proposed by Brakerski, Gentry, and Vaikuntanathan in 2012, which performs a modulus reduction step after each multiplication, in order to keep the noise quasi-constant in absolute value. This significantly increases the multiplicative depth of circuits that can be homomorphically evaluated without resorting to bootstrapping.
The third direction aims to make the bootstrap procedure less costly. We studied the FHEW/TFHE approach proposed by Chillotti, Gama, Georgieva and Izabachène in 2016, which relies on homomorphic indexed access in a table of constants calculated and encrypted in advance. Combined with a key change and a module change, this table-based approach leads to a programmable bootstrap, which not only reduces noise but also homomorphically computes a function of plaintext in plaintext.
