Paper 2025/1753

Bootstrapping over Free $\mathcal{R}$-Module

Abstract

FHEW/TFHE bootstrapping suffers from a structural rigidity: the accumulator's ring dimension $N$ is limited by the input ciphertext modulus $q$ (typically $q \le 2N$), and thus the message space $t$. This coupling forces $N$ to grow with $t$, leading to inflated parameters and thereby high computational costs. In this work, we overcome this limitation by replacing the ring structure with a free $\mathcal{R}_N$-module $\bigoplus_{i=0}^{\tau-1}\mathcal{R}_N \cdot X^i$. This generalization decouples $N$ from $q$ through a flexible parameter $\tau$. We prove that computation in this extended algebra efficiently reduces to base-ring operations, enabling a new bootstrapping algorithm with improvements in both performance and precision. Theoretically, our approach reduces the asymptotic complexity of standard FHEW/TFHE bootstrapping from quadratic $\tilde{O}(t^2)$ to quasi-linear $\tilde{O}(t)$ in the message space $t$. Compared with prior Extended Bootstrapping methods over discrete cyclotomic ring [PKC'23, TCC'25, Asiacrypt'25], our framework constitutes an algebraic generalization that enables more flexible parameter selection. Experimental results demonstrate that our method achieves speedups of 1.40$\times$--2.77$\times$ over the state-of-the-art sorted extended bootstrapping [Asiacrypt'25].

Note: Add comparisons with Extended Bootstrapping [PKC23] and Sorted Bootstrapping [ASIACRYPT25].