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
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 $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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
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
History
2023-01-30: approved
2023-01-29: received
See all versions
Short URL
https://ia.cr/2023/112
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/112,
      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{https://eprint.iacr.org/2023/112}},
      url = {https://eprint.iacr.org/2023/112}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.