International Association
for Cryptologic Research

In Dilithium, the rejection sampling step is crucial for the proof of security and correctness of the scheme. However, to our knowledge, there is no attack in the literature that takes advantage of an attacker knowing rejected signatures. The aim of this paper is to create a practical black-box attack against Dilithium with a weakened rejection sampling. We succeed in showing that an adversary with enough rejected signatures can recover Dilithium's secret key in less than half an hour on a desktop computer. There is one possible application for this result: by physically preventing one of the rejection sampling tests from happening, we obtain two fault attacks against Dilithium.

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 $\bf (A,\bf{t})$, which is at the heart of the construction of Dilithium, the least significant part of $\bf{t}$ -- denoted by $\bf{t}_0$ -- is not included in the public key. The verification algorithm had been adapted accordingly, so that it should not require the knowledge of $\bf{t}_0$. However, since it is still required to compute valid signatures, it has been made part of the secret key. The knowledge of $\bf{t}_0$ 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 $\bf{t}_0$ thus appears to be a sensitive question. In this work, we show that each Dilithium signature leaks information on $\bf{t}_0$, then we construct an attack that retrieves it from Dilithium signatures. Experimentally, depending on the Dilithium security level, between $200\,000$ and $500\,000$ signatures are sufficient to recover $\bf{t}_0$ on a desktop computer.