SPHINCS+

From HandWiki
Short description: Post-quantum digital signature scheme
SPHINCS+
General
DesignersJean-Philippe Aumasson, Daniel J. Bernstein, Ward Beullens, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hülsing, Panos Kampanakis, Stefan Kölbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, Bas Westerbaan
First publishedNovember 30, 2017; 8 years ago (2017-11-30)
Derived fromSPHINCS
Detail
Security claims264 signatures before the work needed to forge a signature is less than the required security level
StructureHash-based cryptography

SPHINCS+, also known officially as SLH-DSA,[1] is a post-quantum signature scheme selected by the NIST for the FIPS 205 standard of the post-quantum standardisation process.

Design

SPHINCS+ is based on a one-time signature scheme called WOTS+ (a modified version of the Winternitz one-time signature scheme), a few-time signature scheme called FORS (Forest of Random Subsets) and Merkle trees.[2]

When signing, the message is signed with a FORS key. The FORS key is signed with a WOTS+ key that is a leaf of a merkle tree. The root of the tree is then signed with another WOTS+ key that is itself a leaf of another tree. That tree's root is again signed with a WOTS+. The number of layers of trees is a parameter that is specified as part of the algorithm. This "tree of trees" is called a hypertree. The root of the top tree is the public key. The signature consists of the FORS key and its signature, the WOTS+ keys with their signatures and inclusion proofs for the merkle tree and a random value called R that was used to generate the path in the hypertree.[2]

In order to verify a signature, the verifier first verifies the first WOTS+ key's inclusion proof against the public key and then verifies the key's signature of the next root. Then, they check the next WOTS+ key's inclusion proof against the new root. This goes on until the last WOTS+ key is reached, which is then used to verify the FORS key. That key is then used to actually verify the message's signature.[2]

All WOTS+ keys and FORS keys are generated deterministically from the private key. During signing, the signer generates a random bit string called R and hashes it together with the message. Parts of the resulting hash are used to select the path through the hypertree while the rest is signed with the FORS key.[2]

Security

SPHINCS+ has been called a "conservative" choice by NIST since its security solely relies on the preimage and collision resistance of the underlying hash function.[3][4]

A theoretical forgery attack for specific SHA256 instances has been described that requires a large amount of legitimate signatures and an infeasible amount of computation. It relies on the Merkle–Damgård structure of SHA256[lower-alpha 1] and reduces each security claim by 40 bits. The authors of the attack believe that it doesn't "call the general soundness of the SPHINCS+ design into question" and mitigations have been proposed.[2]

History

SPHINCS+ is based on the SPHINCS scheme, which was presented at EUROCRYPT 2015.[6]

SPHINCS features a larger 1kb public and private key size and a 41kb signature size.[6]

SPHINCS+ was first released in 2017[7] since SPHINCS suffers from a vulnerability called "multi-target attacks in hash-based signatures", which was addressed by a 2016 paper. Furthermore, it doesn't have verifiable index selection (the path through the trees), which enables another kind of multi-target attack. SPHINCS+ was designed to address all these issues and also decrease the key and signature sizes using tree-less WOTS+ key compression, the addition of the R parameter during signing and the replacement of the few-time signature scheme with FORS.[8][9]

SPHINCS+ was standardized as SLH-DSA by NIST in August 2024 in the FIPS 205 standard,[1] making it one of the two NIST standardized post-quantum signature schemes with the other one being ML-DSA.[10][11][12]

Instances

SLH-DSA specifies the following instances based on the hash function (SHA256 or SHAKE256), the type (f for faster signing time and s for shorter signature) and security level (e.g. 128 means that forging signatures is as hard as breaking AES-128):[1][13]

