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 (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.