Paper 2025/985
Tighter Quantum Security for Fiat-Shamir-with-Aborts and Hash-and-Sign-with-Retry Signatures
Abstract
We revisit the quantum security (in the QROM) of digital signature schemes that follow the Fiat-Shamir-with-aborts (FSwA) or the probabilistic hash-and-sign with retry/abort (HSwA) design paradigm. Important examples of such signature schemes are Dilithium, SeaSign, Falcon+ and UOV. In particular, we are interested in the UF-CMA-to-UF-NMA reduction for such schemes. We observe that previous such reductions have a reduction loss that is larger than what one would hope for, or require a more stringent notion of zero-knowledge than one would hope for. We resolve this matter here by means of a novel UF-CMA-to-UF-NMA reduction that applies to FSwA and HSwA signature schemes simultaneously, and that offers an improved reduction loss (without making the zero-knowledge assumption more stringent).
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Fiat-Shamir with abortspost-quantum cryptographyrandom oracle modelQROM
- Contact author(s)
-
pouria fallahpour @ lip6 fr
serge fehr @ cwi nl
yu-hsuan huang @ mpi-sp org - History
- 2026-04-07: revised
- 2025-05-28: received
- See all versions
- Short URL
- https://ia.cr/2025/985
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/985,
author = {Pouria Fallahpour and Serge Fehr and Yu-Hsuan Huang},
title = {Tighter Quantum Security for Fiat-Shamir-with-Aborts and Hash-and-Sign-with-Retry Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/985},
year = {2025},
url = {https://eprint.iacr.org/2025/985}
}
