Cryptology ePrint Archive: Report 2019/420

Improving Speed of Dilithiumís Signing Procedure

Prasanna Ravi and Sourav Sen Gupta and Anupam Chattopadhyay and Shivam Bhasin

Abstract: Dilithium is a round 2 candidate for digital signature schemes in NIST initiative for post-quantum cryptographic schemes. Since Dilithium is built upon the ďFiat Shamir with AbortsĒ framework, its signing procedure performs rejection sampling of its signatures to ensure they do not leak information about the secret key. Thus, the signing procedure is iterative in nature with a number of rejected iterations, which serve as unnecessary overheads hampering its overall performance. As a first contribution, we propose an optimization that reduces the computations in the rejected iterations through early-evaluation of the conditional checks. This allows to perform an early detection of the rejection condition and reject a given iteration as early as possible. We also incorporate a number of standard optimizations such as unrolling and inlining to further improve the speed of the signing procedure. We incorporate and evalaute our optimizations over the software implementation of Dilithium on both the Intel Core i5- 4460 and ARM Cortex-M4 CPUs. As a second contribution, we identify opportunities to present a more refined evaluation of Dilithiumís signing procedure in several scenarios where pre-computations can be carried out. We also evaluate the performance of our optimizations and the memory requirements for the pre-computed intermediates in the considered scenarios. We could yield speed-ups of up to 35%, considering all the aforementioned scenarios, thus presenting the fastest software implementation of Dilithium till date.

Category / Keywords: public-key cryptography / Lattice based cryptography, Dilithium, digital signatures, algorithmic optimization

Date: received 23 Apr 2019, last revised 18 Jul 2019

Contact author: PRASANNA RAVI at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20190718:101508 (All versions of this report)

Short URL: ia.cr/2019/420


[ Cryptology ePrint archive ]