Uncompressing Dilithium's public key

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 (A,t), which is at the heart of the construction of Dilithium, the least significant part of t – denoted by t₀ – is not included in the public key. The verification algorithm had been adapted accordingly, so that it should not require the knowledge of t₀. However, since it is still required to compute valid signatures, it has been made part of the secret key. The knowledge of t₀ 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 t₀ thus appears to be a sensitive question. In this work, we show that each Dilithium signature leaks information on t₀, 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 t₀ on a desktop computer.