Paper 2024/153
Revisiting the Slot-to-Coefficient Transformation for BGV and BFV
, KU LeuvenAbstract
Numerous algorithms in homomorphic encryption require an operation that moves the slots of a ciphertext to the coefficients of a different ciphertext. We describe an FFT-like method for decomposing this slot-to-coefficient transformation (and its inverse) for BGV and BFV. The proposed method is specific to power-of-two cyclotomic rings and can handle both fully and sparsely packed slots. Previously, such a method was only known for non-power-of-two cyclotomic rings. Our algorithm admits more freedom in the complexity-depth trade-off than prior works. Moreover, it brings down the computational complexity of the slot-to-coefficient transformation from a linear to a logarithmic number of FHE operations in the best case, which is shown via a detailed complexity analysis. We also provide a proof-of-concept implementation in the Magma bootstrapping library.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Homomorphic encryptionLinear transformationsBGVBFV
- Contact author(s)
- robin geelen @ esat kuleuven be
- History
- 2024-02-05: approved
- 2024-02-02: received
- See all versions
- Short URL
- https://ia.cr/2024/153
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/153,
author = {Robin Geelen},
title = {Revisiting the Slot-to-Coefficient Transformation for BGV and BFV},
howpublished = {Cryptology ePrint Archive, Paper 2024/153},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/153}},
url = {https://eprint.iacr.org/2024/153}
}
