Configurable radix-4 NTT hardware optimization and implementation for lattice-based cryptography

Abstract

In response to the complex polynomial multiplication issue in lattice-based cryptography algorithms optimized with number theoretic transform (NTT), as well as the demand for NTT designs catering to multiple application scenarios, a configurable radix-4 NTT hardware architecture for lattice-based cryptography was proposed. By analyzing the radix-4 NTT/INTT (inverse NTT) algorithm process, an efficient FPGA architecture was designed, which parameterized runtime configurability and offered compile-time configurability to meet diverse requirements, a pipeline approach was used to construct the radix-4 NTT unified butterfly unit, key algorithmic modules such as modular division and modular reduction were deeply optimized, thereby enhancing computational efficiency and reconfigurability. Additionally, a configurable multi-RAM storage optimization design scheme and data storage allocation algorithm were proposed to avoid memory conflicts and improve data access efficiency. Comparison and analysis with related approaches show that, using the Dilithium algorithm as an example, the proposed design not only achieves a high operational frequency but also achieves up to 54.3% improvement in area and 2 times optimization in throughput, fully leveraging the computational advantages of FPGA.

Keywords

• NTT
• lattice-based cryptography
• polynomial multiplication
• FPGA
• butterfly unit