Fully homomorphic encryption over the [discretized] torus

Fully Homomorphic Encryption (FHE) allows users to perform computations on encrypted data. Recent developments have meant that, today, both the public and private sectors are embracing this new security paradigm and are actively working to make FHE more practical and easier to use.

In this paper, to be presented at CHES 2022 (24th Conference on Cryptographic Hardware and Embedded Systems, Leuven, Belgium in September 18-21, 2022), we explain the inner-workings of TFHE, a torus-based fully homomorphic encryption scheme, and the scheme on which our Concrete framework is based. We describe its implementation on a discretized version of the torus. We also explain in detail the technique of programmable bootstrapping.

There are basically two main families of FHE schemes: those encoding plaintexts in the upper position and those encoding plaintexts in the lower position. For LWE-based schemes in the first family, the discretized torus is the right structure to use for the description as then it clearly appears that any sub-module 𝕋_pof 𝕋_q is a valid plaintext space. In particular, this explains that various message formats (i.e., beyond bits as in the original description) can be supported provided one constructs an encoding mapping an input message to an element to sub-module 𝕋_p. Furthemore, the torus being not a ring, using the discretized torus for the description explains why (internal) multiplication of ciphertexts is not natively supported: the product of two torus elements is not defined. One has to resort to a different scheme; i.e., one encrypting plaintexts that are integers (modulo q) like the TGSW scheme reviewed in the paper. Hence, if someone wants to define a new multiplication of ciphertexts, a FHE scheme encrypting plaintexts that are integers modulo q must be identified. Moreover, for good performance, the resulting external product must be efficient and have a small impact on the noise propagation.

Importantly, our paper explains ”why” (and not only ”how”) bootstrapping works. It makes clear that bootstrapping on the discretized torus is simply an application of Gentry’s original 'recryption' technique. LWE decryption mainly involves two steps: a linear combination and a (non-linear) rounding operation. The difficult operation is the rounding, which is done over the discretized torus using a rotation with polynomials. This observation shows that a possible direction to improve the bootstrapping operation is to find a better way to do the rounding, since bootstrapping is currently the most critical operation in FHE schemes. Furthermore, this explanation for bootstrapping directly explains how bootstrapping extends to programmable bootstrapping, thus leading to functional circuits.