International Association for Cryptologic Research

International Association
for Cryptologic Research


Faster Amortized FHEW bootstrapping using Ring Automorphisms

Gabrielle De Micheli , UCSD
Duhyeong Kim , Intel
Daniele Micciancio , UCSD
Adam Suhl , UCSD
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2024
Abstract: 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 $\tilde O(n)$ basic cryptographic operations to just $\tilde 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.
  title={Faster Amortized FHEW bootstrapping using Ring Automorphisms},
  author={Gabrielle De Micheli and Duhyeong Kim and Daniele Micciancio and Adam Suhl},