Paper 2024/155

Fully Homomorphic Encryption on large integers

Abstract

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 polynomial 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 × \cdots × 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, determine practical parameters to reach a given correctness threshold and present implementation results.