Paper 2025/163

Bootstrapping (T)FHE Ciphertexts via Automorphisms: Closing the Gap Between Binary and Gaussian Keys

Olivier Bernard, Zama, Paris, France
Marc Joye, Zama, Paris, France
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.