Paper 2023/245

A Detailed Analysis of Fiat-Shamir with Aborts

Julien Devevey, École Normale Supérieure de Lyon
Pouria Fallahpour, École Normale Supérieure de Lyon
Alain Passelègue, Inria, École Normale Supérieure de Lyon
Damien Stehlé, École Normale Supérieure de Lyon, Institut Universitaire de France
Keita Xagawa, Technology Innovation Institute

Lyubashevky's signatures are based on the Fiat-Shamir with Aborts paradigm. It transforms an interactive identification protocol that has a non-negligible probability of aborting into a signature by repeating executions until a loop iteration does not trigger an abort. Interaction is removed by replacing the challenge of the verifier by the evaluation of a hash function, modeled as a random oracle in the analysis. The access to the random oracle is classical (ROM), resp. quantum (QROM), if one is interested in security against classical, resp. quantum, adversaries. Most analyses in the literature consider a setting with a bounded number of aborts (i.e., signing fails if no signature is output within a prescribed number of loop iterations), while practical instantiations (e.g., Dilithium) run until a signature is output (i.e., loop iterations are unbounded). In this work, we emphasize that combining random oracles with loop iterations induces numerous technicalities for analyzing correctness, run-time, and security of the resulting schemes, both in the bounded and unbounded case. As a first contribution, we put light on errors in all existing analyses. We then provide two detailed analyses in the QROM for the bounded case, adapted from Kiltz, Lyubashevsky, and Shaffner [EUROCRYPT'18] and from Grilo, Hövelmanns, Hülsing, and Majenz [ASIACRYPT'21]. In the process, we prove the underlying $\Sigma$-protocol to achieve a stronger zero-knowledge property than usually considered for $\Sigma$-protocols with aborts, which enables a corrected analysis. A further contribution is a detailed analysis in the case of unbounded aborts, the latter inducing several additional subtleties.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
Fiat-Shamir with abortsLyubashevsky's signatureQROM
Contact author(s)
julien devevey @ ens-lyon fr
pouria fallahpour @ ens-lyon fr
alain passelegue @ inria fr
damien stehle @ ens-lyon fr
keita xagawa @ tii ae
2024-05-14: revised
2023-02-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julien Devevey and Pouria Fallahpour and Alain Passelègue and Damien Stehlé and Keita Xagawa},
      title = {A Detailed Analysis of Fiat-Shamir with Aborts},
      howpublished = {Cryptology ePrint Archive, Paper 2023/245},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.