CryptoDB
Revisiting the Slot-to-Coefficient Transformation for BGV and BFV
| Authors: |
|
|---|---|
| Download: | |
| 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 GF(8191^8). We also study a fully packed bootstrapping operation that refreshes 2^15 elements from GF(65537) and obtain an amortized speedup of 12 times. |
BibTeX
@article{cic-2024-34848,
title={Revisiting the Slot-to-Coefficient Transformation for BGV and BFV},
journal={cic},
publisher={International Association for Cryptologic Research},
volume={1, Issue 3},
url={https://cic.iacr.org//p/1/3/37},
doi={10.62056/a01zogy4e-},
author={Robin Geelen},
year=2024
}