Paper 2025/163
Bootstrapping (T)FHE Ciphertexts via Automorphisms: Closing the Gap Between Binary and Gaussian Keys
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Fully homomorphic encryption (FHE)Ciphertext bootstrappingBlind rotationAutomorphisms
- Contact author(s)
-
olivier bernard @ zama ai
marc @ zama ai - History
- 2025-02-14: revised
- 2025-02-04: received
- See all versions
- Short URL
- https://ia.cr/2025/163
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/163, author = {Olivier Bernard and Marc Joye}, title = {Bootstrapping (T){FHE} Ciphertexts via Automorphisms: Closing the Gap Between Binary and Gaussian Keys}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/163}, year = {2025}, url = {https://eprint.iacr.org/2025/163} }