Paper 2022/704

Parameter Optimization & Larger Precision for (T)FHE

Abstract

In theory, Fully Homomorphic Encryption schemes allow to compute any operation over encrypted data. However in practice, one of the major difficulties lies into determining secure cryptographic parameters that reduce the computational cost of evaluating a circuit. In this paper, we propose a framework of optimization to solve this open problem. Even though it mainly focuses on TFHE, the method is generic enough to be adapted to any FHE scheme. As an application, this framework allows us to design solutions to efficiently increase the precision initially supported by the TFHE scheme to large integers. Beyond the classical radix encoding of plaintexts, we propose an alternative representation making use of the Chinese Remainder Theorem, which is particularly suited for parallel computation. We show how to evaluate operations on these new ciphertext types, from basic arithmetic operations, to more complex ones, such as the evaluation of a generic look-up table. The latter relies on a new efficient way to evaluate a programmable bootstrapping. Finally, we propose a plethora of applications of the optimization framework, such as true comparisons between bootstrapping operators, i.e. not only on the computation time but also on the amount of output error and more importantly the probability of failure all at once.