Welcome to the resource topic for 2025/1753
Title:
Bootstrapping over Free \mathcal{R}-Module
Authors: Ruida Wang, Jikang Bai, Yijian Liu, Xinxuan Zhang, Xianhui Lu, Lutan Zhao, Kunpeng Wang, Rui Hou
Abstract:Bootstrapping, introduced by Gentry at STOC 2009, remains the only known method for realizing fully homomorphic encryption (FHE). Since Alperin-Sheriff and Peikert’s 2014 breakthrough on symmetric group accumulator (ACC) based bootstrapping, algebraic ACC designs have offered the lowest bootstrapping latency. The work of Ducas and Micciancio further advanced this paradigm by embedding \mathbb{Z}_q into the multiplicative subgroup of the cyclotomic ring \mathcal{R}_N and exploiting FFT/NTT for fast computation, leading to the milestone constructions FHEW and TFHE. Despite their efficiency, these ring-based schemes face a fundamental limitation: correctness requires q < 2N, rigidly coupling precision, performance, and key size to the polynomial dimension.
We address this limitation by introducing a new accumulator structure - a free \mathcal{R}_N-module \bigoplus_{i=0}^{\tau-1} \mathcal{R}_N X^i. This generalization decouples q and N through a tunable factor \tau, with the classical ring-based construction recovered as the special case \tau=1. The computation over resulting \mathcal{R}_N-algebra enables efficient computation over \bigoplus_{i=0}^{\tau-1} \mathcal{R}_N X^i can be effectively reduced to the base ring \mathcal{R}_N. Based on this structure, we design a bootstrapping scheme that achieves asymptotic improvements in precision, performance, and key size. Experimental results further demonstrate significant concrete gains, confirming the practicality of our approach.
ePrint: https://eprint.iacr.org/2025/1753
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .