TFHE Bootstrapping: Faster, Smaller and Time-Space Trade-Offs

Fully homomorphic encryption (FHE) allows for computation on encrypted data, providing effective privacy protection in data processing scenarios such as cloud computing and machine learning. However, the efficiency and storage overhead of the FHE bootstrapping algorithm remains challenges. The TFHE scheme, proposed by Chillotti et al., offers the fastest bootstrapping among all existing FHE solutions. This scheme has two homomorphic evaluation modes: the LHE mode, which uses circuit bootstrapping; and the FHE mode, which relies on functional bootstrapping. This paper presents four improved bootstrapping algorithms designed to enhance the efficiency and practicality of TFHE applications. Contributions can be summarized as twofold: