An Optimized GPU-based Acceleration of CRYSTALS-Dilithium

CRYSTALS-Dilithium has recently been selected as one of the next generation post-quantum signature algorithm standards. However, due to the extensive volume of data elements and the high complexity of operations, post-quantum cryptographic algorithms commonly face significant performance challenges, for which GPU acceleration has proven to be an effective hardware solution. This paper presents an optimized GPU-based implementation of Dilithium, accelerating the algorithm across three dimensions: inter-thread, intra-thread, and inter-block. Specifically, we propose shared memory and loop unrolling techniques to optimize the most time consuming number theoretic transform operation. Meanwhile, we employ a PTX assembly implementation of Montgomery modular multiplication for frequent dot product computations. Experimental results indicate that, compared to the NIST standard implementation, our implementations of Dilithium across all three parameter sets achieve speedups of up to 143x for Gen, 255x for Sign, and 152x for Verify on the GPU 4090. On the GPU A100, the speedups reach 114x for Gen, 158x for Sign, and 124x for Verify.