Name Security level Type Hash function Public key size Private key size Signature size
SPHINCS+-SHA2-128s 1[lower-alpha 2] small SHA256 32 64 7856
SPHINCS+-SHAKE-128s SHAKE256
SPHINCS+-SHA2-128f fast SHA256 17088
SPHINCS+-SHAKE-128f SHAKE256
SPHINCS+-SHA2-192s 3[lower-alpha 3] small SHA256 48 96 16224
SPHINCS+-SHAKE-192s SHAKE256
SPHINCS+-SHA2-192f fast SHA256 35664
SPHINCS+-SHAKE-192f SHAKE256
SPHINCS+-SHA2-256s 5[lower-alpha 4] small SHA256 64 128 29792
SPHINCS+-SHAKE-256s SHAKE256
SPHINCS+-SHA2-256f fast SHA256 49856
SPHINCS+-SHAKE-256f SHAKE256

Implementations

References

  1. ↑ SHAKE256 instances are unaffected as they rely on the sponge construction[5]
  2. ↑ Signature forgery should be as hard as a successful key search on AES-128 or a SHA256 collision
  3. ↑ Signature forgery should be as hard as a successful key search on AES-192 or a SHA384 collision
  4. ↑ Signature forgery should be as hard as a successful key search on AES-256
  1. ↑ 1.0 1.1 1.2 Stateless hash-based digital signature standard (Report). Washington, D.C.: National Institute of Standards and Technology (U.S.). August 13, 2024. doi:10.6028/nist.fips.205. 
  2. ↑ 2.0 2.1 2.2 2.3 2.4 "Breaking Category Five SPHINCS+ with SHA-256". https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935143. 
  3. ↑ "Recovering the tight security proof of SPHINCS+". https://eprint.iacr.org/2022/346.pdf. 
  4. ↑ "A Tight Security Proof for SPHINCS+, Formally Verified". January 30, 2025. https://pqshield.com/publications/a-tight-security-proof-for-sphincs-formally-verified/. 
  5. ↑ "Keccak Team". https://keccak.team/sponge_duplex.html. 
  6. ↑ 6.0 6.1 "SPHINCS: Introduction". July 18, 2013. https://sphincs.cr.yp.to/. 
  7. ↑ "SPHINCS+ Submission to the NIST post-quantum project". https://sphincs.org/data/sphincs+-specification.pdf. 
  8. ↑ "SPHINCS+ – The smaller SPHINCS". December 4, 2017. https://huelsing.net/wordpress/?p=558. 
  9. ↑ "Mitigating Multi-Target Attacks in Hash-based Signatures". https://eprint.iacr.org/2015/1256.pdf. 
  10. ↑ Valenta, Luke; Gonçalves, Vânia; Westerbaan, Bas; Rosenberg, Michael; Kipp, Kevin; Dincer, Renan; Araya, Felipe Astroza; Galicer, Mari et al. (August 20, 2024). "NIST's first post-quantum standards". https://blog.cloudflare.com/nists-first-post-quantum-standards/. 
  11. ↑ "SPHINCS+". June 10, 2022. https://openquantumsafe.org/liboqs/algorithms/sig/sphincs.html. 
  12. ↑ Boutin, Chad (August 13, 2024). "NIST Releases First 3 Finalized Post-Quantum Encryption Standards". https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards. 
  13. ↑ "Security (Evaluation Criteria)". January 3, 2017. https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/evaluation-criteria/security-(evaluation-criteria). 
  14. ↑ "randombit/botan: Cryptography Toolkit". March 6, 2013. https://github.com/randombit/botan. 
  15. ↑ "PQC and Lightweight Cryptography Updates". January 24, 2025. https://www.bouncycastle.org/resources/pqc-and-lightweight-cryptography-updates-bouncy-castle-1-80-java/. 
  16. ↑ Hess, Tjaden (August 15, 2024). "We wrote the code, and the code won". https://blog.trailofbits.com/2024/08/15/we-wrote-the-code-and-the-code-won/. 
  17. ↑ "open-quantum-safe/liboqs: C library for prototyping and experimenting with quantum-resistant cryptography". August 12, 2016. https://github.com/open-quantum-safe/liboqs?tab=readme-ov-file#supported-algorithms. 



Retrieved from "https://handwiki.org/wiki/index.php?title=SPHINCS%2B&oldid=4156678"