Paper 2023/014
Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented
Abstract
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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2023
- Keywords
- Fully Homomorphic EncryptionBootstrappingLattice-based Cryptography
- Contact author(s)
-
antonio guimaraes @ ic unicamp br
hildervitor limapereira @ kuleuven be
barry vanleeuwen @ kuleuven be - History
- 2023-11-23: last of 2 revisions
- 2023-01-03: received
- See all versions
- Short URL
- https://ia.cr/2023/014
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/014, 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}, url = {https://eprint.iacr.org/2023/014} }