🗓️ The next FHE.org meetup has been scheduled for next week, Thursday, July 3rd at 2pm CEST (Paris, FR).
This meetup features Olivier Bernard, a Cryptology researcher at Zama, presenting Bootstrapping (T)FHE Ciphertexts via Automorphisms: Closing the Gap Between Binary and Gaussian Keys.
The GINX method in TFHE enables low-latency ciphertext bootstrapping with relatively small bootstrapping keys, but is limited to binary or ternary key distributions. In contrast, the AP method supports arbitrary key distributions, however at the cost of significantly large bootstrapping keys. Building on AP, automorphism-based methods (LMK⁺, EUROCRYPT 2023) achieve smaller keys, though each automorphism application necessitates a key switch, introducing computational overhead and noise.
This paper advances automorphism-based methods in two important ways. First, it proposes a novel traversal blind rotation algorithm that optimizes the number of key switches for a given key material. Second, it introduces a new external product that is automorphism-parametrized and seamlessly applies an automorphism to one of the input ciphertexts. Together, these techniques substantially reduce the number of key switches, resulting in faster bootstrapping and improved noise control. As an independent contribution, this paper also introduce a comprehensive theoretical framework for analyzing the expected number of automorphism key switches, whose predictions perfectly align with the results of extensive numerical experiments, demonstrating its practical relevance.
In a typical setting, by utilizing additional key material, the LLW⁺ approach (TCHES 2024) reduces key switches by 17% compared to LMK⁺. Our combined techniques achieve a 46% reduction using similar key material and can eliminate an arbitrary large number (e.g., > 99%) of key switches with only a moderate (9x) increase in key material size.
About the speaker
Olivier Bernard is a cryptology researcher at Zama, whose research interests evolve around Post-Quantum Cryptography and Fully Homomorphic Encryption with a primary appetite for Cryptanalysis and Algorithmic Number Theory.
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. We just celebrated our 5000th community member joining and would love to see you there too!
