SLHDSA

Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) is a digital signature scheme based on SPHINCS+ and standardized by NIST as FIPS 205. It is one of the three signature schemes selected at the end of the third round of the NIST PQC competition.

As the name implies, it is based on hash functions. More precisely, it relies on the preimage resistance and related properties, not on the collision resistance.

Note

As with the other selected candidates, SLH-DSA introduces some changes to the round 3 version of SPHINCS+, meaning that they are not compatible.

Overview

SLH-DSA is based on SPHINCS+. SPHINCS+ is a “stateless hash-based signature scheme” based on the SPHINCS signature scheme [BHH+14]. Andreas Hülsing has a blog post that goes over the changes made to SPHINCS.

The latest version of the specification document at the time of writing can be found here. Other resources are listed in the Resources section of the SPHINCS+ website.

SPHINCS+ is a stateless hash-based signature scheme, which means that is doesn’t require the user to save a state, unlike stateful schemes like XMSS [BDH11]. The disadvantage of stateful schemes is that reusing one-time key pairs may be catastrophic [GBH18].

The specification provides the following overview: “At a high level, SPHINCS+ works like SPHINCS. The basic idea is to authenticate a huge number of few-time signature (FTS) key pairs using a so-called hypertree. FTS schemes are signature schemes that allow a key pair to produce a small number of signatures, e.g., in the order of ten for our parameter sets. For each new message, a (pseudo)random FTS key pair is chosen to sign the message. The signature consists then of the FTS signature and the authentication information for that FTS key pair. The authentication information is roughly a hypertree signature, i.e. a signature using a certification tree of Merkle tree signatures.”.

Parameters

Description of the SLH-DSA Parameters

Parameter

Description

\(n\)

The security parameter is the length in bytes of the messages that may be signed with WOTS+, as well as the length of the private key, public key and signature elements.

\(h\)

The height of the XMSS hypertree.

\(d\)

The number of layers of XMSS trees.

\(h'\)

The height of a XMSS tree.

\(a\)

The value such that \(2^a\) is the number of byte strings in a single set of a FORS private key.

\(k\)

The number of Merkle trees in FORS, conforming the private key.

\(lg_w\)

The number of bits that are encoded with each WOTS+ hash chain used.

Note that the values are valid for both SHA-2 and SHAKE variants. For example, SLH-DSA-128s applies to both SLH-DSA-SHA2-128s and SLH-DSA-SHAKE-128s.

Parameter sets for SLH-DSA

Parameter set

\(n\)

\(h\)

\(d\)

\(h'\)

\(a\)

\(k\)

\(lg_w\)

\(m\)

security category

SLH-DSA-128s

16

63

7

9

12

14

4

30

1

SLH-DSA-128f

16

66

22

3

6

33

4

34

1

SLH-DSA-192s

24

63

7

9

14

17

4

39

3

SLH-DSA-192f

24

66

22

3

8

33

4

42

3

SLH-DSA-256s

32

64

8

8

14

22

4

47

5

SLH-DSA-256f

32

68

17

4

9

35

4

49

5

Sizes of keys and signatures in SLH-DSA

Parameter set

Public key

Private key

Signature

SLH-DSA-128s

32

64

7856

SLH-DSA-128f

32

64

17088

SLH-DSA-192s

48

96

16224

SLH-DSA-192f

48

96

35664

SLH-DSA-256s

64

128

29792

SLH-DSA-256f

64

128

49856

Implementations

The reference implementation can be found on GitHub: sphincs/sphincsplus. Work for updating the reference implementation to match the FIPS 205 standard can be found in the consistent-basew branch.

It has optimized implementations for the previous version, including an AVX2 version of SPHINCS+-SHA256 and SPHINCS+-SHAKE256.

The Software page of the website lists some third-party implementations such as:

Some integrations not listed there are:

  • Open Quantum Safe’s liboqs.

  • PQClean, which includes the same variations as the reference repository (SHAKE256 with AVX2/in aarch64, SHA256 with AVX2, and Haraka with AES-NI).

Benchmarks

While there are no benchmarks on the website, an extensive one is included in the specification, in Section 10, Table 4.

Benchmarks are also available in the SUPERCOP benchmarking framework.

Considering the number of variants, no benchmarks are proposed here.

Attacks

Some attacks have been published:

  • Breaking Category Five SPHINCS+ with SHA-256 [PKC22], which gives “a complete forgery attack that reduces the concrete classical security of these parameter sets by approximately 40 bits of security”.

  • Practical Fault Injection Attacks on SPHINCS [GKPM18], an attack that “allows the creation of a universal signature forgery that applies to all current standardisation candidates (XMSS, LMS, SPHINCS+, and Gravity-SPHINCS)”.

  • Grafting Trees: a Fault Attack against the SPHINCS framework [CMP18], in which the authors propose “the first fault attack against the framework underlying SPHINCS, Gravity-SPHINCS and SPHINCS+”.

  • On Protecting SPHINCS+ Against Fault Attacks [Gen23], in which the author “adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures”.

Bibliography

[BHH+14]

Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O'Hearn. Sphincs: practical stateless hash-based signatures. Cryptology ePrint Archive, Paper 2014/795, 2014. https://eprint.iacr.org/2014/795. URL: https://eprint.iacr.org/2014/795.

[BDH11]

Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. Xmss - a practical forward secure signature scheme based on minimal security assumptions. Cryptology ePrint Archive, Paper 2011/484, 2011. https://eprint.iacr.org/2011/484. URL: https://eprint.iacr.org/2011/484.

[CMP18]

Laurent Castelnovi, Ange Martinelli, and Thomas Prest. Grafting trees: a fault attack against the sphincs framework. Cryptology ePrint Archive, Paper 2018/102, 2018. https://eprint.iacr.org/2018/102. URL: https://eprint.iacr.org/2018/102.

[Gen23]

Aymeric Genêt. On protecting sphincs+ against fault attacks. Cryptology ePrint Archive, Paper 2023/042, 2023. https://eprint.iacr.org/2023/042. URL: https://eprint.iacr.org/2023/042.

[GKPM18]

Aymeric Genêt, Matthias J. Kannwischer, Hervé Pelletier, and Andrew McLauchlan. Practical fault injection attacks on sphincs. Cryptology ePrint Archive, Paper 2018/674, 2018. https://eprint.iacr.org/2018/674. URL: https://eprint.iacr.org/2018/674.

[GBH18]

L. Groot Bruinderink and A.T. Hülsing. “oops, i did it again” – security of one-time signatures under two-message attacks. In Carlisle Adams and Jan Camenisch, editors, Selected Areas in Cryptography – SAC 2017, Lecture Notes in Computer Science, 299–322. Germany, 2018. Springer. 24th International Conference on Selected Areas in Cryptography (SAC 2017), SAC 2017 ; Conference date: 16-08-2017 Through 18-08-2017. doi:10.1007/978-3-319-72565-9_15.

[PKC22]

Ray Perlner, John Kelsey, and David Cooper. Breaking category five sphincs+ with sha-256. Cryptology ePrint Archive, Paper 2022/1061, 2022. https://eprint.iacr.org/2022/1061. URL: https://eprint.iacr.org/2022/1061.