Paper 2023/979

Faster Secret Keys for (T)FHE

Abstract

GLWE secret keys come with some associated public information, like their size or the distribution probability of their coefficients. Those information have an impact on the FHE algorithms, their computational cost, their noise growth, and the overall security level. In this paper, we identify two limitations with (T)FHE: there is no fine-grained control over the size of a GLWE secret key, and there is a minimal noise variance which leads to an unnecessary increment of the level of security with large GLWE secret keys. We introduce two (non exclusive) new types of secret keys for GLWE-based cryptosystems, that are designed to overcome the aforementioned limitations. We explain why these are as secure as the traditional ones, and detail all the improvements that they brought to the FHE algorithms. We provide many comparisons with state-of-the-art TFHE techniques, and benchmarks showing computational speed-ups between $1.3$ and $2.4$ while keeping the same level of security and failure probability. Furthermore, the size of the public material (i.e., key switching and bootstrapping keys) is also reduced by factors from $1.5$ and $2.7$.