Paper 2024/153 Original: eprint.iacr.org/2024/153 ↗

Revisiting the Slot-to-Coefficient Transformation for BGV and BFV

Abstract

Numerous applications in homomorphic encryption require an operation that moves the slots of a ciphertext to the coefficients of a different ciphertext. For the BGV and BFV schemes, the only efficient algorithms to implement this slot-to-coefficient transformation were proposed in the setting of non-power-of-two cyclotomic rings. In this paper, we devise an FFT-like method to decompose the slot-to-coefficient transformation (and its inverse) for power-of-two cyclotomic rings. The proposed method can handle both fully and sparsely packed slots. Our algorithm brings down the computational complexity of the slot-to-coefficient transformation from a linear to a logarithmic number of FHE operations, which is shown via a detailed complexity analysis. The new procedures are implemented in Microsoft SEAL for BFV. The experiments report a speedup of up to $44\times$ when packing $2^{12}$ elements from $\operatorname{GF}(8191^8)$. We also study a fully packed bootstrapping operation that refreshes $2^{15}$ elements from $\operatorname{GF}(65537)$ and obtain an amortized speedup of $12\times$.