Sparse-Aware NTT: Accelerating Lattice-Based Cryptography on FPGAs
Dixit Dutt Bohra, Dip Sankar Banerjee, Somitra Kumar Sanadhya · 2025
Lattice-based cryptographic schemes rely on structured polynomial arithmetic, where efficient multiplication is critical for performance. The Number Theoretic Transform (NTT) accelerates polynomial multiplication but performs redundant computations for sparse polynomials, leading to increased hardware overhead. This work introduces Sparse-Aware NTT (SparseNTT), a hybrid multiplication scheme that dynamically detects and processes only nonzero coefficients, reducing transformation costs. By leveraging precomputed NTT representations and applying early-stage modular pre-reduction, SparseNTT minimizes unnecessary operations while preserving correctness. The proposed approach seamlessly integrates into Kyber’s CCA-secure key generation, encryption, and decryption and extends to other lattice-based schemes utilizing sparse polynomials. FPGA implementation on Artix-7 demonstrates a 54% reduction in LUT usage, a 47% decrease in FFs, and an 80% reduction in DSP utilization, while achieving a 58.3% improvement in execution time. These optimizations enhance cryptographic accelerators, enabling scalable, high-performance post-quantum security for embedded systems with minimal overhead.