Paper 2022/1359

Probabilistic Hash-and-Sign with Retry in the Quantum Random Oracle Model

Haruhisa Kosuge, Japan Ministry of Defense
Keita Xagawa, Technology Innovation Institute

A hash-and-sign signature based on a preimage-sampleable function (Gentry et al., STOC 2008) is secure in the quantum random oracle model if the preimage-sampleable function is collision-resistant (Boneh et al., ASIACRYPT 2011) or one-way (Zhandry, CRYPTO 2012). However, trapdoor functions in code-based and multivariate-quadratic-based signatures are not preimage-sampleable functions; for example, underlying trapdoor functions of the Courtois-Finiasz-Sendrier, 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. While Sakumoto et al. in PQCRYPTO 2011 showed the security of this paradigm in the classical random oracle model, their proof contains an error. Also, there is currently no known security proof for the probabilistic hash-and-sign with retry in the quantum random oracle model. We correct the proof in the random oracle model and give the first security proof in the quantum random oracle model for the probabilistic hash-and-sign with retry, assuming that the underlying trapdoor function is non-invertible, that is, it is hard to find a preimage of a given random value in the range. Our reduction from the non-invertibility assumption is tighter than the existing ones that apply only to signature schemes based on preimage-sampleable functions. We apply the security proof to code-based and multivariate-quadratic-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. 8/2/2024: We add a security proof of the probabilistic hash-and-sign with retry in the (classical) ROM.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2024
post-quantum cryptographydigital signaturehash-and-signquantum random oracle model (QROM)preimage sampleable function
Contact author(s)
harucrypto @ gmail com
keita xagawa @ tii ae
2024-02-08: last of 5 revisions
2022-10-11: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.