Open-Source FPGA Implementation of Number-Theoretic Transform for CRYSTALS-Dilithium

Voci, Brandon

Student Work

Open-Source FPGA Implementation of Number-Theoretic Transform for CRYSTALS-Dilithium

Public Deposited

In Ring-Learning with Error (R-LWE) and R-LWE related cryptosystems, the Number Theoretic Transform (NTT) is the most important mathematical operation. The NTT effectively reduces the time complexity of polynomial multiplication from quadratic time to logarithmic by exploiting a certain algebraic isomorphism. One of such R-LWE related cryptosystems is the CRYSTALS-Dilithium (Dilithium) digital signature scheme, a Round 3 finalist in the National Institute for Standards in Technology's Post-Quantum Cryptography (PQC) standardization project. This paper discusses the mathematical theory underpinning the NTT and implementation details concerning the Dilithium NTT specifically. Ultimately, we develop an open-source FPGA implementation of the Dilithium NTT at the Register-Transfer Level (RTL). Targeting speed and high-throughput, our RTL design exploits the full parallelism of the Radix-2 Decimation-in-Time (DIT) Cooley-Tukey NTT algorithm. We hence performed behavioral simulation on our RTL design via unit and regression tests, estimating a 40-48 clock cycle delay to compute the full forward transform. However, given the increased utilization of FPGA resources, our design is better suited for dedicated parallel hardware.

This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.

Creator