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 optimization of its public key size. Namely, among the data of the MLWE instance \((\textbf{A},{\textbf {t}})\) , which is at the heart of the construction of Dilithium, the least significant part of \({\textbf {t}}\) – denoted by \({\textbf {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 \({\textbf {t}}_0\) . However, since it is still required to compute valid signatures, it has been made part of the secret key. The knowledge of \({\textbf {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 \({\textbf {t}}_0\) thus appears to be a sensitive question. In this work, we show that each Dilithium signature leaks information on \({\textbf {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 \({\textbf {t}}_0\) on a desktop computer.