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 $\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.

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