Paper 2024/1318

FHEW-like Leveled Homomorphic Evaluation: Refined Workflow and Polished Building Blocks

Abstract

In FHEW-like cryptosystems, the leveled homomorphic evaluation (LHE) mode performs bootstrapping after circuit evaluation rather than after each gate. The core procedure and the performance bottleneck are known as circuit bootstrapping (CBS). This paper revisits the LHE mode by refining the workflow and proposing polished building blocks: 1. Algorithmic Enhancements - We introduce an NTT-based CBS algorithm, patched from WWL+ [Eurocrypt24], achieving up to a 2.9$\times$ efficiency improvement. - We present an FFT-based CBS that is 3.5$\times$ faster than the most efficient FFT-CBS implementation, with a key size reduction of 37.5$\times$. 2. Refined Leveled Homomorphic Evaluation and Applications - We propose the $\mathsf{HalfCBS}$ algorithm, which is 2.4$\times$ faster than the traditional CBS algorithm, enabling a flexible leveled evaluation. - By applying these improvements to evaluate general look-up tables (LUTs), we can evaluate a 16-8 LUT in 311 ms, which is $2^{13.61} \times$ faster than the trivial FHE mode implementation. - When applied to AES transciphering, our enhancements yield a 2.9$\times$ improvement in efficiency and a 31.6$\times$ reduction in key size compared to the state of the art, Thunderbird [TCHES24]. 3. High-Precision LHE - To handle multi-bit inputs, we propose a high-precision LHE framework. Compared to the WoP-PBS [JoC23], the compute efficiency (resp. key size) is improved by factors from 9.7 to 16.2 (resp. 3.4 to 4.4) according to the parameters.