Paper 2023/245
A Detailed Analysis of Fiat-Shamir with Aborts
Abstract
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 et al. [EUROCRYPT'18] and Grilo et al. [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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2023-02-21: approved
- 2023-02-21: received
- See all versions
- Short URL
- https://ia.cr/2023/245
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/245,
author = {Julien Devevey and Pouria Fallahpour and Alain Passelègue and Damien Stehlé},
title = {A Detailed Analysis of Fiat-Shamir with Aborts},
howpublished = {Cryptology ePrint Archive, Paper 2023/245},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/245}},
url = {https://eprint.iacr.org/2023/245}
}
