Paper 2026/068

Practical Amortized Bootstrapping for NTRU-Based FHE

Abstract

Fully homomorphic encryption (FHE) enables computation on encrypted data. NTRU-based FHE offers compact ciphertexts—a single ring element rather than a tuple—but FINAL, the leading NTRU-based scheme, represents its ciphertexts and decryption in matrix form that hides the polynomial-ring structure on which recent automorphism-based amortized bootstrapping relies. We reformulate FINAL in the standard polynomial-ring setting and express its decryption as coefficient-wise inner products compatible with FHEW-style accumulators. This preserves the required ring automorphisms and lets us adapt monomial-by-polynomial amortized bootstrapping to NTRU ciphertexts with sparse secret keys: for a secret of Hamming weight $h$, the dominant per-coefficient work drops from $O(n\ell_Q)$ to $O(h\ell_{\mathsf{pos}})$ external-product operations, where $\ell_Q$ and $\ell_{\mathsf{pos}}$ denote the gadget-decomposition lengths of the standard and position-based bootstrapping keys, respectively. Concrete parameters are selected by a joint optimization that combines a refined average-case noise analysis with security validation via NTRU fatigue analysis and the Lattice Estimator under sparse-secret distributions. Our highly optimized single-threaded C++ implementation based on Intel HEXL bootstraps a message coefficient in $2.68$~ms at $n = 8192$—$45\times$ faster than FINAL and $2.6\times$ faster than TFHE-rs. The bootstrapping key does not scale with $n$ ($11.28$~MB at $n=8192$). Packed ciphertexts cost about 8 bytes per message bit, and the total key material remains below that of state-of-the-art amortized RLWE bootstrapping.