Sparse-Aware NTT: Accelerating Lattice-Based Cryptography on FPGAs
Authors:
- 6 July 2025
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 1-6
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Unif-NTT: A Unified Hardware Design of Forward and Inverse NTT for PQC AlgorithmsIEEE Access, 2024
- Low latency FPGA implementation of NTT for KyberMicroprocessors and Microsystems, 2024
- High-Speed NTT Accelerator for CRYSTAL-Kyber and CRYSTAL-DilithiumIEEE Access, 2024
- An FPGA-Based Efficient NTT Accelerator for Post-Quantum Cryptography CRYSTALS-Kyber2023
- FastNTT: Design and Evaluation of Modular-Reduction Based Fast NTT Design on FPGA2023
- Efficient Modular Polynomial Multiplier for NTT Accelerator of Crystals-Kyber2022
- Pipelined High-Throughput NTT Architecture for Lattice-Based Cryptography2021
- Towards Efficient Hardware Implementation of NTT for Kyber on FPGAs2021
- Design and Implementation of a Fast and Scalable NTT-Based Polynomial Multiplier Architecture2019
- Sparse polynomial multiplication for lattice-based cryptography with small complexityThe Journal of Supercomputing, 2015