  CRYSTALS-Dilithium is a lattice-based signature scheme to be standardized by
NIST as the primary post-quantum signature algorithm. In this work, we make a
thorough study of optimizing the implementations of Dilithium by utilizing the
Advanced Vector Extension (AVX) instructions, specifically AVX2 and the latest
AVX-512. We first present an improved parallel small polynomial multiplication
with tailored early evaluation (PSPM-TEE) to further speed up the signing
procedure. Our PSPM algorithm outperform the NTT by 47%-66% in AVX2 and AVX-512
implementation. We then present a tailored reduction method that is simpler and
faster than Montgomery reduction. We minimize the CPU cycles of tailored
reduction AVX-512 implementation by using AVX-512IFMA. Finally, we propose a
fully and highly vectorized implementation of Dilithium using AVX-512. This is
achieved by carefully vectorizing most of Dilithium functions with the AVX-512
instructions in order to improve efficiency both for time and for space
simultaneously. With all the optimization efforts, our AVX-512 implementation
improves the performance by 43.2%/39.3%/45.6% in key generation,
36.6%/41.6%/43.7% in signing, and 45.3%/46.5%/47.4% in verification for the
parameter sets of Dilithium2/3/5 respectively. To the best of our knowledge,
our AVX-512 implementation has the best performance for Dilithium on the Intel
x86-64 CPU platform to date.
