Uncompressing Dilithium's public key

Paco Azevedo Oliveira; Andersson Calle Viera; Benoît Cogliati; Louis Goubin

Paper 2024/1373

Uncompressing Dilithium's public key

Paco Azevedo Oliveira, Thales DIS, France, Laboratoire de Mathématiques de Versailles, UVSQ, CNRS, Université Paris-Saclay, 78035 Versailles, France

Andersson Calle Viera, Thales DIS, France, Sorbonne Université, CNRS, Inria, LIP6, F-75005 Paris, France

Benoît Cogliati, Thales DIS, France

Louis Goubin, Laboratoire de Mathématiques de Versailles, UVSQ, CNRS, Université Paris-Saclay, 78035 Versailles, France

Abstract

The Dilithium signature scheme – recently standardized by NIST under the name ML-DSA – owes part of its success to a specific mechanism that allows an optimizaion of its public key size. Namely, among the data of the MLWE instance , which is at the heart of the construction of Dilithium, the least significant part of -- denoted by -- is not included in the public key. The verification algorithm had been adapted accordingly, so that it should not require the knowledge of . However, since it is still required to compute valid signatures, it has been made part of the secret key. The knowledge of has no impact on the black-box cryptographic security of Dilithium, as can be seen in the security proof. Nevertheless, it does allow the construction of much more efficient side-channel attacks. Whether it is possible to recover thus appears to be a sensitive question. In this work, we show that each Dilithium signature leaks information on , then we construct an attack that retrieves it from Dilithium signatures. Experimentally, depending on the Dilithium security level, between and signatures are sufficient to recover on a desktop computer.

Note: Minor revision: New practical results have been included.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Dilithium Public Key Partial Key Recovery
Contact author(s): paco azevedo-oliveira @ thalesgroup com
andersson calle-viera @ thalesgroup com
benoit-michel cogliati @ thalesgroup com
louis goubin @ uvsq fr
History: 2025-02-14: revised; 2024-09-02: received; See all versions
Short URL: https://ia.cr/2024/1373
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1373,
      author = {Paco Azevedo Oliveira and Andersson Calle Viera and Benoît Cogliati and Louis Goubin},
      title = {Uncompressing Dilithium's public key},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1373},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1373}
}