Paper 2022/346

Recovering the tight security proof of $SPHINCS^{+}$

Andreas Hülsing
Mikhail Kudinov

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.

Available format(s)
Public-key cryptography
Publication info
Post-quantum cryptography hash-based signatures W-OTS SPHINCS+ WOTS-TW hash functions undetectability PRF.
Contact author(s)
andreas @ huelsing net
mishel kudinov @ gmail com
2022-08-19: last of 2 revisions
2022-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andreas Hülsing and Mikhail Kudinov},
      title = {Recovering the tight security proof of $SPHINCS^{+}$},
      howpublished = {Cryptology ePrint Archive, Paper 2022/346},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.