Paper 2022/1359
Probabilistic Hash-and-Sign with Retry in the Quantum Random Oracle Model
Abstract
A hash-and-sign signature based on a preimage-sampleable function (PSF) (Gentry et al. [STOC 2008]) is secure in the Quantum Random Oracle Model (QROM) if the PSF is collision-resistant (Boneh et al. [ASIACRYPT 2011]) or one-way (Zhandry [CRYPTO 2012]). However, trapdoor functions (TDFs) in code-based and multivariate-quadratic-based (MQ-based) signatures are not PSFs; for example, underlying TDFs of the Courtois-Finiasz-Sendrier (CFS), Unbalanced Oil and Vinegar (UOV), and Hidden Field Equations (HFE) signatures are not surjections. Thus, such signature schemes adopt probabilistic hash-and-sign with retry. This paradigm is secure in the (classical) Random Oracle Model (ROM), assuming that the underlying TDF is non-invertible, that is, it is hard to find a preimage of a given random value in the range (e.g., Sakumoto et al. [PQCRYPTO 2011] for the modified UOV/HFE signatures). Unfortunately, there is currently no known security proof for the probabilistic hash-and-sign with retry in the QROM. We give the first security proof for the probabilistic hash-and-sign with retry in the QROM, assuming that the underlying non-PSF TDF is non-invertible. Our reduction from the non-invertibility assumption is tighter than the existing ones that apply only to signature schemes based on PSFs. We apply the security proof to code-based and MQ-based signatures. Additionally, we extend the proof into the multi-key setting and propose a generic method that provides security reduction without any security loss in the number of keys.
Note: 1/18/2023: The new version fixes the EUF-CMA security proof of the probabilistic hash-and-sign (main theorem) using the semi-classical O2H technique. This adds another term to the security bound of the EUF-CMA/sEUF-CMA security proofs and security proofs for some existing signature schemes. 6/1/2023: We have restructured the organization and added a security analysis of the original UOV signature. 10/19/2023: We made three modifications: First, we slightly improved the security bound of the main theorem (a factor of the last term is changed from 2(q_sign+q_qro+2) to 2(q_qro+2)). Second, we added an alternative security proof of EUF-NMA->EUF-CMA of the Fiat-Shamir with aborts using the same techniques as the main theorem. Last, we refined the notation of the measure-and-reprogram technique.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- post-quantum cryptographydigital signaturehash-and-signquantum random oracle model (QROM)preimage sampleable function
- Contact author(s)
-
harucrypto @ gmail com
keita xagawa @ tii ae - History
- 2023-10-19: last of 3 revisions
- 2022-10-11: received
- See all versions
- Short URL
- https://ia.cr/2022/1359
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1359, author = {Haruhisa Kosuge and Keita Xagawa}, title = {Probabilistic Hash-and-Sign with Retry in the Quantum Random Oracle Model}, howpublished = {Cryptology ePrint Archive, Paper 2022/1359}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1359}}, url = {https://eprint.iacr.org/2022/1359} }