Surpassing the Word Size Limitation of TFHE with Noise Calibration

Torus fully homomorphic encryption (TFHE) is a promising solution for secure computation, offering low computational cost and simple setup requirements. A key feature of TFHE is programmable bootstrap (PBS), which enables efficient homomorphic evaluation of arbitrary functions over small domains. However, the domain size of PBS is constrained by the word size limitation of TFHE, an unavoidable restriction to ensure data security. This limitation raises scalability challenges for extending homomorphic function evaluation to larger domains. Existing approaches attempt to overcome this limitation but suffer from high computational costs. The vertical packing technique (Chillotti et al., 2020) supports function evaluations beyond the word size limitation but depends on circuit bootstrap, a computationally expensive primitive. The tree-based method (Guimarães et al., 2021) avoids using circuit bootstrap but introduces significant computational overhead, requiring O(2W) PBS calls for a W-bit domain.