Quantum-access Security of Hash-based Signature Schemes

Quan Yuan; Mehdi Tibouchi; Masayuki Abe

Paper 2023/556

Quantum-access Security of Hash-based Signature Schemes

Quan Yuan

, University of Tokyo

Mehdi Tibouchi

, NTT Social Informatics Laboratories, Kyoto University

Masayuki Abe, NTT Social Informatics Laboratories, Kyoto University

Abstract

In post-quantum cryptography, hash-based signature schemes are attractive choices because of the weak assumptions. Most existing hash-based signature schemes are proven secure against post-quantum chosen message attacks (CMAs), where the adversaries are able to execute quantum computations and classically query to the signing oracle. In some cases, the signing oracle is also considered quantum-accessible, meaning that the adversaries are able to send queries with superpositions to the signing oracle. Considering this, Boneh and Zhandry [BZ13] propose a stronger security notion called existential unforgeability under quantum chosen message attacks (EUF-qCMA). We call it quantum-access security (or Q2 security in some literature). The quantum-access security of practical signature schemes is lacking in research, especially of the hash-based ones. In this paper, we analyze the quantum-access security of hash-based signature schemes in two directions. First, we show concrete quantum chosen message attacks (or superposition attacks) on existing hash-based signature schemes, such as SPHINCS and SPHINCS+. The complexity of the attacks is obviously lower than that of optimal classical chosen message attacks, implying that quantum chosen message attacks are more threatening than classical ones to these schemes. Second, we propose a simple variant of SPHINCS+ and give security proof against quantum chosen message attacks. As far as we know, it is the first practical hash-based stateless signature scheme against quantum chosen message attacks with concrete provable security.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. ACISP 2023
Keywords: hash-based signatures quantum security post-quantum cryptography digital signatures superposition attacks
Contact author(s): yuanquan @ g ecc u-tokyo ac jp
History: 2023-04-24: approved; 2023-04-19: received; See all versions
Short URL: https://ia.cr/2023/556
License: CC BY

BibTeX

@misc{cryptoeprint:2023/556,
      author = {Quan Yuan and Mehdi Tibouchi and Masayuki Abe},
      title = {Quantum-access Security of Hash-based Signature Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/556},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/556}},
      url = {https://eprint.iacr.org/2023/556}
}