Paper 2025/1753

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

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Jikang Bai, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Yijian Liu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Xinxuan Zhang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Xianhui Lu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Lutan Zhao, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Kunpeng Wang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

Rui Hou, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS; School of Cybersecurity, UCAS

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].

@misc{cryptoeprint:2025/1753,
      author = {Ruida Wang and Jikang Bai and Yijian Liu and Xinxuan Zhang and Xianhui Lu and Lutan Zhao and Kunpeng Wang and Rui Hou},
      title = {Bootstrapping over Free $\mathcal{R}$-Module},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1753},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1753}
}