[Resource Topic] 2024/155: Fully Homomorphic Encryption on large integers

Welcome to the resource topic for 2024/155

Fully Homomorphic Encryption on large integers

Authors: Philippe Chartier, Michel Koskas, Mohammed Lemou, Florian Méhats


At the core of fully homomorphic encryption lies a procedure to refresh the ciphertexts whose noise component has grown too big. The efficiency of the so-called bootstrap is of paramount importance as it is usually regarded as the main bottleneck towards a real-life deployment of fully homomorphic crypto-systems. In two of the fastest implementations so far, the space of messages is limited to binary integers. If the message space is extended to the discretized torus T_{p_i} or equivalently to Z_{p_i} with values of p_i large as compared to the dimension of the quotient ring in which the operations are realised, the bootstrap delivers incorrect results with far too high probability. As a consequence, the use of a residue numeral system to address large integers modulo p=p_1 \times \ldots \times p_\kappa would be of limited interest in practical situations without the following remedy: rather than increasing the polynomial degree and thus the computational cost, we introduce here a novel and simple technique (hereafter referred to as ``collapsing") which, by grouping the components of the mask, attenuates both rounding errors and computational costs, and greatly helps to sharpen the correctness of the bootstrap. We then rigorously estimate the probability of success as well as the output error and determine practical parameters to reach a given correctness threshold.

ePrint: https://eprint.iacr.org/2024/155

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .