CRYSTALS-Dilithium#

Dilithium is “a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices” [Sch].

The latest version of the specification at the time of writing can be found here.

A high-level overview of the scheme is available in this presentation. NIST submission packages and the different versions of the paper are available in the Resources page.

Dilithium is based on the “Fiat-Shamir with Aborts” approach described in [Lyu09], [Lyu12], and resembles the schemes [GLP12] and [BG14].

Unlike the schemes presented in [DDLL13] and [DLP14] that sample randomness from a discrete Gaussian distribution, Dilithium uses uniform sampling. This was proposed in [Lyu09] and [GLP12], and has the advantage of avoiding the problem of safely implementing Gaussian sampling, which is hard to protect against side-channel attacks such as [GBHLY16], [EFGT17], and [PBY17].

While Dilithium is a random scheme, it offers a deterministic variant which the authors recommend by the default as long as side-channel attacks that exploit determinism cannot be mounted. For examples, see [SBB+18] and [PSS+18].

The operations used for signing and verification are mostly expansion of an XOF, in this case SHAKE128 and SHAKE256. The other set of heavily used operations are multiplications in \(R_q\), which is why the scheme uses the same ring for all parameter sets. As with Kyber, polynomial mulitiplication is implemented with the Number Theoretic Transform.

The authors offer two recommendations:

  • Use Dilithium in a so-called hybrid mode in combination with an established “pre-quantum” signature scheme.

  • We recommend using the Dilithium3 parameter set, which—according to a very conservative analysis—achieves more than 128 bits of security against all known classical and quantum attacks.

This scheme uses the ring \(R_q = \mathbb{Z}_q[X] / (X^n + 1)\), with \(q = 2^{23} - 2^{13} + 1\) and \(n = 256\).

Parameters#

Dilithium parameter sets#

Parameter

NIST sec 2

NIST sec 3

NIST sec 5

Description

\(q\)

8380417

8380417

8380417

Modulus

\(d\)

13

13

13

Dropped bits from \(\boldsymbol{t}\)

\(\tau\)

39

49

60

Number of \(\pm 1\) in \(c\)

Challenge entropy

192

225

257

\(\log \binom{256}{\tau} + \tau\)

\(\gamma_1\)

\(2^{17}\)

\(2^{19}\)

\(2^{19}\)

\(\boldsymbol{y}\) coefficient range

\(\gamma_2\)

\((q-1) / 88\)

\((q-1)/32\)

\((q-1)/32\)

low-order rounding range

\((k,l)\)

\((4,4)\)

\((6,5)\)

\((8,7)\)

Dimensions of \(\boldsymbol{A}\)

\(\eta\)

2

4

2

Secret key range

\(\beta\)

78

196

120

\(\tau \cdot \eta\)

\(\omega\)

80

55

75

Maximum number of ones in the hint \(\boldsymbol{h}\)

Repetitions

4.25

5.1

3.85
Dilithium sizes in bytes#

Parameters set

Public key

Private key

Signature

NIST security level

Dilithium2

1312

2528

2420

2

Dilithium3

1952

4000

3293

3

Dilithium5

2592

4864

4595

5

Implementations#

  • The reference and the AVX2 optimized implementations can be found in the pq-crystals/dilithium repository.

  • It is integrated into Open Quantum Safe’s liboqs.

  • It is integrated into PQclean, including an aarch64 implementation.

Other third-party implementations are referenced in Dilithium’s Software page, such as:

Benchmarks#

Benchmarks performed on an Intel i7-8565u using the provided programs.

There are also benchmarks provided by the authors in Dilithium’s homepage as well as benchmarks from the SUPERCOP benchmarking framework.

Dilithium cycles#

Parameter set

Key generation

Sign

Verify

Dilithium2

182956

753125

199536

Dilithium3

316955

1324089

304934

Dilithium5

498482

1579503

526596

Dilithium2 AVX2

55235

141680

54872

Dilithium3 AVX2

85148

223664

88795

Dilithium5 AVX2

136783

268426

132707
Dilithium AES cycles#

Parameter set

Key generation

Sign

Verify

Dilithium2aes

371173

1074952

359543

Dilithium3aes

675773

1862761

624963

Dilithium5aes

1247287

2510715

1111386

Dilithium2aes AVX2

34764

122613

38536

Dilithium3aes AVX2

57075

162428

58841

Dilithium5aes AVX2

70887

180428

76336

Attacks#

The paper has a section called “Concrete security”, which goes over the problems that the scheme is based on and their known attacks.

Side-channel attacks against Dilithium have been published:

  • Differential Fault Attacks on Deterministic Lattice Signatures [GBP18].

  • Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach [BVC+23].

  • An Efficient Non-Profiled Side-Channel Attack on the CRYSTALS-Dilithium Post-Quantum Signature [CKA+21].

  • Practical Public Template Attacks on CRYSTALS-Dilithium With Randomness Leakages [QLZ+23].

Other attacks:

  • Signature Correction Attack on Dilithium Signature Scheme, [IMS+22].

Bibliography#

[BG14]

Shi Bai and Steven D. Galbraith. An Improved Compression Technique for Signatures Based on Learning with Errors. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, and Josh Benaloh, editors, Topics in Cryptology – CT-RSA 2014, volume 8366, pages 28–47. Springer International Publishing, Cham, 2014. URL: http://link.springer.com/10.1007/978-3-319-04852-9_2 (visited on 2023-07-18), doi:10.1007/978-3-319-04852-9_2.

[BVC+23]

Alexandre Berzati, Andersson Calle Viera, Maya Chartouny, Steven Madec, Damien Vergnaud, and David Vigilant. Exploiting intermediate value leakage in dilithium: a template-based approach. Cryptology ePrint Archive, Paper 2023/050, 2023. https://eprint.iacr.org/2023/050. URL: https://eprint.iacr.org/2023/050.

[CKA+21]

Zhaohui Chen, Emre Karabulut, Aydin Aysu, Yuan Ma, and Jiwu Jing. An Efficient Non-Profiled Side-Channel Attack on the CRYSTALS-Dilithium Post-Quantum Signature. In 2021 IEEE 39th International Conference on Computer Design (ICCD), 583–590. Storrs, CT, USA, October 2021. IEEE. URL: https://ieeexplore.ieee.org/document/9643637/ (visited on 2023-07-19), doi:10.1109/ICCD53106.2021.00094.

[DDLL13]

Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice Signatures and Bimodal Gaussians. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, volume 8042, pages 40–56. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: http://link.springer.com/10.1007/978-3-642-40041-4_3 (visited on 2023-07-18), doi:10.1007/978-3-642-40041-4_3.

[EFGT17]

Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 1857–1874. Dallas Texas USA, October 2017. ACM. URL: https://dl.acm.org/doi/10.1145/3133956.3134028 (visited on 2023-07-18), doi:10.1145/3133956.3134028.

[GBHLY16]

Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. Flush, Gauss, and Reload – A Cache Attack on the BLISS Lattice-Based Signature Scheme. In Benedikt Gierlichs and Axel Y. Poschmann, editors, Cryptographic Hardware and Embedded Systems – CHES 2016, volume 9813, pages 323–345. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. URL: http://link.springer.com/10.1007/978-3-662-53140-2_16 (visited on 2023-07-18), doi:10.1007/978-3-662-53140-2_16.

[GBP18]

Leon Groot Bruinderink and Peter Pessl. Differential Fault Attacks on Deterministic Lattice Signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 21–43, August 2018. URL: https://tches.iacr.org/index.php/TCHES/article/view/7267 (visited on 2023-07-19), doi:10.46586/tches.v2018.i3.21-43.

[GLP12] (1,2)

Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Emmanuel Prouff, and Patrick Schaumont, editors, Cryptographic Hardware and Embedded Systems – CHES 2012, volume 7428, pages 530–547. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://link.springer.com/10.1007/978-3-642-33027-8_31 (visited on 2023-07-18), doi:10.1007/978-3-642-33027-8_31.

[IMS+22]

Saad Islam, Koksal Mus, Richa Singh, Patrick Schaumont, and Berk Sunar. Signature correction attack on dilithium signature scheme. 2022. arXiv:2203.00637.

[Lyu09] (1,2)

Vadim Lyubashevsky. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, and Mitsuru Matsui, editors, Advances in Cryptology – ASIACRYPT 2009, volume 5912, pages 598–616. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. URL: http://link.springer.com/10.1007/978-3-642-10366-7_35 (visited on 2023-07-18), doi:10.1007/978-3-642-10366-7_35.

[Lyu12]

Vadim Lyubashevsky. Lattice Signatures without Trapdoors. In David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, David Pointcheval, and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237, pages 738–755. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL: http://link.springer.com/10.1007/978-3-642-29011-4_43 (visited on 2023-07-18), doi:10.1007/978-3-642-29011-4_43.

[PBY17]

Peter Pessl, Leon Groot Bruinderink, and Yuval Yarom. To BLISS-B or not to be: Attacking strongSwan's Implementation of Post-Quantum Signatures. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 1843–1855. Dallas Texas USA, October 2017. ACM. URL: https://dl.acm.org/doi/10.1145/3133956.3134023 (visited on 2023-07-18), doi:10.1145/3133956.3134023.

[PSS+18]

Damian Poddebniak, Juraj Somorovsky, Sebastian Schinzel, Manfred Lochter, and Paul Rosler. Attacking Deterministic Signature Schemes Using Fault Attacks. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), 338–352. London, April 2018. IEEE. URL: https://ieeexplore.ieee.org/document/8406609/ (visited on 2023-07-18), doi:10.1109/EuroSP.2018.00031.

[QLZ+23]

Zehua Qiao, Yuejun Liu, Yongbin Zhou, Jingdian Ming, Chengbin Jin, and Huizhong Li. Practical public template attacks on crystals-dilithium with randomness leakages. IEEE Transactions on Information Forensics and Security, 18():1–14, 2023. doi:10.1109/TIFS.2022.3215913.

[SBB+18]

Niels Samwel, Lejla Batina, Guido Bertoni, Joan Daemen, and Ruggero Susella. Breaking Ed25519 in WolfSSL. In Nigel P. Smart, editor, Topics in Cryptology – CT-RSA 2018, volume 10808, pages 1–20. Springer International Publishing, Cham, 2018. URL: http://link.springer.com/10.1007/978-3-319-76953-0_1 (visited on 2023-07-18), doi:10.1007/978-3-319-76953-0_1.

[Sch]

Peter Schwabe. Dilithium. URL: https://pq-crystals.org/dilithium/index.shtml (visited on 2023-07-18).