Paper 2024/1318

Patching and Extending the WWL+ Circuit Bootstrapping Method to FFT Domains

Abstract

TFHE is a homomorphic encryption scheme supporting fast bootstrapping. There are two kinds of bootstrapping in TFHE: programmable bootstrapping (also known as gate bootstrapping) and circuit bootstrapping. Circuit bootstrapping offers more functionality than programmable bootstrapping, but requires heavier computational cost and larger evaluation key size. A recent work by Wang et al. improving circuit bootstrapping using homomorphic trace evaluation seems to mitigate its heavy cost, while we observe some flaws in their error analysis. In this paper, we patch the circuit bootstrapping method proposed by Wang et al. with correct error analysis and extend the ciphertext modulus from a prime modulus to a power-of-two modulus, enabling FFT-based implementation of our patched method. In addition, we propose a high precision WWL+ method by adopting GLWE keyswitching, improving the circuit bootstrapping time (resp. key size) of WoP-PBS proposed by Bergerat et al. by factors from $3.26$ to $7.22$ (resp. $2.39$ to $2.63$). We also patch the parameter selection used in the AES evaluation by the WWL+ method, obtaining $26.301$s for a single AES evaluation in a single thread.