Paper 2026/068

From Matrix to Polynomial NTRU FHE: Enabling Amortized Bootstrapping via Sparse Keys

Ja-Ling Wu, National Taiwan University, Taipei, Taiwan

Abstract

Fully homomorphic encryption (FHE) enables computation on encrypted data and is a fundamental building block for privacy-preserving applications. Recent work has shown that FHE schemes can be constructed under the NTRU assumption, leveraging its inherently compact ciphertexts. However, existing NTRU-based FHE constructions rely on matrix representations, which obscure the underlying polynomial-ring structure and prevent the direct adoption of modern amortized bootstrapping techniques. In this work, we bridge this gap by reformulating the matrix-based NTRU construction into a standard polynomial-ring setting. We show that NTRU decryption can be decomposed into inner products compatible with FHEW-style accumulators while fully preserving the required polynomial structure. Building on this formulation, we adapt a recent amortized bootstrapping approach—based on monomial-by-polynomial multiplication—to the NTRU setting with sparse secret keys. To ensure concrete security, our parameter selection is rigorously guided by recent analyses of NTRU fatigue and the Lattice Estimator for vulnerabilities in sparse-key settings, and is complemented by a comprehensive noise analysis. The resulting scheme combines NTRU's compact-ciphertext advantage with highly efficient amortized bootstrapping, reducing both the asymptotic computational cost and the bootstrapping key size for low-Hamming-weight secrets. Rather than relying solely on a theoretical proof of concept, we present a highly optimized C++ implementation using Intel HEXL. Our evaluation shows that the proposed amortized approach yields a near 40x speedup compared to the native NTRU baseline at ring dimension $n=8192$. Furthermore, our implementation achieves a significant performance advantage over FINAL, the leading NTRU-based FHE framework, establishing its competitive potential against mainstream bitwise FHE schemes under conservative security parameters.