SPHINCS+

SPHINCS⁺, also known officially as SLH-DSA, 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 few-time signature scheme called FORS and Merkle trees.
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.
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.
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.

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.
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 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.

History

SPHINCS⁺ is based on the SPHINCS scheme, which was presented at EUROCRYPT 2015.
SPHINCS features a larger 1kB public and private key size and a 41kB signature size.
SPHINCS⁺ was first released in 2017 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, 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.
SPHINCS⁺ was standardized as SLH-DSA by NIST in August 2024 in the FIPS 205 standard, making it one of the two NIST standardized post-quantum signature schemes with the other one being ML-DSA.

Instances

SLH-DSA specifies the following instances based on the hash function, the type and security level :

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

SPHINCS+

Design

Security

History

Instances

Implementations