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

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.