Paper 2024/1373

Uncompressing Dilithium's public key

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 $\mathbf{(}\mathbf{A}\mathbf{,}\mathbf{t}\mathbf{)}$, 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.