Signatures with Memory-Tight Security in the Quantum Random Oracle Model

Keita Xagawa

Paper 2023/1734

Signatures with Memory-Tight Security in the Quantum Random Oracle Model

Keita Xagawa

, Technology Innovation Institute

Abstract

Memory tightness of reductions in cryptography, in addition to the standard tightness related to advantage and running time, is important when the underlying problem can be solved efficiently with large memory, as discussed in Auerbach, Cash, Fersch, and Kiltz (CRYPTO 2017). Diemert, Geller, Jager, and Lyu (ASIACRYPT 2021) and Ghoshal, Ghosal, Jaeger, and Tessaro (EUROCRYPT 2022) gave memory-tight proofs for the multi-challenge security of digital signatures in the random oracle model. This paper studies the memory-tight reductions for _post-quantum_ signature schemes in the _quantum_ random oracle model. Concretely, we show that signature schemes from lossy identification are multi-challenge secure in the quantum random oracle model via memory-tight reductions. Moreover, we show that the signature schemes from lossy identification achieve more enhanced securities considering _quantum_ signing oracles proposed by Boneh and Zhandry (CRYPTO 2013) and Alagic, Majenz, Russel, and Song (EUROCRYPT 2020). We additionally show that signature schemes from preimage-sampleable functions achieve those securities via memory-tight reductions.

Note: 2024-06-07: We correct typos. 2024-02-28: We move some sections in the appendix to the main body and modify the bounds slightly. 2024-01-09: We correct errors in the proofs to remove the requirement on LID and extend the proofs to the divergence HVZK cases.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2024
DOI: 10.1007/978-3-031-58754-2_2
Keywords: post-quantum signature memory-tight reductions QROM plus-one unforgeability blinded unforgeability
Contact author(s): keita xagawa @ tii ae
History: 2024-06-07: last of 5 revisions; 2023-11-09: received; See all versions
Short URL: https://ia.cr/2023/1734
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1734,
      author = {Keita Xagawa},
      title = {Signatures with Memory-Tight Security in the Quantum Random Oracle Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1734},
      year = {2023},
      doi = {10.1007/978-3-031-58754-2_2},
      url = {https://eprint.iacr.org/2023/1734}
}