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, albeit at the cost of significantly large bootstrapping keys. Building on AP, automorphism-based methods, introduced in LMK⁺ (EUROCRYPT 2023), achieve smaller key sizes. However, each automorphism application necessitates a key switch, introducing additional computational overhead and noise accumulation. 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, we introduce a comprehensive theoretical framework for analyzing the expected number of automorphism key switches. The predictions of this framework perfectly align with the results of extensive numerical experiments, demonstrating its practical relevance. In typical settings, by leveraging additional key material, the LLW⁺ approach (TCHES 2024) reduces the number of 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., more than 99%) of key switches with only a moderate (9x) increase in key material size. As a result, the total bootstrapping runtime decreases by more than 34%.

Note: 25/09/10: Numerical comparisons with [ZWC25] (App.C); explicit discussion about the bootstrapping total runtime.