Don't throw your nonces out with the bathwater: Speeding up Dilithium by reusing the tail of y

Amber Sprenkels; Bas Westerbaan

Paper 2020/1158

Don't throw your nonces out with the bathwater: Speeding up Dilithium by reusing the tail of y

Amber Sprenkels

, Radboud University Nijmegen

Bas Westerbaan

Abstract

We suggest a small change to the Dilithium signature scheme, that allows one to reuse computations between rejected nonces, for a speed-up in signing time. The modification is based on the idea that, after rejecting on a too large $\|\mathbf{r}_0\|_\infty$, not all elements of the nonce $\mathbf{y}$ are spent. We swap the order of the checks; and if this $\mathbf{r}_0$-check fails, we only need to resample $y_1$. We provide a proof that shows that the modification does not affect the security of the scheme. We present measurements of the performance of the modified scheme on AVX2, Cortex M4, and Cortex M3, which show a speed-up ranging from 11% for Dilithium2 on M3 to 22% for Dilithium3 on AVX2.

Note: New versions are based are based on our previous paper from 22 Sep 2020, which was published under the same name.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Dilithium Fiat-Shamir with aborts lattice-based cryptography AVX2 ARM Cortex-M4 ARM Cortex-M3
Contact author(s): amber @ electricdusk com
bas @ westerbaan name
History: 2023-05-24: last of 2 revisions; 2020-09-25: received; See all versions
Short URL: https://ia.cr/2020/1158
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1158,
      author = {Amber Sprenkels and Bas Westerbaan},
      title = {Don't throw your nonces out with the bathwater: Speeding up Dilithium by reusing the tail of y},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1158},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1158}
}