Welcome to the resource topic for 2023/112
Title:
Faster Amortized FHEW bootstrapping using Ring Automorphisms
Authors: Gabrielle De Micheli, Duhyeong Kim, Daniele Micciancio, Adam Suhl
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.
ePrint: https://eprint.iacr.org/2023/112
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 .