[Resource Topic] 2021/1484: On Forging SPHINCS+-Haraka Signatures on a Fault-tolerant Quantum Computer

Welcome to the resource topic for 2021/1484

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

Authors: Robin M. Berger, Marcel Tiepelt


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.

ePrint: https://eprint.iacr.org/2021/1484

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .