KIT | KIT-Bibliothek | Impressum | Datenschutz

On Forging SPHINCS$^{+}$-Haraka Signatures on a Fault-Tolerant Quantum Computer

Berger, Robin M. ORCID iD icon; Tiepelt, Marcel

Abstract (englisch):

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 $2.65\cdot 2^{99}$ logical-qubit-cycles.

Postprint §
DOI: 10.5445/IR/1000138852
Veröffentlicht am 01.10.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Kompetenzzentrum für angewandte Sicherheitstechnologie (KASTEL)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-030-88238-9
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000138852
HGF-Programm 46.23.01 (POF IV, LK 01) Methods for Engineering Secure Systems
Erschienen in Progress in Cryptology – LATINCRYPT 2021 – 7th International Conference on Cryptology and Information Security in Latin America, Bogotá, Colombia, October 6–8, 2021, Proceedings. Ed.: P. Longa
Veranstaltung 7th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2021), Online, 06.10.2021 – 08.10.2021
Verlag Springer International Publishing
Seiten 44–63
Serie Lecture Notes in Computer Science ; 12912
Vorab online veröffentlicht am 30.09.2021
Schlagwörter post-quantum cryptography, quantum implementation, resource estimation, cryptanalysis
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page