Paper 2022/1359

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

Haruhisa Kosuge, Japan Ministry of Defense
Keita Xagawa, NTT Social Informatics Laboratories
Abstract

A hash-and-sign signature based on 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 surjection. 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 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 is tighter than the existing ones that apply to only signature schemes based on PSFs. We apply the security proof to code-based and MQ-based signatures. Moreover, we extend the proof into the multi-key setting by using prefix hashing (Duman et al. [ACM CCS 2021]).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
post-quantum cryptography digital signature hash-and-sign quantum random oracle model (QROM) preimage sampleable function
Contact author(s)
harucrypto @ gmail com
keita xagawa @ ntt com
History
2022-10-14: approved
2022-10-11: received
See all versions
Short URL
https://ia.cr/2022/1359
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.