Sparse Polynomial Multiplication-based High-Performance Hardware Implementation for CRYSTALS-Dilithium

CRYSTALS-Dilithium has been declared as the first recommended digital signature algorithm in NIST Post-Quantum Cryptography Standardization. The advancement of high-speed hardware research for Dilithium is propelled by the need for real-time processing of extensive data in numerous digital signature applications. To address the slow signature generation speed issue, a two-stage pipeline structure was developed to accelerate the underlying rejection loop, at a cost of substantial resource consumption. In this paper, we present the first analysis on the possibility of leveraging sparse multiplication in the second stage, which can reduce the bit complexity of corresponding multiplications by over 85% and lower the storage requirements for the secret key by over 68%. Building on this, we propose a sparse computing core and a high-speed hybrid architecture for Dilithium, with an efficient scheduling mechanism and optimized modules. Compared to state-of-the-art high-speed implementations on similar platforms, the signature generation speed is at least 2x faster. Meanwhile, the area-time-products of signature generation achieve 3.6x/4.3x/2.0x/2.1x improvement in terms of LUT/FF/DSP/BRAM, respectively.