CRYSTALS

Cryptographic Suite for Algebraic Lattices

CRYSTALS-Dilithium

Introduction

Dilithium is a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices. The security notion means that an adversary having access to a signing oracle cannot produce a signature of a message whose signature he hasn't yet seen, nor produce a different signature of a message that he already saw signed. Dilithium is one of the candidate algorithms submitted to the NIST post-quantum cryptography project.

For users who are interested in using Dilithium, we recommend the following:

  • Use Dilithium in a so-called hybrid mode in combination with an established "pre-quantum" signature scheme.
  • We recommend using the Dilithium-1280x1024 parameter set, which—according to a very conservative analysis—achieves around 128 bits of security against all known classical and quantum attacks.

Scientific Background

The design of Dilithium is based on the "Fiat-Shamir with Aborts" technique of Lyubashevsky which uses rejection sampling to make lattice-based Fiat-Shamir schemes compact and secure. The scheme with the smallest signature sizes using this approach is the one of Ducas, Durmus, Lepoint, and Lyubashevsky which is based on the NTRU assumption and crucially uses Gaussian sampling for creating signatures. Because Gaussian sampling is hard to implement securely and efficiently, we opted to only use the uniform distribution. Dilithium improves on the most efficient scheme that only uses the uniform distribution, due to Bai and Galbraith, by using a new technique that shrinks the public key by more than a factor of 2. To the best of our knowledge, Dilithium has the smallest public key + signature size of any lattice-based signature scheme that only uses uniform sampling.

Performance Overview

The table below gives an indication of the performance of Dilithium. All benchmarks were obtained on one core of an Intel Core-i7 4770K (Haswell) CPU. We report benchmarks of two different implementations: a C reference implementation and an optimized implementation using AVX2 vector instructions.

Dilithium-1024x768
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:
gen: 269K gen: 156K
pk: 1184 sign: 1285K sign: 493K
sig: 2044 verify: 296K verify: 150K
Dilithium-1280x1024
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:
gen: 382K gen: 225K
pk: 1472 sign: 1817K sign: 673K
sig: 2701 verify: 395K verify: 207K
Dilithium-1536x1280
Sizes (in bytes) Haswell cycles (ref) Haswell cycles (avx2)
sk:
gen: 512K gen: 292K
pk: 1760 sign: 1677K sign: 711K
sig: 3366 verify: 548K verify: 288K