Paper 2021/1484

On Forging SPHINCS+-Haraka Signatures on a Fault-tolerant Quantum Computer

Robin M. Berger and Marcel Tiepelt

Abstract

SPHINCS+ is a state-of-the-art hash based signature scheme, the security of which is either based on SHA-256, SHAKE-256 or on the Haraka hash function. In this work, we perform an in-depth analysis of how the hash functions are embedded into SPHINCS+ and how the quantum pre-image resistance impacts the security of the signature scheme. Subsequently, we evaluate the cost of implementing Grover’s quantum search algorithm to find a pre-image that admits a universal forgery. In particular, we provide quantum implementations of the Haraka and SHAKE-256 hash functions in Q# and consider the efficiency of attacks in the context of fault-tolerant quantum computers. We restrict our findings to SPHINCS+-128 due to the limited security margin of Haraka. Nevertheless, we present an attack that performs better, to the best of our knowledge, than previously published attacks. We can forge a SPHINCS + -128-Haraka signature in about $1.5 \cdot 2^{90}$ surface code cycles and $2.03 \cdot 10^{6}$ physical qubits, translating to about $1.55 \cdot 2^{101}$ logical-qubit-cycles. For SHAKE-256, the same attack requires $8.65 \cdot 10^{6}$ qubits and $1.6 \cdot 2^{84}$ cycles resulting in about $1.17 \cdot 2^{99}$ logical-qubit-cycles.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.Latincrypt 2021
DOI
10.1007/978-3-030-88238-9_3
Keywords
public-key cryptographypost-quantumcryptanalysisquantum implementation
Contact author(s)
marcel tiepelt @ kit edu
History
2021-11-08: received
Short URL
https://ia.cr/2021/1484
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1484,
      author = {Robin M.  Berger and Marcel Tiepelt},
      title = {On Forging SPHINCS+-Haraka Signatures on a Fault-tolerant Quantum Computer},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1484},
      year = {2021},
      doi = {10.1007/978-3-030-88238-9_3},
      note = {\url{https://eprint.iacr.org/2021/1484}},
      url = {https://eprint.iacr.org/2021/1484}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.