[Resource Topic] 2022/346: Recovering the tight security proof of $SPHINCS^{+}$

Welcome to the resource topic for 2022/346

Title:
Recovering the tight security proof of SPHINCS^{+}

Authors: Andreas Hülsing, Mikhail Kudinov

Abstract:

In 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the SPHINCS^{+} construction. This work gives a new tight security proof for SPHINCS^{+}. The flaw can be traced back to the security proof for the Winternitz one-time signature scheme (WOTS) used within SPHINCS^{+}. In this work, we give a standalone description of the WOTS variant used in SPHINCS+ that we call WOTS-TW. We provide a security proof for WOTS-TW and multi-instance WOTS-TW against non-adaptive chosen message attacks where the adversary only learns the public key after it made its signature query. Afterwards, we show that this is sufficient to give a tight security proof for SPHINCS^{+}. We recover almost the same bound for the security of SPHINCS^{+}, with only a factor w loss compared to the previously claimed bound, where w is the Winternitz parameter that is commonly set to 16. On a more technical level, we introduce new lower bounds on the quantum query complexity for generic attacks against properties of cryptographic hash functions and analyse the constructions of tweakable hash functions used in SPHINCS^{+} with regard to further security properties.

ePrint: https://eprint.iacr.org/2022/346

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 .

1 Like