Welcome to the resource topic for 2021/1484
Title:
On Forging SPHINCS±Haraka Signatures on a Fault-tolerant Quantum Computer
Authors: Robin M. Berger, 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.
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 .