🗓️ The next FHE.org meetup has been scheduled for next week, Thursday, July 17th at 3pm CEST (Paris, FR).
This meetup features Antonio Guimarães, postdoctoral researcher at IMDEA Software Institute, presenting Fast Amortized Bootstrapping with Small Keys and Polynomial Noise Overheads.
Most homomorphic encryption (FHE) schemes exploit a technique called single-instruction multiple-data (SIMD) to process several messages in parallel. However, they base their security in somehow strong assumptions, such as the hardness of approximate lattice problems with superpolynomial approximation factor. On the other extreme of the spectrum, there are lightweight FHE schemes that have much faster bootstrapping but no SIMD capabilities. On the positive side, the security of these schemes is based on lattice problems with (low degree) polynomial approximation factor only, which is a much weaker security assumption. Aiming the best of those two options, Micciancio and Sorrell (ICALP'18) proposed a new amortized bootstrapping that can process many messages at once, yielding sublinear time complexity per message, and allowing one to construct FHE based on lattice problems with polynomial approximation factor. Some subsequent works on this line achieve near-optimal asymptotic performance, nevertheless, concrete efficiency remains mostly an open problem. The only existing implementation to date (GPV23, Asiacrypt 2023) requires keys of up to a hundred gigabytes while only providing gains for relatively large messages.
In this paper, we introduce a new method for amortized bootstrapping where the number of homomorphic operations required per message is O(h) and the noise overhead is O(sqrt(h\lambda) log(\lambda)), where h is the Hamming weight of the LWE secret key and \lambda is the security parameter. This allows us to use much smaller parameters and to obtain faster running time. Our method is based on a new efficient homomorphic evaluation of sparse polynomial multiplication. We bootstrap 2 to 8-bit messages in 1.1 ms to 26.5 ms, respectively. Compared to TFHE-rs, this represents a performance improvement of 3.9 to 41.5 times while requiring bootstrapping keys up to 50.4 times smaller.
About the speaker
Antonio Guimarães is a postdoctoral researcher at IMDEA Software Institute in Madrid, Spain. His research interests include all practical aspects of Fully Homomorphic Encryption (FHE), with particular focus on verifiable FHE, fast bootstrapping algorithms, and efficient homomorphic evaluation of cryptographic primitives.
Platform Note
We’ve recently switched from using Zoom for our meetups to Google Meet. The meetup link will remain the same (https://fhe.org/meetups/join). If you have any issues getting into the new meetup, please email us at contact@fhe.org.
Never miss an update
Join the discord server to discuss FHE related topics with the community: discord.fhe.org.
