Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)


We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.
Originele taal-2Engels
TitelAdvances in Cryptology – CRYPTO 2023
Subtitel43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20–24, 2023, Proceedings
RedacteurenHelena Handschuh, Anna Lysyanskaya
Plaats van productieCham
Aantal pagina's32
ISBN van elektronische versie978-3-031-38554-4
ISBN van geprinte versie978-3-031-38553-7
StatusGepubliceerd - 2023
Evenement43rd Annual International Cryptology Conference, CRYPTO 2023 - Santa Barbara, Verenigde Staten van Amerika
Duur: 20 aug. 202324 aug. 2023
Congresnummer: 43

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres43rd Annual International Cryptology Conference, CRYPTO 2023
Verkorte titelCRYPTO 2023
Land/RegioVerenigde Staten van Amerika
StadSanta Barbara


Acknowledgments. Jelle Don is supported by the ERC-ADG project ALGSTR ONGCRYPTO (Project No. 740972). Benjamin Grégoire is supported by the Agence Nationale de la Recherche (French National Research Agency) as part of the France 2030 programme - ANR-22-PECY-0006. Yu-Hsuan Huang is supported by the Dutch Research Agenda (NWA) project HAPKIDO (Project No. NWA.1215.18.002), which is financed by the Dutch Research Council (NWO). Andreas Hülsing is supported by an NWO VIDI grant (Project No. VI.Vidi.193. 066). Xiaodi Wu is supported by AFOSR Young Investigator Program (YIP) Award (FA95502110094) and NSF CAREER Award (NSF-CCF-1942837).

Dutch Research Agenda
Air Force Office of Scientific Research (AFOSR)NSF-CCF-1942837, FA95502110094
National Weather Association
Agence Nationale de la Recherche (ANR)ANR-22-PECY-0006
Nederlandse Organisatie voor Wetenschappelijk Onderzoek


    Duik in de onderzoeksthema's van 'Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit