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 6600U (Skylake) 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) Skylake cycles (ref) Skylake cycles (avx2)
gen: 242532 gen: 107823
pk: 1184 sign: 1058483 sign: 313347
sig: 2044 verify: 272800 verify: 108988
Dilithium-1280x1024
Sizes (in bytes) Skylake cycles (ref) Skylake cycles (avx2)
sk:
gen: 371083 gen: 156777
pk: 1472 sign: 1562215 sign: 437638
sig: 2701 verify: 375708 verify: 155784
Dilithium-1536x1280
Sizes (in bytes) Skylake cycles (ref) Skylake cycles (avx2)
sk:
gen: 470842 gen: 221348
pk: 1760 sign: 1420285 sign: 463084
sig: 3366 verify: 510895 verify: 220400

As an update for round 2 of the NIST project we propose a variant of Dilithium, called Dilithium-AES, that uses AES-256 in counter mode instead of SHAKE to expand the matrix and the masking vectors, and to sample the secret polynomials.

Dilithium-1024x768-AES
Skylake cycles (avx2)
gen: 69893
sign: 238113
verify: 81459
Dilithium-1280x1024-AES
Skylake cycles (avx2)
gen: 99907
sign: 350465
verify: 109782
Dilithium-1536x1280-AES
Skylake cycles (avx2)
gen: 130802
sign: 359186
verify: 143106