Revisiting the Slot-to-Coefficient Transformation for BGV and BFV
Authors
Robin Geelen
Robin Geelen
COSIC, KU Leuven, Leuven, Belgium
robin dot geelen at esat dot kuleuven dot be
robin dot geelen at esat dot kuleuven dot be
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.
References
[AP13]
Jacob Alperin-Sheriff and Chris Peikert. Practical Bootstrapping in Quasilinear Time. In CRYPTO (1), volume 8042 of Lecture Notes in Computer Science, pages 1–20. 2013. Springer. DOI: 10.1007/978-3-642-40041-4_1
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. J. Math. Cryptol., 9(3):169–203, 2015. DOI: 10.1515/jmc-2015-0016
[BCK+23]
Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, Jai Hyun Park, and Damien Stehlé. HERMES: Efficient Ring Packing Using MLWE Ciphertexts and Application to Transciphering. In CRYPTO (4), volume 14084 of Lecture Notes in Computer Science, pages 37–69. 2023. Springer. DOI: 10.1007/978-3-031-38551-3_2
[BGGJ20]
Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes. J. Math. Cryptol., 14(1):316–338, 2020. DOI: 10.1515/JMC-2019-0026
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. DOI: 10.1145/2090236.2090262
[BLZ23]
Matvey Borodin, Ethan Liu, and Justin Zhang. Results on Vanishing Polynomials and Polynomial Root Counting with Relevant Technological Applications. In 2023 IEEE MIT Undergraduate Research Technology Conference (URTC), pages 1–5. 2023. IEEE. DOI: 10.1109/URTC60662.2023.10534940
[BMTH21]
Jean-Philippe Bossuat, Christian Mouchet, Juan Ramón Troncoso-Pastoriza, and Jean-Pierre Hubaux. Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys. In EUROCRYPT (1), volume 12696 of Lecture Notes in Computer Science, pages 587–617. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_21
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 868–886. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_50
[BTH22]
Jean-Philippe Bossuat, Juan Ramón Troncoso-Pastoriza, and Jean-Pierre Hubaux. Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation. In ACNS, volume 13269 of Lecture Notes in Computer Science, pages 521–541. 2022. Springer. DOI: 10.1007/978-3-031-09234-3_26
[CCLS19]
Jung Hee Cheon, Hyeongmin Choe, Donghwan Lee, and Yongha Son. Faster Linear Transformations in $\mathsf{HElib}$, Revisited. IEEE Access, 7:50595–50604, 2019. DOI: 10.1109/ACCESS.2019.2911300
[CCS19]
Hao Chen, Ilaria Chillotti, and Yongsoo Song. Improved Bootstrapping for Approximate Homomorphic Encryption. In EUROCRYPT (2), volume 11477 of Lecture Notes in Computer Science, pages 34–54. 2019. Springer. DOI: 10.1007/978-3-030-17656-3_2
[CH18]
Hao Chen and Kyoohyung Han. Homomorphic Lower Digits Removal and Improved FHE Bootstrapping. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer Science, pages 315–337. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_12
[CHK+18]
Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song. Bootstrapping for Approximate Homomorphic Encryption. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer Science, pages 360–384. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_14
[CHK+21]
Jihoon Cho, Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Joohee Lee, Jooyoung Lee, Dukjae Moon, and Hyojin Yoon. Transciphering Framework for Approximate Homomorphic Encryption. In ASIACRYPT (3), volume 13092 of Lecture Notes in Computer Science, pages 640–669. 2021. Springer. DOI: 10.1007/978-3-030-92078-4_22
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In ASIACRYPT (1), volume 10624 of Lecture Notes in Computer Science, pages 409–437. 2017. Springer. DOI: 10.1007/978-3-319-70694-8_15
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2012/144. 2012.
[Gau86]
Carl Friedrich. Gauss. Disquisitiones arithmeticae. Springer, Berlin 1986. DOI: 10.1007/978-1-4939-7560-0
[GHS12a]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Better Bootstrapping in Fully Homomorphic Encryption. In Public Key Cryptography, volume 7293 of Lecture Notes in Computer Science, pages 1–16. 2012. Springer. DOI: 10.1007/978-3-642-30057-8_1
[GHS12b]
Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 465–482. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_28
[GIKV23]
Robin Geelen, Ilia Iliashenko, Jiayi Kang, and Frederik Vercauteren. On Polynomial Functions Modulo $p^e$ and Faster Bootstrapping for Homomorphic Encryption. In EUROCRYPT (3), volume 14006 of Lecture Notes in Computer Science, pages 257–286. 2023. Springer. DOI: 10.1007/978-3-031-30620-4_9
[GV23]
Robin Geelen and Frederik Vercauteren. Bootstrapping for BGV and BFV Revisited. J. Cryptol., 36(2):12, 2023. DOI: 10.1007/S00145-023-09454-6
[HHC19]
Kyoohyung Han, Minki Hhan, and Jung Hee Cheon. Improved Homomorphic Discrete Fourier Transforms and FHE Bootstrapping. IEEE Access, 7:57361–57370, 2019. DOI: 10.1109/ACCESS.2019.2913850
[HS18]
Shai Halevi and Victor Shoup. Faster Homomorphic Linear Transformations in HElib. In CRYPTO (1), volume 10991 of Lecture Notes in Computer Science, pages 93–120. 2018. Springer. DOI: 10.1007/978-3-319-96884-1_4
[HS20]
Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481. 2020.
[HS21]
Shai Halevi and Victor Shoup. Bootstrapping for HElib. J. Cryptol., 34(1):7, 2021. DOI: 10.1007/s00145-020-09368-7
[KPZ21]
Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting Homomorphic Encryption Schemes for Finite Fields. In ASIACRYPT (3), volume 13092 of Lecture Notes in Computer Science, pages 608–639. 2021. Springer. DOI: 10.1007/978-3-030-92078-4_21
[LHH+21]
Wen-jie Lu, Zhicong Huang, Cheng Hong, Yiping Ma, and Hunter Qu. PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption. In SP, pages 1057–1073. 2021. IEEE. DOI: 10.1109/SP40001.2021.00043
[LPR13]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A Toolkit for Ring-LWE Cryptography. In EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 35–54. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_3
[LS18]
Vadim Lyubashevsky and Gregor Seiler. Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer Science, pages 204–224. 2018. Springer. DOI: 10.1007/978-3-319-78381-9_8
[LW23a]
Feng-Hao Liu and Han Wang. Batch Bootstrapping I: - A New Framework for SIMD Bootstrapping in Polynomial Modulus. In EUROCRYPT (3), volume 14006 of Lecture Notes in Computer Science, pages 321–352. 2023. Springer. DOI: 10.1007/978-3-031-30620-4_11
[LW23b]
Zeyu Liu and Yunhao Wang. Amortized Functional Bootstrapping in Less than 7 ms, with $\tilde{O}(1)$ Polynomial Multiplications. In ASIACRYPT (6), volume 14443 of Lecture Notes in Computer Science, pages 101–132. 2023. Springer. DOI: 10.1007/978-981-99-8736-8_4
[MHWW24a]
Shihe Ma, Tairong Huang, Anyu Wang, and Xiaoyun Wang. Accelerating BGV Bootstrapping for Large $p$ Using Null Polynomials over $\mathbb{Z}_{p^e}$. In EUROCRYPT (2), volume 14652 of Lecture Notes in Computer Science, pages 403–432. 2024. Springer. DOI: 10.1007/978-3-031-58723-8_14
[MHWW24b]
Shihe Ma, Tairong Huang, Anyu Wang, and Xiaoyun Wang. Faster BGV Bootstrapping for Power-of-Two Cyclotomics through Homomorphic NTT. Cryptology ePrint Archive, Paper 2024/164. 2024.
[OPP23]
Hiroki Okada, Rachel Player, and Simon Pohmann. Homomorphic Polynomial Evaluation Using Galois Structure and Applications to BFV Bootstrapping. In ASIACRYPT (6), volume 14443 of Lecture Notes in Computer Science, pages 69–100. 2023. Springer. DOI: 10.1007/978-981-99-8736-8_3
[SEA23]
Microsoft SEAL (release 4.1). Microsoft Research, Redmond, WA.. https://github.com/Microsoft/SEAL. January 2023.
[SV14]
Nigel P. Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. Des. Codes Cryptogr., 71(1):57–81, 2014. DOI: 10.1007/s10623-012-9720-4
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Robin Geelen, Revisiting the Slot-to-Coefficient Transformation for BGV and BFV. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a01zogy4e-.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.