[Resource Topic] 2023/357: FFT-less TFHE: Simpler, Faster and Scale-invariant

Welcome to the resource topic for 2023/357

FFT-less TFHE: Simpler, Faster and Scale-invariant

Authors: Zhen Gu, Wen-jie Lu, Cheng Hong


Fully homomorphic encryption FHE has been one of the most promising cryptographic tools for secure two-party computation and secure outsourcing computation in recent years. However, the complex bootstrapping procedure in FHE schemes is the main bottleneck of it practical usage, and the TFHE scheme is the state-of-the-art for efficient bootstrapping. To further improve the efficiency of bootstrapping in TFHE, the number of fast Fourier transforms (FFT) should be reduced since bootstrapping in TFHE is mainly composed of vast FFTs. In this paper, we focus on a novel method of decomposing-in-Fourier (DIF) to reduce the number of FFTs in bootstrapping of TFHE, from 2(\ell+1)n to 4n. As a result, our method would reduce the number of FFTs required by each external product in bootstrapping to a constant number rather than varying with decomposing parameters, which leads to a scale-invariant bootstrapping structure.

ePrint: https://eprint.iacr.org/2023/357

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .