Welcome to the resource topic for 2023/014
Title:
Amortized Bootstrapping Revisited: Simpler, Asymptotically-faster, Implemented
Authors: Antonio Guimarães, Hilder V. L. Pereira, Barry van Leeuwen
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 can 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.5 + \rho}). 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 provide a C++ implementation of our algorithm, thus showing that the amortized bootstrapping is not only theoretical, but practical. Moreover, it is up to 2.7 times faster than an equivalent non-amortized version for the smallest parameter set we consider, and gains are expected to increase as the parameters increase.
ePrint: https://eprint.iacr.org/2023/014
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .