Paper 2023/112

Faster Amortized FHEW bootstrapping using Ring Automorphisms

Gabrielle De Micheli, University of California, San Diego
Duhyeong Kim, Intel
Daniele Micciancio, University of California, San Diego
Adam Suhl, University of California, San Diego

Amortized bootstrapping offers a way to simultaneously refresh many ciphertexts of a fully homomorphic encryption scheme, at a total cost comparable to that of refreshing a single ciphertext. An amortization method for FHEW-style cryptosystems was first proposed by (Micciancio and Sorrell, ICALP 2018), who showed that the amortized cost of bootstrapping n FHEW-style ciphertexts can be reduced from $O(n)$ basic cryptographic operations to just $O(n^{\epsilon})$, for any constant $\epsilon>0$. However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the asymptotic notation. In this work, we propose an alternative amortized boostrapping method with much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost, but with a hidden constant that is only linear in $1/\epsilon$, and with reduced noise growth. This is achieved following the general strategy of (Micciancio and Sorrell), but replacing their use of the Nussbaumer transform, with a much more practical Number Theoretic Transform, with multiplication by twiddle factors implemented using ring automorphisms. A key technical ingredient to do this is a new "scheme switching" technique proposed in this paper which may be of independent interest.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PKC 2024
Fully Homomorphic EncryptionRing Learning With ErrorsFHEWbootstrappingscheme switching
Contact author(s)
gdemicheli @ eng ucsd edu
duhyeong kim @ intel com
daniele @ cs ucsd edu
asuhl @ ucsd edu
2024-03-29: revised
2023-01-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gabrielle De Micheli and Duhyeong Kim and Daniele Micciancio and Adam Suhl},
      title = {Faster Amortized {FHEW} bootstrapping using Ring Automorphisms},
      howpublished = {Cryptology ePrint Archive, Paper 2023/112},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.