Paper 2023/357

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

Zhen Gu, Alibaba Group (China)
Wen-jie Lu, Alibaba Group (China)
Cheng Hong, Alibaba Group (China)
Abstract

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.

Metadata
Available format(s)
-- withdrawn --
Category
Foundations
Publication info
Preprint.
Keywords
TFHEBootstrapFFTFHEHomomorphic Encryption
Contact author(s)
guzhen gz @ alibaba-inc com
juhou lwj @ alibaba-inc com
vince hc @ alibaba-inc com
History
2023-04-15: withdrawn
2023-03-11: received
See all versions
Short URL
https://ia.cr/2023/357
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.