Paper 2023/014

Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented

Antonio Guimarães, University of Campinas, Brazil
Hilder V. L. Pereira, imec-COSIC, KU Leuven, Leuven, Belgium
Barry van Leeuwen, COSIC, KU Leuven, Leuven, Belgium

Micciancio and Sorrel (ICALP 2018) proposed a bootstrapping algorithm that can refresh many messages at once with sublinearly many homomorphic operations per message. However, despite the attractive asymptotic cost, it is unclear if their algorithm could ever be practical, which reduces the impact of their results. In this work, we follow their general framework, but propose an amortized bootstrapping that is conceptually simpler and asymptotically cheaper. We reduce the number of homomorphic operations per refreshed message from $O(3^\rho \cdot n^{1/\rho} \cdot \log n)$ to $O(\rho \cdot n^{1/\rho})$, and the noise overhead from $\tilde{O}(n^{2 + 3 \cdot \rho})$ to $\tilde{O}(n^{1 + \rho})$. We also make it more general, by handling non-binary messages and applying programmable bootstrapping. To obtain a concrete instantiation of our bootstrapping algorithm, we propose a double-CRT (aka RNS) version of the GSW scheme, including a new operation, called shrinking, used to speed-up homomorphic operations by reducing the dimension and ciphertext modulus of the ciphertexts. We also provide a C++ implementation of our algorithm, thus showing for the first time the practicability of the amortized bootstrapping. Moreover, it is competitive with existing bootstrapping algorithms, being even around 3.4 times faster than an equivalent non-amortized version of our bootstrapping.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Fully Homomorphic EncryptionBootstrappingLattice-based Cryptography
Contact author(s)
antonio guimaraes @ ic unicamp br
hildervitor limapereira @ kuleuven be
barry vanleeuwen @ kuleuven be
2023-11-23: last of 2 revisions
2023-01-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Antonio Guimarães and Hilder V. L. Pereira and Barry van Leeuwen},
      title = {Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented},
      howpublished = {Cryptology ePrint Archive, Paper 2023/014},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.