Fixing and Mechanizing the Analysis of Dilithium

[Yi Lee]

Hi all,

Our recent paper [1] has been uploaded to eprint. We identified and fixed a flaw in the analysis of Dilithium, or more generally, of the Fiat-Shamir with Aborts (FSwA) paradigm. The flaw lies in the CMA-to-NMA reduction of prior analyses considering both classical and quantum attackers, and we provide new, fixed proofs for both cases. Furthermore, we formally verified the classical proof using EasyCrypt, and we have restored the same level of security guarantee via an improved concrete analysis, without changing the parameters of Dilithium. A concurrent work [2] also located this flaw and fixed it, by different means, in the scope of Lyubashevsky-style signatures.

Given that the above concerns the FSwA paradigm in general, many more papers are potentially affected, and we encourage authors that made use of FSwA to check their work.

Best,
Manuel Barbosa, Gilles Barthe, Christian Doczkal, Jelle Don, Serge Fehr, Benjamin Grégoire, Yu-Hsuan Huang, Andreas Hülsing, Yi Lee, Xiaodi Wu

[1] Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium. eprint: ia.cr/2023/246
[2] A Detailed Analysis of Fiat-Shamir with Aborts. eprint: ia.cr/2023/245