076 Bootstrapping (T)FHE Ciphertexts via Automorphisms: Closing 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., great than 99%) of key switches with only a moderate (9x) increase in key material size.

About the speakers

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.

Never miss an update

The newsletter where we post community announcements: https://fheorg.substack.com/
The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org

Make sure to join either (or both) of these to stay informed about future events!

View all resources related to this meetup on https://fhe.org/meetups/076