Optimized Vectorization Implementation of CRYSTALS-Dilithium

CRYSTALS-Dilithium is a lattice-based signature scheme that is being standardized by NIST as the primary post-quantum signature algorithm. In this work, we present a comprehensive study of optimizing the implementation of Dilithium using Advanced Vector Extensions (AVX), specifically AVX2 and the latest AVX-512. We begin by introducing an enhanced parallel small polynomial multiplication with tailored early evaluation (PSPM-TEE) to accelerate the signing process. We provide both AVX2 and AVX-512 implementations of PSPM-TEE, demonstrating that our PSPM algorithm outperforms the traditional NTT by 47%-66% on these platforms. Next, we propose a tailored reduction method that is simpler and faster than Montgomery reduction. By leveraging AVX-512IFMA, we further minimize the CPU cycles required for the tailored reduction. Finally, we present a fully vectorized implementation of Dilithium using AVX-512, carefully optimizing most of the Dilithium functions to improve both time and space efficiency simultaneously. As a result of these optimizations, our AVX-512 implementation achieves performance improvements of 2.25×/2.07×/2.20× in key generation, 2.07×/2.13×/2.36× in signing, and 2.20×/2.36×/2.46× in verification for the Dilithium2/3/5 parameter sets, respectively compared to the state-of-the-art AVX2 implementation.