Paper 2021/1484
On Forging SPHINCS+Haraka Signatures on a Faulttolerant Quantum Computer
Robin M. Berger and Marcel Tiepelt
Abstract
SPHINCS+ is a stateoftheart hash based signature scheme, the security of which is either based on SHA256, SHAKE256 or on the Haraka hash function. In this work, we perform an indepth analysis of how the hash functions are embedded into SPHINCS+ and how the quantum preimage resistance impacts the security of the signature scheme. Subsequently, we evaluate the cost of implementing Grover’s quantum search algorithm to find a preimage that admits a universal forgery. In particular, we provide quantum implementations of the Haraka and SHAKE256 hash functions in Q# and consider the efficiency of attacks in the context of faulttolerant 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 + 128Haraka 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}$ logicalqubitcycles. For SHAKE256, 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}$ logicalqubitcycles.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision.Latincrypt 2021
 DOI
 10.1007/9783030882389_3
 Keywords
 publickey cryptographypostquantumcryptanalysisquantum implementation
 Contact author(s)
 marcel tiepelt @ kit edu
 History
 20211108: received
 Short URL
 https://ia.cr/2021/1484
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1484, author = {Robin M. Berger and Marcel Tiepelt}, title = {On Forging SPHINCS+Haraka Signatures on a Faulttolerant Quantum Computer}, howpublished = {Cryptology ePrint Archive, Paper 2021/1484}, year = {2021}, doi = {10.1007/9783030882389_3}, note = {\url{https://eprint.iacr.org/2021/1484}}, url = {https://eprint.iacr.org/2021/1484} }