Paper 2023/413

Accelerating HE Operations from Key Decomposition Technique

Miran Kim, Hanyang University
Dongwon Lee, Seoul National University
Jinyeong Seo, Seoul National University
Yongsoo Song, Seoul National University

Lattice-based homomorphic encryption (HE) schemes are based on the noisy encryption technique, where plaintexts are masked with some random noise for security. Recent advanced HE schemes rely on a decomposition technique to manage the growth of noise, which involves a conversion of a ciphertext entry into a short vector followed by multiplication with an evaluation key. Prior to this work, the decomposition procedure turns out to be the most time-consuming part, as it requires discrete Fourier transforms (DFTs) over the base ring for efficient polynomial arithmetic. In this paper, an expensive decomposition operation over a large modulus is replaced with relatively cheap operations over a ring of integers with a small bound. Notably, the cost of DFTs is reduced from quadratic to linear with the level of a ciphertext without any extra noise growth. We demonstrate the implication of our approach by applying it to the key-switching procedure. Our experiments show that the new key-switching method achieves a speedup of 1.2-2.3 or 2.1-3.3 times over the previous method, when the dimension of a base ring is $2^{15}$ or $2^{16}$, respectively.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2023
Homomorphic EncryptionGadget DecompositionKey Switching
Contact author(s)
miran @ hanyang ac kr
dongwonlee95 @ snu ac kr
jinyeong seo @ snu ac kr
y song @ snu ac kr
2023-10-28: last of 2 revisions
2023-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Miran Kim and Dongwon Lee and Jinyeong Seo and Yongsoo Song},
      title = {Accelerating HE Operations from Key Decomposition Technique},
      howpublished = {Cryptology ePrint Archive, Paper 2023/413},
      year = {2023},
      doi = {10.1007/978-3-031-38551-3_3},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.