Paper 2025/2311 Original: eprint.iacr.org/2025/2311 ↗

Accelerating NTRU-based Bootstrapping with Block Key Distributions

Abstract

NTRU-based bootstrapping is a high-performance variant of FHEW-like bootstrapping schemes. Its main computational bottleneck lies in the blind rotation step, which involves numerous external products. In this work, we propose multiple techniques to reduce the number of these costly operations, including the use of block binary keys, block ternary keys, and the integration of block keys with the key unrolling method. Specifically, our approach reduces the number of external products to $n/\ell$ for block keys $\mathbf{B}_{k,\ell}$ ($\mathbf{T}_{k,\ell}$), compared to $n$ in FINAL (ASIACRYPT 2021) and $n/2$ in the key unrolling approach (CHES 2024). When combining block keys with key unrolling, the number can further be reduced to $n/2\ell$ . We implemented our algorithms using the CHIFHE library. Under 128-bit security settings, using block binary keys $\mathbf{B}_{k,\ell}$ ($\ell=4$), block ternary keys $\mathbf{T}_{k,\ell}$ ($\ell=4$) and key unrolling on $\mathbf{B}_{n/2,2}$ achieve a speedup of $1.12\times$ over the key unrolling method (CHES 2024) and $1.73\times$ over FINAL (ASIACRYPT 2021). Notably, the last $2$ algorithms increase memory usage by less than 15MB compared to the key unrolling method (CHES 2024).