NIST FIPS 205 日本語訳

Federal Information Processing Standards Publication

Category: Computer Security

Subcategory: Cryptography

Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8900

This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.205

Published: August 13, 2024

U.S. Department of Commerce Gina M. Raimondo, Secretary

National Institute of Standards and Technology Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

The Federal Information Processing Standards Publication (FIPS) series of the National Institute of Standards and Technology (NIST) is the official series of publications relating to standards and guidelines developed under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Comments concerning this Federal Information Processing Standard publication are welcomed and should be submitted using the contact information in the “Inquiries and comments” clause of the announcement section.

Kevin M. Stine, Director Information Technology Laboratory

This standard specifies the stateless hash-based digital signature algorithm (SLH-DSA). Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. SLH-DSA is based on SPHINCS+, which was selected for standardization as part of the NIST Post-Quantum Cryptography Standardization process.

Keywords: computer security; cryptography; digital signatures; Federal Information Processing Standards; hash-based signatures; post-quantum; public-key cryptography.

Federal Information Processing Standards Publication 205

Published: August 13, 2024 Effective: August 13, 2024

Federal Information Processing Standards (FIPS) publications are developed by the National Institute of Standards and Technology (NIST) under 15 U.S.C. 278g-3 and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Signature generation uses a private key to generate a digital signature. Signature verification uses a public key that corresponds to but is not the same as the private key. Each signatory possesses a private and public key pair. Public keys may be known by the public, but private keys must be kept secret. Anyone can verify the signature by employing the signatory’s public key. Only the user who possesses the private key can perform signature generation.

The digital signature is provided to the intended verifier along with the signed data. The verifying entity verifies the signature by using the claimed signatory’s public key. Similar procedures may be used to generate and verify signatures for both stored and transmitted data.

This standard specifies several parameter sets for SLH-DSA that are approved for use. Additional parameter sets may be specified and approved in future NIST Special Publications.

The adoption and use of this standard are available to private and commercial organizations.

Agencies are advised that digital signature key pairs shall not be used for other purposes.

c. Specified in the list of approved security functions in SP 800-140C.

Similarly, the use of a product containing an implementation that conforms to this standard does not guarantee the security of the overall system in which the product is used. The responsible authority in each agency or department shall ensure that an overall implementation provides an acceptable level of security.

Since a standard of this nature must be flexible enough to adapt to advancements and innovations in science and technology, this standard will be reviewed every five years in order to assess its adequacy.

National Institute of Standards and Technology (2024) Stateless Hash-Based Digital Signature Standard. (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 205. https://doi.org/10.6028/NIST.FIPS.205

Federal Information Processing Standards Publication 205

This standard defines a method for digital signature generation that can be used for the protection of binary data (commonly called a message) and for the verification and validation of those digital signatures.¹ The security of the stateless hash-based digital signature algorithm (SLH-DSA) relies on the presumed difficulty of finding preimages for hash functions as well as several related properties of the same hash functions. Unlike the algorithms specified in FIPS 186-5 [1], SLH-DSA is designed to provide resistance against attacks from a large-scale quantum computer.

This standard specifies the mathematical steps that need to be performed for key generation, signature generation, and signature verification. Additional assurances are required for digital signatures to be valid (e.g., the assurance of identity and private key possession). SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies the required assurances and the methods for obtaining these assurances.

Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems will be at risk if large-scale quantum computers are ever realized. This would include key-establishment schemes and digital signatures that are based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). As a result, in 2016, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process to select quantum-resistant public-key cryptographic algorithms for standardization. A total of 82 candidate algorithms were submitted to NIST for consideration.

After three rounds of evaluation and analysis, NIST selected the first four algorithms for standardization. These algorithms are intended to protect sensitive U.S. Government information well into the foreseeable future, including after the advent of cryptographically relevant quantum computers. This standard includes the specification for one of the algorithms selected: SPHINCS+, a stateless hash-based digital signature scheme. This standard contains several minor modifications compared to Version 3 [4], which was submitted at the beginning of round three of the NIST PQC Standardization process. The changes are described in Appendix A. Throughout this standard, SPHINCS+ will be referred to as SLH-DSA for stateless hash-based digital signature algorithm.

approved — FIPS-approved and/or NIST-recommended. An algorithm or technique that is either 1) specified in a FIPS or NIST recommendation, 2) adopted in a FIPS or NIST recommendation, or 3) specified in a list of NIST-approved security functions. [1]

big-endian — The property of a byte string having its bytes positioned in order of decreasing significance. In particular, the leftmost (first) byte is the most significant, and the rightmost (last) byte is the least significant. The term “big-endian” may also be applied in the same manner to bit strings. [5, adapted]

byte string — An array of integers in which each integer is in the set \(\{0, \ldots, 255\}\).

claimed signatory — From the verifier’s perspective, the claimed signatory is the entity that purportedly generated a digital signature. [1]

destroy — An action applied to a key or a piece of secret data. After a key or a piece of secret data is destroyed, no information about its value can be recovered. [1]

digital signature — The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity, and signatory non-repudiation. [1]

entity — An individual (person), organization, device, or process. Used interchangeably with party. [1]

equivalent process — Two processes are equivalent if the same output is produced when the same values are input to each process (either as input parameters, as values made available during the process, or both). [1]

extendable-output function — A function on bit strings in which the output can be extended to any desired length. Approved XOFs (such as those specified in FIPS 202 [6]) are designed to satisfy the following properties as long as the specified output length is sufficiently long to prevent trivial attacks:

fresh random value — A previously unused output of a random bit generator.

hash function — A function on bit strings in which the length of the output is fixed. Approved hash functions (such as those specified in FIPS 180 [8] and FIPS 202 [6]) are designed to satisfy the following properties:

hash value — See message digest.

key — A parameter used in conjunction with a cryptographic algorithm that determines its operation. Examples applicable to this standard include:

key pair — A public key and its corresponding private key. [1]

message — The data that is signed. Also known as signed data during the signature verification and validation process. [1]

message digest — The result of applying a hash function to a message. Also known as a hash value. [1]

non-repudiation — A service that is used to provide assurance of the integrity and origin of data in such a way that the integrity and origin can be verified and validated by a third party as having originated from a specific entity in possession of the private key (i.e., the signatory). [1]

owner — A key pair owner is the entity authorized to use the private key of a key pair. [1]

party — An individual (person), organization, device, or process. Used interchangeably with entity. [1]

private key — A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm. The private key is uniquely associated with the owner and is not made public. The private key is used to compute a digital signature that may be verified using the corresponding public key. [1]

pseudorandom — A process or data produced by a process is said to be pseudorandom when the outcome is deterministic yet also effectively random as long as the internal action of the process is hidden from observation. For cryptographic purposes, “effectively random” means “computationally indistinguishable from random within the limits of the intended security strength.” [1]

public key — A cryptographic key that is used with an asymmetric (public-key) cryptographic algorithm and is associated with a private key. The public key is associated with an owner and may be made public. In the case of digital signatures, the public key is used to verify a digital signature that was generated using the corresponding private key. [1]

security category — A number associated with the security strength of a post-quantum cryptographic algorithm, as specified by NIST (see [9, Sect. 5.6]).

security strength — A number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm or system. [1]

shall — Used to indicate a requirement of this standard. [1]

should — Used to indicate a strong recommendation but not a requirement of this standard. Ignoring the recommendation could result in undesirable results. [1]

signatory — The entity that generates a digital signature on data using a private key. [1]

signature generation — The process of using a digital signature algorithm and a private key to generate a digital signature on data. [1]

signature validation — The (mathematical) verification of the digital signature and obtaining the appropriate assurances (e.g., public-key validity, private-key possession, etc.). [1]

signature verification — The process of using a digital signature algorithm and a public key to verify a digital signature on data. [1]

signed data — The data or message upon which a digital signature has been computed. Also see message. [1]

verifier — The entity that verifies the authenticity of a digital signature using the public key. [1]

ADRS — Address

ADRS\(^{c}\) — Compressed Address

AES — Advanced Encryption Standard

DER — Distinguished Encoding Rules

FIPS — Federal Information Processing Standard

FORS — Forest of Random Subsets

ITL — Information Technology Laboratory

MGF — Mask Generation Function

NIST — National Institute of Standards and Technology

OID — Object Identifier

PQC — Post-Quantum Cryptography

PRF — Pseudorandom Function

SHA — Secure Hash Algorithm

SHAKE — Secure Hash Algorithm KECCAK

SP — Special Publication

RFC — Request for Comments

WOTS\(^+\) — Winternitz One-Time Signature Plus

XMSS — eXtended Merkle Signature Scheme

XOF — eXtendable-Output Function

\(X \parallel Y\) — The concatenation of two arrays \(X\) and \(Y\). If \(X\) is an array of length \(\ell_x\), and \(Y\) is an array of length \(\ell_y\), then \(Z = X \parallel Y\) is an array of length \(\ell_x + \ell_y\) such that

\(X[i : j]\) — A subarray of \(X\). If \(X\) is an array of length \(\ell_x\), \(0 \le i < j \le \ell_x\), and \(Y = X[i : j]\), then \(Y\) is an array of length \(j - i\) such that \(Y[k] = X[i + k]\) for \(0 \le k < j - i\).

\(\mathsf{Trunc}_\ell(X)\) — A truncation function that outputs the leftmost \(\ell\) bytes of the input byte string \(X\). If \(Y = \mathsf{Trunc}_\ell(X)\), then \(Y\) is a byte string (array) of length \(\ell\) such that \(Y[i] = X[i]\) for \(0 \le i < \ell\) (i.e., \(Y = X[0 : \ell]\)).

\(|X|\) — The length (in bytes) of byte string \(X\).

\(\lceil a \rceil\) — The ceiling of \(a\); the smallest integer that is greater than or equal to \(a\). For example, \(\lceil 5 \rceil = 5\), \(\lceil 5.3 \rceil = 6\), and \(\lceil -2.1 \rceil = -2\). [1]

\(\lfloor a \rfloor\) — The floor of \(a\); the largest integer that is less than or equal to \(a\). For example, \(\lfloor 5 \rfloor = 5\), \(\lfloor 5.3 \rfloor = 5\), and \(\lfloor -2.1 \rfloor = -3\). [1]

\(a \bmod n\) — The unique remainder \(r\), \(0 \le r \le (n - 1)\), when integer \(a\) is divided by the positive integer \(n\). For example, \(23 \bmod 7 = 2\). [1]

\(a \cdot b\) — The product of \(a\) and \(b\). For example, \(3 \cdot 5 = 15\).

\(a^b\) — \(a\) raised to the power \(b\). For example, \(2^5 = 32\).

\(\log_2 x\) — The base 2 logarithm of \(x\). For example, \(\log_2(16) = 4\).

0b — The prefix to a number that is represented in binary.

0x — The prefix to a number that is represented in hexadecimal. [1, adapted]

\(a \gg b\) — The logical right shift of \(a\) by \(b\) positions (i.e., \(a \gg b = \lfloor a/2^b \rfloor\)). For example, \(\text{0x}73 \gg 4 = 7\). [10, adapted]

\(a \ll b\) — The logical left shift of \(a\) by \(b\) positions (i.e., \(a \ll b = a \cdot 2^b\)). For example, \(\text{0x}73 \ll 4 = \text{0x}730\). [10, adapted]

\(a \oplus b\) — The bitwise exclusive-or of \(a\) and \(b\). For example, \(115 \oplus 1 = 114\) (\(115 \oplus 1 = \text{0b}01110011 \oplus \text{0b}00000001 = \text{0b}01110010 = 114\)).

\(s \leftarrow x\) — In pseudocode, this notation means that the variable \(s\) is set to the value of the expression \(x\).

\(s \xleftarrow{\$} \mathbb{B}^n\) — In pseudocode, this notation means that the variable \(s\) is set to a byte string of length \(n\) chosen at random. A fresh random value is generated for each time this step is performed.

\(\bot\) — A symbol indicating failure or the lack of output from an algorithm.

SLH-DSA is a stateless hash-based signature scheme that is constructed using other hash-based signature schemes as components: (1) a few-time signature scheme, forest of random subsets (FORS), and (2) a multi-time signature scheme, the eXtended Merkle Signature Scheme (XMSS). XMSS is constructed using the hash-based one-time signature scheme Winternitz One-Time Signature Plus (WOTS+) as a component.²

Conceptually, an SLH-DSA key pair consists of a very large set of FORS key pairs.³ The few-time signature scheme FORS allows each key pair to safely sign a small number of messages. An SLH-DSA signature is created by computing a randomized hash of the message, using part of the resulting message digest to pseudorandomly select a FORS key, and signing the remaining part of the message digest with that key. An SLH-DSA signature consists of the FORS signature and the information that authenticates the FORS public key. The authentication information is created using XMSS signatures.

XMSS is a multi-time signature scheme that is created using a combination of WOTS+ one-time signatures and Merkle hash trees [13]. An XMSS key consists of \(2^{h'}\) WOTS+ keys and can sign \(2^{h'}\) messages. The WOTS+ public keys are formed into a Merkle hash tree, and the root of the tree is the XMSS public key. (The Merkle hash tree formed from the WOTS+ keys is also referred to as an XMSS tree.) An XMSS signature consists of a WOTS+ signature and an authentication path within the Merkle hash tree for the WOTS+ public key. In Figure 1, triangles represent XMSS trees, squares represent the WOTS+ public keys, and circles represent the interior nodes of the hash tree. Within an XMSS tree, the square and circles that are filled in represent the authentication path for the WOTS+ public key needed to verify the signature.

The authentication information for a FORS public key is a hypertree signature. A hypertree is a tree of XMSS trees, as depicted in Figure 1. The tree consists of \(d\) layers⁴ in which the top layer (layer \(d-1\)) consists of a single XMSS tree, the next layer down (layer \(d-2\)) consists of \(2^{h'}\) XMSS trees, and the lowest layer (layer 0) consists of \(2^{(d-1)h'}\) XMSS trees. The public key of each XMSS key at layers 0 through \(d-2\) is signed by an XMSS key at the next higher layer. The XMSS keys at layer 0 collectively have \(2^{dh'} = 2^h\) WOTS+ keys, which are used to sign the \(2^h\) FORS public keys in the SLH-DSA key pair. The sequence of \(d\) XMSS signatures needed to authenticate a FORS public key when starting with the public key of the XMSS key at layer \(d-1\) is a hypertree signature. An SLH-DSA signature consists of a FORS signature along with a hypertree signature.

An SLH-DSA public key (Figure 16) contains two \(n\)-byte components: (1) \(\mathbf{PK}\).root, which is the public key of the XMSS key at layer \(d-1\), and (2) \(\mathbf{PK}\).seed, which is used to provide domain separation between different SLH-DSA key pairs. An SLH-DSA private key (Figure 15) consists of an \(n\)-byte seed \(\mathbf{SK}\).seed that is used to pseudorandomly generate all of the secret values for the WOTS+ and FORS keys and an \(n\)-byte key \(\mathbf{SK}\).prf that is used in the generation of the randomized hash of the message. An SLH-DSA private key also includes copies of \(\mathbf{PK}\).root and \(\mathbf{PK}\).seed, as these values are needed during both signature generation and signature verification.

Figure 1. An SLH-DSA signature

The WOTS+ one-time signature scheme is specified in Section 5, and the XMSS multi-time signature scheme is specified in Section 6. Section 7 specifies the generation and verification of hypertree signatures. The FORS few-time signature scheme is specified in Section 8. Finally, Section 9 specifies the SLH-DSA key generation, signature, and verification functions. As the WOTS+, XMSS, hypertree, and FORS schemes described in this standard are not intended for use as stand-alone signature schemes, only the components of the schemes necessary to implement SLH-DSA are described. In particular, these sections do not include functions for key pair generation, and a signature verification function is only specified for hypertree signatures.

When used in this standard, WOTS+, XMSS, and FORS signatures are implicitly verified using functions to generate public keys from messages and signatures (see Sections 5.3, 6.3, and 8.4). When verifying an SLH-DSA signature, the randomized hash of the message and the FORS signature are used to compute a candidate FORS public key. The candidate FORS public key and the WOTS+ signature from the layer 0 XMSS key are used to compute a candidate WOTS+ public key, which is then used in conjunction with the corresponding authentication path to compute a candidate XMSS public key. The candidate layer 0 XMSS public key is used along with the layer 1 XMSS signature to compute a candidate layer 1 XMSS public key. This process is repeated until a candidate layer \(d-1\) public key has been computed. SLH-DSA signature verification succeeds if the computed candidate layer \(d-1\) XMSS public key is the same as the SLH-DSA public key root \(\mathbf{PK}.\mathrm{root}\).

This section specifies requirements for cryptographic modules that implement SLH-DSA. Section 3.2 discusses issues that implementers of cryptographic modules should take into consideration but that are not requirements. SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [3], specifies requirements that apply to the use of digital signature schemes.

SLH-DSA key generation (Algorithm 21) requires the generation of three random \(n\)-byte values: \(\mathbf{PK}.\mathrm{seed}\), \(\mathbf{SK}.\mathrm{seed}\), and \(\mathbf{SK}.\mathrm{prf}\), where \(n\) is 16, 24, or 32, depending on the parameter set. For each invocation of key generation, each of these values shall be a fresh (i.e., not previously used) random value generated using an approved random bit generator (RBG), as prescribed in SP 800-90A, SP 800-90B, and SP 800-90C [14, 15, 16]. Moreover, the RBG used shall have a security strength of at least \(8n\) bits. See Table 2 for the value of \(n\) for each parameter set.

Data used internally by key generation and signing algorithms in intermediate computation steps could be used by an adversary to gain information about the private key and thereby compromise security. The data used internally by verification algorithms is similarly sensitive for some applications, including the verification of signatures that are used as bearer tokens (i.e., authentication secrets) or signatures on plaintext messages that are intended to be confidential. Intermediate values of the verification algorithm may reveal information about its inputs (i.e., the message, signature, and public key), and in some applications, security or privacy requires one or more of these inputs to be confidential. Therefore, implementations of SLH-DSA shall ensure that any local copies of the inputs and any potentially sensitive intermediate data are destroyed as soon as they are no longer needed.

SP 800-89 imposes requirements for the assurance of public-key validity and private-key possession. In the case of SLH-DSA, where public-key validation is required, implementations shall verify that the public key is \(2n\) bytes in length. When the assurance of private key possession is obtained via regeneration, the owner of the private key shall check that the private key is \(4n\) bytes in length and shall use \(\mathbf{SK}.\mathrm{seed}\) and \(\mathbf{PK}.\mathrm{seed}\) to recompute \(\mathbf{PK}.\mathrm{root}\) and compare the newly generated value with the value in the private key currently held.

Implementations of SLH-DSA shall not use floating-point arithmetic, as rounding errors in floating point operations may lead to incorrect results in some cases. In all pseudocode in this standard in which division is performed (e.g., \(x/y\)) and \(y\) may not divide \(x\), either \(\lfloor x/y \rfloor\) or \(\lceil x/y \rceil\) is used. Both of these can be computed without floating-point arithmetic, as ordinary integer division \(x/y\) computes \(\lfloor x/y \rfloor\), and \(\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor\) for non-negative integers \(x\) and positive integers \(y\).

While the value of \(\mathit{len}_2\) (see Equation 5.3) may be computed without using floating-point arithmetic (see Algorithm 1), it is recommended that this value be precomputed. For all parameter sets in this standard, \(\mathit{len}_2\) is 3.

This section discusses some implementation considerations for SLH-DSA.

As WOTS\(^+\), XMSS, FORS, and hypertree signature schemes are not approved for use as stand-alone signature schemes, cryptographic modules should not make interfaces to these components available to applications. SP 800-208 [12] specifies approved stateful hash-based signature schemes.

For signature schemes, the secrecy of the private key is critical. Care must be taken to protect implementations against attacks, such as side-channel attacks or fault attacks [17, 18, 19, 20, 21]. A cryptographic device may leak critical information with side-channel analysis or attacks that allow internal data or keying material to be extracted without breaking the cryptographic primitives.

The specification of SLH-DSA makes use of six functions — \(\mathbf{PRF}_{msg}\), \(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{T}_\ell\), \(\mathbf{H}\), and \(\mathbf{F}\) — that are all implemented using hash functions or XOFs with fixed output lengths. The inputs and output of each function are byte strings. In the following definitions, \(\mathbb{B} = \{0, \dots, 255\}\) denotes the set of all bytes, \(\mathbb{B}^n\) denotes the set of byte strings of length \(n\) bytes, and \(\mathbb{B}^*\) denotes the set of all byte strings. The \(\mathbf{ADRS}\) input is described in Section 4.2.

The specific instantiations for these functions differ for different parameter sets and are specified in Section 11.

Four of the functions described in Section 4.1 take a 32-byte address (i.e., \(\mathbf{ADRS}\)) as input. An \(\mathbf{ADRS}\) consists of public values that indicate the position of the value being computed by the function. A different \(\mathbf{ADRS}\) value is used for each call to each function. In the case of \(\mathbf{PRF}\), this is used to generate a large number of different secret values from a single seed. In the case of \(\mathbf{T}_\ell\), \(\mathbf{H}\), and \(\mathbf{F}\), it is used to mitigate multi-target attacks. In the pseudocode, where addresses are passed as parameters, they may be passed either by reference or by value.

The structure of an \(\mathbf{ADRS}\) conforms to word boundaries, with each word being 4 bytes long and values encoded as unsigned integers in big-endian byte order (see Figure 2). The first word of \(\mathbf{ADRS}\) specifies the layer address, which is the height of an XMSS tree within the hypertree. Trees on the bottom layer have a height of zero, and the single XMSS tree at the top has a height of \(d - 1\) (see Figure 1). The next three words of \(\mathbf{ADRS}\) specify the tree address, which is the position of an XMSS tree within a layer of the hypertree. The leftmost XMSS tree in a layer has a tree address of zero, and the rightmost XMSS tree in layer \(L\) has a tree address of \(2^{(d-1-L)h'} - 1\). The next word is used to specify the type of the address, which differs depending on the use case.

There are seven different types of address used in SLH-DSA, as described below.⁵ The address type determines how the final 12 bytes of the address are to be interpreted. The algorithms in this standard are written based on the assumption that whenever the type in an \(\mathbf{ADRS}\) is changed, the final 12 bytes of the address are initialized to zero.

Figure 2. Address (ADRS)

The type is set to WOTS_HASH (i.e., \(type = 0\)) for a WOTS\(^+\) hash address (see Figure 3), which is used when computing hash chains in WOTS\(^+\). When type is WOTS_HASH, the next word encodes the key pair address, which is the index of the WOTS\(^+\) key pair within the XMSS tree specified by the layer and tree addresses, with the leftmost WOTS\(^+\) key having an index of zero and the rightmost WOTS\(^+\) key having an index of \(2^{h'} - 1\). Next is the chain address, which encodes the index of the chain within WOTS\(^+\), followed by the hash address, which encodes the address of the hash function within the chain.

Figure 3. WOTS\(^+\) hash address

Figure 4. WOTS\(^+\) public-key compression address

The type is set to WOTS_PK (i.e., \(type = 1\)) when compressing WOTS\(^+\) public keys (see Figure 4). As when the type is WOTS_HASH, the next word encodes the index of the WOTS\(^+\) key pair within the XMSS tree specified by the layer and tree addresses. The remaining two words of \(\mathbf{ADRS}\) are not needed and are set to zero.

The type is set to TREE (i.e., \(type = 2\)) when computing the hashes within the XMSS tree (see Figure 5). For this type of address, the next word is always set to zero. The following word encodes the height of the node within the tree that is being computed, and the final word encodes the index of the node at that height.

Figure 5. Hash tree address

The type is set to FORS_TREE (i.e., \(\mathit{type} = 3\)) when computing hashes within the FORS tree (see Figure 6). The next word is the key pair address, which encodes the FORS key that is used. The value is the same as the key pair address for the WOTS\(^+\) key used to sign the FORS key (see Figure 3 and Figure 4). The next two words — the tree height and tree index — encode the node within the FORS tree that is being computed. The tree height starts with zero for the leaf nodes. The tree index is counted continuously across the \(k\) different FORS trees. The leftmost node in the leftmost tree has an index of zero, and the rightmost node in the rightmost tree at level \(j\) has an index of \(k \cdot 2^{(a-j)} - 1\), where \(a\) is the height of the tree.

Figure 6. FORS tree address

Figure 7. FORS tree roots compression address

The type is set to FORS_ROOTS (i.e., \(\mathit{type} = 4\)) when compressing the \(k\) FORS tree roots (see Figure 7). The next word is the key pair address, which has the same meaning as it does in the FORS_TREE address. The remaining two words of \(\mathbf{ADRS}\) are not needed and are set to zero.

The type is set to WOTS_PRF (i.e., \(\mathit{type} = 5\)) when generating secret values for WOTS\(^+\) keys (see Figure 8). The values for the other words in the address are set to the same values as for the WOTS_HASH address (Figure 3) used for the chain. The hash address is always set to zero.

Figure 8. WOTS\(^+\) key generation address

Figure 9. FORS key generation address

The type is set to FORS_PRF (i.e., \(\mathit{type} = 6\)) when generating secret values for FORS keys (see Figure 9). The values for the other words in the address are set to the same values as for the FORS_TREE address (Figure 6) used for the same leaf node.

The algorithms in this standard make use of member functions. If a complex data structure (e.g., an \(\mathbf{ADRS}\)) contains a component \(X\), then \(\mathbf{ADRS}\).getX() returns the value of \(X\), and \(\mathbf{ADRS}\).setX(\(Y\)) sets the component \(X\) in \(\mathbf{ADRS}\) to the value held by \(Y\). If a data structure \(s\) contains multiple instances of \(X\), then \(s\).getX(\(i\)) returns the value of the \(i^{\text{th}}\) instance of \(X\) in \(s\). For example, if \(s\) is a FORS signature (Figure 14), then \(s\).getAUTH(\(i\)) returns the authentication path for the \(i^{\text{th}}\) tree.

Whenever the type in an address changes, the final 12 bytes of the address are initialized to zero. The member function \(\mathbf{ADRS}\).setTypeAndClear(\(Y\)) for addresses sets the \(\mathit{type}\) of the \(\mathbf{ADRS}\) to \(Y\) and sets the final 12 bytes of the \(\mathbf{ADRS}\) to zero.\(^{6}\)

Table 1 shows alternative notation for each of the member functions that operates on addresses.

Table 1. Member functions for addresses

If \(X\) is a byte string of length \(n\), then \(X[i]\) for \(i \in \{0, \ldots, n-1\}\) will refer to the \(i^{\text{th}}\) element in the string \(X\). If \(X\) is an array of \(m\) \(n\)-byte strings, then \(X[i]\) for \(i \in \{0, \ldots, m-1\}\) will refer to the \(i^{\text{th}}\) \(n\)-byte string in \(X\), and \(X\) will refer to the \(m \cdot n\)-byte string \(X[0] \parallel X[1] \parallel \ldots X[m-1]\).

A byte string may be interpreted as the big-endian representation of an integer. In such cases, a byte string \(X\) of length \(n\) is converted to the integer

Similarly, an integer \(x\) may be converted to a byte string of length \(n\) by finding coefficients \(x_0, x_1, \ldots x_{n-2}, x_{n-1} \in \{0, \ldots, 255\}\) such that

and then setting the byte string to be \(x_0 x_1 \ldots x_{n-2} x_{n-1}\).

Algorithm 2 is a function that converts a byte string \(X\) of length \(n\) to an integer, and Algorithm 3 is a function that converts an integer \(x\) to a byte string of length \(n\).

For the WOTS\(^+\) and FORS schemes, the messages to be signed need to be split into a sequence of \(b\)-bit strings, where each \(b\)-bit string is interpreted as an integer between \(0\) and \(2^b - 1\).\(^{7}\) This is the equivalent of creating the base-\(2^b\) representation of the message. The \(\mathsf{base\_2^b}\) function (Algorithm 4) takes a byte string \(X\), a bit string length \(b\), and an output length \(\mathit{out\_len}\) as input and returns an array of base-\(2^b\) integers that represent the first \(\mathit{out\_len} \cdot b\) bits of \(X\) if the individual bytes in \(X\) are encoded as 8-bit strings in big-endian bit order. \(X\) must be at least \(\lceil \mathit{out\_len} \cdot b/8 \rceil\) bytes in length. As the value of \(\mathit{bits}\) will never exceed \(b+7\), a \(b+7\)-bit unsigned integer is sufficient to store \(\mathit{total}\) (i.e., \(\mathit{total}\) may be stored as a 32-bit unsigned integer).

This section describes the WOTS+ one-time signature scheme that is a component of SLH-DSA.

WOTS+ uses two parameters. The security parameter \(n\) is the length in bytes of the messages that may be signed as well as the length of the private key elements, public key elements, and signature elements. For the parameter sets specified in this standard, \(n\) may be 16, 24, or 32 (see Table 2). The second parameter \(lg_w\) indicates the number of bits that are encoded by each hash chain that is used.⁸ \(lg_w\) is 4 for all parameter sets in this standard. These parameters are used to compute four additional values:

When \(lg_w = 4\), \(w = 16\), \(len_1 = 2n\), \(len_2 = 3\), and \(len = 2n + 3\).

A WOTS+ private key consists of \(len\) secret values of length \(n\). In SLH-DSA, these are all generated from an \(n\)-byte seed \(\mathbf{SK}\).seed using a PRF. Chains of length \(w\) are then created from the secret values using a chaining function, and the end values from each of the chains are public values. The WOTS+ public key is computed as the hash of these public values. In order to create a signature, the \(8n\)-bit message is first converted into an array of \(len_1\) base-\(w\) integers. A checksum is then computed for this string, and the checksum is converted into an array of \(len_2\) base-\(w\) integers. The signature consists of the appropriate entries from the chains for each of the integers in the message and checksum arrays.

The WOTS+ functions make use of two helper functions: base_2b and chain. The base_2b function (Section 4.4) is used to break the message to be signed and the checksum value into arrays of base-\(w\) integers. The chain function (Algorithm 5) is used to compute the hash chains.

The chain function takes an \(n\)-byte string \(X\) and integers \(s\) and \(i\) (where \(i + s < w\)) as input and returns the result of iterating a hash function \(\mathbf{F}\) on the input \(s\) times, starting from an index of \(i\).9 The chain function also requires as input \(\mathbf{PK}\).seed, which is part of the SLH-DSA public key, and an address \(\mathbf{ADRS}\). The type in \(\mathbf{ADRS}\) must be set to WOTS_HASH, and the layer address, tree address, key pair address, and chain address must be set to the address of the chain being computed. The chain function updates the hash address in \(\mathbf{ADRS}\) with each iteration to specify the current position in the chain prior to \(\mathbf{ADRS}\)’s use in \(\mathbf{F}\).

The wots_pkGen function (Algorithm 6) generates WOTS+ public keys. It takes \(\mathbf{SK}\).seed and \(\mathbf{PK}\).seed from the SLH-DSA private key and an address as input. The type in the address \(\mathbf{ADRS}\) must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS+ public key to be generated.

Lines 4 through 9 in Algorithm 6 generate the public values, as described in Section 5. For each of the 𝑙𝑒𝑛 public values, the corresponding secret value is generated in lines 5 and 6, and the chain function is called to compute the end value of the chain of length 𝑤. Once the 𝑙𝑒𝑛 public values are computed, they are compressed into a single 𝑛-byte value in lines 10 through 13.

A WOTS\(^+\) signature is an array of \(len\) byte strings of length \(n\), as shown in Figure 10. The wots_sign function (Algorithm 7) generates the signature by converting the \(n\)-byte message \(M\)10 into an array of \(len_1\) base-\(w\) integers (line 2). A checksum is computed over \(M\) (lines 3 through 5). The checksum is converted to a byte string, which is then converted into an array of \(len_2\) base-\(w\) integers (lines 6 and 7). The \(len_2\) integers that represent the checksum are appended to the \(len_1\) integers that represent the message (line 7).¹¹ For each of the \(len\) base-\(w\) integers, the signature consists of the corresponding node in one of the hash chains. For each of these integers, lines 12 and 13 compute the secret value for the hash chain, and lines 14 and 15 compute the node in the hash chain that corresponds to the integer. The selected nodes are concatenated to form the WOTS\(^+\) signature.

Figure 10. WOTS\(^+\) signature data format

In addition to the \(n\)-byte message to be signed, wots_sign takes \(\mathbf{SK}\).seed and \(\mathbf{PK}\).seed from the SLH-DSA private key and an address as input. The type in the address \(\mathbf{ADRS}\) must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS\(^+\) key that is used to sign the message.

Generates a WOTS\(^+\) signature on an \(n\)-byte message.

Verifying a WOTS+ signature involves computing a public-key value from a message and signature value. Verification succeeds if the correct public-key value is computed, which is determined by using the computed public-key value along with other information to compute a candidate \(\mathbf{PK}.\mathrm{root}\) value and then comparing that value to the known value of \(\mathbf{PK}.\mathrm{root}\) from the SLH-DSA public key. This section describes wots_pkFromSig (Algorithm 8), a function that computes a candidate WOTS+ public key from a WOTS+ signature and corresponding message.

In addition to an \(n\)-byte message \(M\) and a \(len \cdot n\)-byte signature \(sig\), which is interpreted as an array of \(len\) \(n\)-byte strings, the wots_pkFromSig function takes \(\mathbf{PK}.\mathrm{seed}\) from the SLH-DSA public key and an address as input. The type of the address \(\mathbf{ADRS}\) must be set to WOTS_HASH, and the layer address, tree address, and key pair address must encode the address of the WOTS+ key that was used to sign the message.

Lines 1 through 7 of wots_pkFromSig are the same as lines 1 through 7 of wots_sign (Algorithm 7). Lines 8 through 11 of wots_pkFromSig compute the end nodes for each of the chains using the signature value as the starting point and the message value to determine the number of iterations that need to be performed to get to the end node. Finally, as with lines 10 through 13 of Algorithm 6, the computed public-key values are compressed in lines 12 through 15.

XMSS extends the WOTS+ signature scheme into one that can sign multiple messages. A Merkle tree [13] of height \(h'\) is used to allow \(2^{h'}\) WOTS+ public keys to be authenticated using a single \(n\)-byte XMSS public key, which is the root of the Merkle tree.¹² As each WOTS+ key may be used to sign one message, the XMSS key may be used to sign \(2^{h'}\) messages.

An XMSS signature is \((h' + len) \cdot n\) bytes in length and consists of a WOTS+ signature and an authentication path (see Figure 11). The authentication path is an array of nodes from the Merkle tree — one from each level of the tree, except for the root — that allows the verifier to compute the root of the tree when used in conjunction with the WOTS+ public key that can be computed from the WOTS+ signature.

Figure 11. XMSS signature data format

The xmss_node function (Algorithm 9) computes the nodes of an XMSS tree. The xmss_node function takes as input \(\mathbf{SK}.\mathrm{seed}\) and \(\mathbf{PK}.\mathrm{seed}\) from the SLH-DSA private key; a target node index \(i\), which is the index of the node being computed; a target node height \(z\), which is the height within the Merkle tree of the node being computed; and an address. The address \(\mathbf{ADRS}\) must have the layer address and tree address set to the XMSS tree within which the node is being computed. The target node height and index must satisfy \(z \le h'\) and \(i < 2^{(h'-z)}\).

Each node in an XMSS tree is the root of a subtree, and Algorithm 9 computes the root of the subtree recursively. If the subtree consists of a single leaf node, then the function simply returns the value of the node’s WOTS+ public key (lines 2 through 4). Otherwise, the function computes the roots of the left subtree (line 6) and right subtree (line 7) and hashes them together (lines 8 through 11).

Computes the root of a Merkle subtree of WOTS\(^+\) public keys.

The xmss_sign function (Algorithm 10) creates an XMSS signature on an \(n\)-byte message \(M\)13 by creating an authentication path (lines 1 through 4) and signing \(M\) with the appropriate WOTS\(^+\) key (lines 5 through 7). In addition to \(M\), xmss_sign takes \(\mathbf{SK}.\mathsf{seed}\) and \(\mathbf{PK}.\mathsf{seed}\) from the SLH-DSA private key, an address, and an index as input. The address \(\mathbf{ADRS}\) must have the layer address and tree address set to the XMSS key that is being used to sign the message, and the index \(idx\) must be the index of the WOTS\(^+\) key within the XMSS tree that will be used to sign the message.

The authentication path consists of the sibling nodes of each node that is on the path from the WOTS\(^+\) key used to the root. For example, in Figure 12, if the message is signed with \(K_2\), then \(K_2\), \(n_{1,1}\), and \(n_{2,0}\) are the on path nodes, and the authentication path consists of \(K_3\), \(n_{1,0}\), and \(n_{2,1}\). In line 2 of Algorithm 10, \(\lfloor idx/2^j \rfloor\) is the on path node, and \(\lfloor idx/2^j \rfloor \oplus 1\) is the authentication path node. Line 3 computes the value of the authentication path node.

Generates an XMSS signature.

Figure 12. Merkle hash tree

Verifying an XMSS signature involves computing a public-key value from a message and a signature value. Verification succeeds if the correct public-key value is computed, which is determined by using the computed public-key value along with other information to compute a candidate \(\mathbf{PK}.\mathsf{root}\) value and then comparing that value to the known value of \(\mathbf{PK}.\mathsf{root}\) from the SLH-DSA public key. This section describes xmss_pkFromSig (Algorithm 11), a function that computes a candidate XMSS public key from an XMSS signature and corresponding message.

In addition to an \(n\)-byte message \(M\) and an \((len+h')\cdot n\)-byte signature \(\mathsf{SIG}_{XMSS}\), xmss_pkFromSig takes \(\mathbf{PK}.\mathsf{seed}\) from the SLH-DSA public key, an address, and an index as input. The address \(\mathbf{ADRS}\) must be set to the layer address and tree address of the XMSS key that was used to sign the message, and the index \(idx\) must be the index of the WOTS\(^+\) key within the XMSS tree that was used to sign the message.

Algorithm 11 begins by computing the WOTS\(^+\) public key in lines 1 through 5. The root is then computed in lines 6 through 18. Starting with the leaf node (i.e., the WOTS\(^+\) public key), a node at each level of the tree is computed by hashing together the node computed in the previous iteration with the corresponding authentication path node. In lines 12 and 15, AUTH is interpreted as an array of \(h'\) \(n\)-byte strings.

Computes an XMSS public key from an XMSS signature.

SLH-DSA requires a very large number of WOTS\(^+\) keys to sign FORS public keys. As it would not be feasible for the parameter sets in this standard to have a single XMSS key with so many WOTS\(^+\) keys, SLH-DSA uses a hypertree to sign the FORS keys. As depicted in Figure 1, a hypertree is a tree of XMSS trees. The XMSS keys at the lowest layer are used to sign FORS public keys (Section 8), and the XMSS keys at every other layer are used to sign the XMSS public keys at the layer below.

The hypertree has \(d\) layers of XMSS trees with each XMSS tree being a Merkle tree of height \(h'\), so the total height of the hypertree is \(h = d \cdot h'\) (see Table 2). The top layer (layer \(d - 1\)) is a single XMSS tree, and the public key of this XMSS key pair (i.e., the root of the Merkle tree) is the public key of the hypertree (\(\mathbf{PK}.\mathsf{root}\)). The next layer down has \(2^{h'}\) XMSS trees, and the public key of each of these XMSS keys is signed by one of the \(2^{h'}\) WOTS\(^+\) keys that is part of the top layer’s XMSS key. The lowest layer has \(2^{h-h'}\) XMSS trees, providing \(2^h\) WOTS\(^+\) keys to sign FORS keys.

A hypertree signature is \((h + d \cdot len) \cdot n\) bytes in length and consists of a sequence of \(d\) XMSS signatures, starting with a signature generated using an XMSS key at the lowest layer and ending with a signature generated using the XMSS key at the top layer (see Figure 13).

Figure 13. HT signature data format

In addition to the \(n\)-byte message \(M\),14 the ht_sign function (Algorithm 12) takes as input \(\mathbf{SK}.\mathsf{seed}\) and \(\mathbf{PK}.\mathsf{seed}\) from the SLH-DSA private key, the index of the XMSS tree at the lowest layer that will sign the message \(idx_{tree}\), and the index of the WOTS\(^+\) key within the XMSS tree that will sign the message \(idx_{leaf}\).

Algorithm 12 begins in lines 1 through 3 by signing \(M\) with the specified XMSS key using the WOTS\(^+\) key within that XMSS key specified by \(idx_{leaf}\). The XMSS public key is obtained (line 5 or 14) for each successive layer and signed by the appropriate key at the next higher level (lines 7 through 11).

Generates a hypertree signature.

Hypertree signature verification works by making \(d\) calls to xmss_pkFromSig (Algorithm 11) and comparing the result to the public key of the hypertree.

In addition to the \(n\)-byte message \(M\) and the \((h + d \cdot len) \cdot n\)-byte signature \(\mathsf{SIG}_{HT}\), ht_verify (Algorithm 13) takes as input \(\mathbf{PK}.\mathsf{seed}\) and \(\mathbf{PK}.\mathsf{root}\) from the SLH-DSA public key, the index of the XMSS tree at the lowest layer that signed the message \(idx_{tree}\), and the index of the WOTS\(^+\) key within the XMSS tree that signed the message \(idx_{leaf}\).

At each layer, either the message \(M\) or the computed public key of the XMSS key at the lower layer is provided along with the appropriate XMSS signature to xmss_pkFromSig in order to obtain the layer’s computed XMSS public key. If the computed XMSS public key of the top layer tree is the same as the known hypertree public key, \(\mathbf{PK}.\mathsf{root}\), then verification succeeds.

Verifies a hypertree signature.

FORS is a few-time signature scheme that is used to sign the digests of the actual messages. Unlike WOTS\(^+\), for which forgeries become feasible if a key is used twice [22], the security of a FORS key degrades gradually as the number of signatures increases.

FORS uses two parameters: \(k\) and \(t = 2^a\) (see Table 2). A FORS private key consists of \(k\) sets of \(t\) \(n\)-byte strings, all of which are pseudorandomly generated from the seed \(\mathbf{SK}\).seed. Each of the \(k\) sets is formed into a Merkle tree, and the roots of the trees are hashed together to form the FORS public key. A signature on a \(k \cdot a\)-bit message digest consists of \(k\) elements from the private key, one from each set selected using \(a\) bits of the message digest, along with the authentication paths for each of these elements (see Figure 14).

Figure 14. FORS signature data format

The fors_skGen function (Algorithm 14) generates the \(n\)-byte strings of the FORS private key. The function takes \(\mathbf{SK}\).seed and \(\mathbf{PK}\).seed from the SLH-DSA private key, an address, and an index as input. The \(type\) in the address \(\mathbf{ADRS}\) must be set to FORS_TREE, and the tree address and key pair address must be set to the index of the WOTS\(^+\) key within the XMSS tree that signs the FORS key. The layer address must be set to zero. The index \(idx\) is the index of the FORS secret value within the sets of FORS trees.

The fors_node function (Algorithm 15) computes the nodes of a Merkle tree. It is the same as xmss_node, except that the leaf nodes are the hashes of the FORS secret values instead of WOTS\(^+\) public keys.

The fors_node function takes as input \(\mathbf{SK}\).seed and \(\mathbf{PK}\).seed from the SLH-DSA private key; a target node index \(i\), which is the index of the node being computed; a target node height \(z\), which is the height within the Merkle tree of the node being computed; and an address. The address \(\mathbf{ADRS}\) must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the \(type\) set to FORS_TREE, and the key pair address set to the index of the WOTS\(^+\) key within the XMSS tree that signs the FORS key. The target node height and index must satisfy \(z \le a\) and \(i < k \cdot 2^{(a-z)}\).

Each node in the Merkle tree is the root of a subtree, and Algorithm 15 computes the root of a subtree recursively. If the subtree consists of a single leaf node, then the function simply returns a hash of the node’s private 𝑛-byte string (lines 2 through 5). Otherwise, the function computes the roots of the left subtree (line 7) and right subtree (line 8) and hashes them together (lines 9 through 11).

The fors_sign function (Algorithm 16) signs a \(k \cdot a\)-bit message digest \(md\).15 In addition to the message digest, fors_sign takes \(\mathbf{SK}\).seed and \(\mathbf{PK}\).seed from the SLH-DSA private key and an address as input. The address \(\mathbf{ADRS}\) must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the \(type\) set to FORS_TREE, and the key pair address set to the index of the WOTS+ key within the XMSS tree that signs the FORS key.

The fors_sign function splits \(k \cdot a\) bits of \(md\) into \(k\) \(a\)-bit strings (line 2), each of which is interpreted as an integer between 0 and \(t-1\). Each of these integers is used to select a secret value from one of the \(k\) sets (line 4). For each secret value selected, an authentication path is computed and added to the signature (lines 5 through 9).

Verifying a FORS signature involves computing a public-key value from a message digest and a signature value. Verification succeeds if the correct public-key value is computed, which is determined by verifying the hypertree signature on the computed public-key value using the SLH-DSA public key. This section describes fors_pkFromSig (Algorithm 17), a function that computes a candidate FORS public key from a FORS signature and corresponding message digest.

In addition to a message digest \(md\) and a \(k \cdot (a+1) \cdot n\)-byte signature \(\mathrm{SIG}_{FORS}\), fors_pkFromSig takes \(\mathbf{PK}\).seed from the SLH-DSA public key and an address as input.¹⁶ The address \(\mathbf{ADRS}\) must have the layer address set to zero (since the XMSS tree that signs a FORS key is always at layer 0), the tree address set to the XMSS tree that signs the FORS key, the \(type\) set to FORS_TREE, and the key pair address set to the index of the WOTS\(^+\) key within the XMSS tree that signs the FORS key.

The fors_pkFromSig function begins by computing the roots of each of the \(k\) Merkle trees (lines 2 through 20). As in fors_sign, \(k \cdot a\) bits of the message digest are split into \(k\) \(a\)-bit strings (line 1), each of which is interpreted as an integer between 0 and \(t-1\). The integers are used to determine the locations in the Merkle trees of the secret values from the signature (lines 3 through 5). The hashes of the secret values are computed (line 6), and the hash values are used along with the corresponding authentication paths from the signature to compute the Merkle tree roots (lines 7 through 19). Once all of the Merkle tree roots have been computed, they are hashed together to compute the FORS public key (lines 21 through 24).

SLH-DSA uses the hypertree and the FORS keys to create a stateless hash-based signature scheme. The SLH-DSA private key contains a secret seed value and a secret PRF key. The public key consists of a key identifier \(\mathbf{PK}.\mathrm{seed}\) and the root of the hypertree. A signature is created by hashing the message, using part of the message digest to select a FORS key, signing other bits from the message digest with the FORS key, and generating a hypertree signature for the FORS key. The parameters for SLH-DSA are those specified previously for WOTS+, XMSS, the SLH-DSA hypertree, and FORS (see Table 2).

SLH-DSA uses one additional parameter \(m\), which is the length in bytes of the message digest. It is computed as:

SLH-DSA uses \(h\) bits of the message digest to select a FORS key: \(h - h'\) bits to select an XMSS tree at the lowest layer and \(h'\) bits to select a WOTS+ key and corresponding FORS key from that tree. \(k \cdot a\) bits of the digest are signed by the selected FORS key. While only \(h + k \cdot a\) bits of the message digest are used, implementation is simplified by extracting the necessary bits from a slightly larger digest.

This section describes the functions for SLH-DSA key generation, signature generation, and signature verification. In the functions in this section, where randomness is required, the random values are provided as inputs to the functions. The interfaces specified in this section will be used when testing of SLH-DSA implementations is performed through the Cryptographic Algorithm Validation Program (CAVP). The key generation function in this section may also be used to obtain the assurance of private key possession via regeneration, as described in Section 3.1.

Other than for testing purposes, the interfaces for key generation and signature generation specified in this section should not be made available to applications, as any random values required for key generation and signature generation shall be generated by the cryptographic module. Section 10 provides guidance on the interfaces to be made available to applications.

SLH-DSA public keys contain two elements (see Figure 16). The first is an 𝑛-byte public seed PK.seed, which is used in many hash function calls to provide domain separation between different SLH-DSA key pairs. The second value is the hypertree public key (i.e., the root of the top layer XMSS tree). PK.seed shall be generated using an approved random bit generator (see

Figure 15. SLH-DSA private key

Figure 16. SLH-DSA public key

[14, 15, 16]), where the instantiation of the random bit generator supports at least \(8n\) bits of security strength.

The SLH-DSA private key contains two random, secret \(n\)-byte values (see Figure 15). \(\mathbf{SK}.\mathrm{seed}\) is used to generate all of the WOTS+ and FORS private key elements. \(\mathbf{SK}.\mathrm{prf}\) is used to generate a randomization value for the randomized hashing of the message in SLH-DSA. The private key also includes a copy of the public key. Both \(\mathbf{SK}.\mathrm{seed}\) and \(\mathbf{SK}.\mathrm{prf}\) shall be generated using an approved random bit generator, where the instantiation of the random bit generator supports at least \(8n\) bits of security strength.

Algorithm 18 generates an SLH-DSA key pair. Lines 1 through 3 compute the root of the top layer XMSS tree. Line 4 bundles the three inputs and the computed PK.seed into the private and public keys.

SLH-DSA signing has two variants — “hedged” and deterministic (see Section 9.2) — whose keys should only be used for the generation and verification of hedged and deterministic SLH-DSA digital signatures, respectively.

An SLH-DSA signature consists of a randomization string, a FORS signature, and a hypertree signature, as shown in Figure 17.

Generating an SLH-DSA signature (Algorithm 19) begins by creating an \(m\)-byte message digest (lines 2 through 5). A PRF is used to create a message randomizer (line 3), and it is hashed along with the message to create the digest (line 5). Bits are then extracted from the message digest to be signed by the FORS key (line 6), to select an XMSS tree (lines 7 and 9), and to select a WOTS+ key and corresponding FORS key within that XMSS tree (lines 8 and 10). Next, the FORS signature is computed (lines 11 through 14), and the corresponding FORS public key is obtained (line 16). Finally, the FORS public key is signed (line 17).

Figure 17. SLH-DSA signature data format

Generates an SLH-DSA signature.

The message randomizer may be set in either a non-deterministic or deterministic way, depending on whether \(\mathit{addrnd}\) is provided as an input. For the “hedged” variant, \(\mathit{addrnd}\) is provided as an input, and \(\mathit{opt\_rand}\) is set to \(\mathit{addrnd}\). The hedged variant is the default and should be used on platforms where side-channel attacks are a concern. When using the hedged version, \(\mathit{addrnd}\) shall be an \(n\)-byte random value. While \(\mathit{addrnd}\) should ideally be generated by an approved random bit generator, other methods for generating fresh random values may be used. For the deterministic variant, \(\mathit{addrnd}\) is not provided as an input, and \(\mathit{opt\_rand}\) is set to \(\mathbf{PK}.\mathrm{seed}\), which results in signing being deterministic (i.e., signing the same message twice will result in the same signature). The deterministic variant is available for platforms where a random bit generator is not available.

As with signature generation, SLH-DSA signature verification (Algorithm 20) begins by computing a message digest (line 8) and then extracting \(\mathit{md}\) (line 9), \(\mathit{idx}_{tree}\) (lines 10 and 12), and \(\mathit{idx}_{leaf}\) (lines 11 and 13) from the digest. A candidate FORS public key is then computed (line 17), and the signature on the FORS key is verified (line 18). If this signature verification succeeds, then the correct FORS public key was computed, and the signature SIG on message \(M\) is valid.

Verifies an SLH-DSA signature.

This section provides guidance on the key generation, signature generation, and signature verification functions that should be provided for use by applications. The functions in this section use the functions in Section 9 to implement the underlying SLH-DSA scheme.

Algorithm 21 generates an SLH-DSA key pair. Lines 1 through 3 generate the random values for the private and public keys, and line 7 calls slh_keygen_internal to compute PK.root and return the private and public key. PK.seed, SK.seed, and SK.prf shall be generated using an approved random bit generator (see [14, 15, 16]), where the instantiation of the random bit generator supports at least 8𝑛 bits of security strength.

This section presents two versions of SLH-DSA signature generation: a “pure” version (slh_sign) and a “pre-hash” version (hash_slh_sign). Both versions use slh_sign_internal, but they differ in how the message input to slh_sign_internal is created from the content to be signed. In the pure version, the content is signed by slh_sign_internal along with some domain separation information. In the pre-hash version, a hash of the content is signed by slh_sign_internal along with some domain separation information.

Both versions take the content to be signed, the private key, and a context as input. The pre-hash version also takes as input a hash function or XOF that is to be used to pre-hash the content to be signed. The context string has a maximum length of 255 bytes. By default, the context is the empty string. However, applications may specify the use of a non-empty context string.

The identifier for a signature (e.g., the object identifier [OID]) should indicate whether the signature is a pure signature or a pre-hash signature. In the case of pre-hash signatures, the identifier should also indicate the hash function or XOF used to compute the pre-hash.¹⁷ While a single key pair may be used for both pure and pre-hash signatures, it is recommended that each key pair only be used for one version or the other. If a non-empty context string is to be used, this should either be indicated by the signature’s identifier or the application with which the signature is being used.

If the default hedged variant of slh_sign_internal is used, the \(n\)-byte random value \(addrnd\) shall be generated by the cryptographic module that runs slh_sign_internal. However, \(M'\) in Algorithms 22 and 23 may be constructed outside of the crytographic module. In the case of hash_slh_sign, the hash or XOF of the content to be signed must be computed within a FIPS 140-validated cryptographic module, but it may be a different cryptographic module than the one that runs slh_sign_internal.

In general, the pure version is preferred. However, for some cryptographic modules that generate SLH-DSA signatures, performing lines 3 and 5 of Algorithm 19 may be infeasible if the message \(M\) is large. This may, for example, be the result of the module having limited memory to store the message to be signed. Similarly, for some cryptographic modules that verify SLH-DSA signatures, performing line 8 of Algorithm 20 may be infeasible if the message \(M\) is large. For some use cases, these issues may be addressed by signing a digest of the content rather than signing the content directly.

In many cases where the content to be signed is large, hashing of the content is performed at the application level. For example, in the Cryptographic Message Syntax [23], a digest of the content may be computed, and that digest is signed along with other attributes. In cases in which the content is not hashed at the application level, the pre-hash version of SLH-DSA signing (Section 10.2.2) may be used.

To maintain the same level of security strength when the content is hashed at the application level or when using the pre-hash version of SLH-DSA, the digest that is signed needs to be generated using an approved hash function or XOF (e.g., from FIPS 180-4 [8] or FIPS 202 [6]) that provides at least \(8n\) bits of classical security strength against both collision and second preimage attacks [6, Table 4].¹⁸ Verification of a signature created in this way will require the verify function to generate a digest from the message in the same way for input to the verification function.

Even if it is feasible to compute collisions on the hash functions or XOF used to instantiate \(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_l\), there is believed to be no adverse effect on the security of SLH-DSA.¹⁹ However, if the input to the signing function is a digest of the content, then collisions on the function used to compute the digest can result in forged messages.

In the pure version, the content to be signed is prepended with a one-byte domain separator, one byte that indicates the length of the context string, and the context string. The domain separator, which has a value of zero for pure signing, is included to prevent pre-hash signatures from verifying as pure signatures and vice versa. In the default case in which the context string

is empty, pure signing simply involves prepending two zero bytes to the content to be signed and passing the result to slh_sign_internal along with the private key and, in the case of hedged signing, an 𝑛-byte random value.

In the pre-hash version, the message input to slh_sign_internal is the result of applying either a hash function or a XOF to the content to be signed. The output of the hash function or XOF is prepended by a one-byte domain separator, one byte that indicates the length of the context string, the context string, and the distinguished encoding rules (DER) encoding of the hash function or XOF’s OID. The domain separator has a value of one for pre-hash signing. The DER encoding of the OID includes the tag and length.

Algorithm 23 shows the DER encodings of the OIDs for SHA-256, SHA-512, SHAKE128, and SHAKE256. However, hash_slh_sign may be used with other hash functions or XOFs. SHA-256 and SHAKE128 are only appropriate for use with SLH-DSA parameter sets that are claimed to be in security category 1 (see Section 11).

Algorithms 24 and 25 present the pure and pre-hash versions of SLH-DSA signature verification that correspond to the pure and pre-hash versions of SLH-DSA signature generation in Section 10.2. These functions construct \(M'\) in the same way as Algorithms 22 and 23, respectively, and pass the resulting \(M'\) to slh_verify_internal for verification. As with signature generation, \(M'\) may be constructed outside of the cryptographic module that performs slh_verify_internal. However, in the case of hash_slh_verify, the hash or XOF of the content must be computed within a FIPS 140-validated cryptographic module, which may be a different cryptographic module than the one that performs slh_verify_internal.

The identifier associated with the signature should indicate whether the pure or pre-hash version of signature verification should be used, and in the pre-hash case, the hash function or XOF to use to compute the pre-hash. A non-empty context string should be used in verification if one is specified in the signature’s identifier or by the application with which the signature is being used.

This standard approves 12 parameter sets for use with SLH-DSA. A parameter set consists of parameters for WOTS\(^+\) (\(n\) and \(lg_w\)), XMSS and the SLH-DSA hypertree (\(h\) and \(d\)), and FORS (\(k\) and \(a\)), as well as instantiations for the functions \(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_\ell\).

Table 2 lists the parameter sets that are approved for use.²⁰ Each parameter set name indicates the hash function family (SHA2 or SHAKE) that is used to instantiate the hash functions, the length in bits of the security parameter \(n\), and whether the parameter set was designed to create relatively small signatures (‘s’) or to have relatively fast signature generation (‘f’). There are six sets of values for \(n\), \(lg_w\), \(h\), \(d\), \(k\), and \(a\) that are approved for use.²¹ For each of the six sets of values, the functions \(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_\ell\) may be instantiated using either SHAKE [6] or SHA-2 [8]. For the SHAKE parameter sets, the functions shall be instantiated as specified in Section 11.1. For the SHA2 parameter sets, the functions shall be instantiated as specified in Section 11.2.1 if \(n = 16\) and shall be instantiated as specified in Section 11.2.2 if \(n = 24\) or \(n = 32\).

Table 2. SLH-DSA parameter sets

The 12 parameter sets included in Table 2 were designed to meet certain security strength categories defined by NIST in its original Call for Proposals [25] with respect to existential unforgeability under chosen message attack (EUF-CMA) when each key pair is used to sign at most \(2^{64}\) messages.²² These security strength categories are explained further in SP 800-57, Part 1 [9].

Using this approach, security strength is not described by a single number, such as “128 bits of security.” Instead, each parameter set is claimed to be at least as secure as a generic block cipher with a prescribed key size. More precisely, it is claimed that the computational resources needed to break SLH-DSA are greater than or equal to the computational resources needed to break the block cipher when these computational resources are estimated using any realistic model of computation. Different models of computation can be more or less realistic and, accordingly, lead to more or less accurate estimates of security strength. Some commonly studied models are discussed in [26].

Concretely, the parameter sets with \(n = 16\) are claimed to be in security category 1, the parameter sets with \(n = 24\) are claimed to be in security category 3, and the parameter sets with \(n = 32\) are claimed to be in security category 5 [10]. For additional discussion of the security strength of SLH-DSA, see [10, 27].

Some applications require a property known as message-bound signatures [28, 29], which intuitively requires that it be infeasible for anyone to create a public key and a signature that are valid for two different messages. Signature schemes are not required to have this property under the EUF-CMA security definition used in assigning security categories. In the case of SLH-DSA, the key pair owner could create two messages with the same signature by finding a collision on \(\mathbf{H}_{msg}\). Due to the length of the output of \(\mathbf{H}_{msg}\), finding such a collision would be expected to require fewer computational resources than specified for the parameter sets’ claimed security categories in all cases except SLH-DSA-SHA2-128f and SLH-DSA-SHAKE-128f.²³ Therefore, applications that require message-bound signatures should either take the expected cost of finding collisions on \(\mathbf{H}_{msg}\) into account when choosing an appropriate parameter set or apply a technique (e.g., the BUFF transformation [29]) to obtain the message-bound signatures property.

\(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_\ell\) shall be instantiated as follows for the SLH-DSA-SHAKE-128s, SLH-DSA-SHAKE-128f, SLH-DSA-SHAKE-192s, SLH-DSA-SHAKE-192f, SLH-DSA-SHAKE-256s, and SLH-DSA-SHAKE-256f parameter sets:

In Sections 11.2.1 and 11.2.2, the functions MGF1-SHA-256 and MGF1-SHA-512 are MGF1 from Appendix B.2.1 of RFC 8017 [30], where Hash is SHA-256 or SHA-512, respectively. The functions

HMAC-SHA-256 and HMAC-SHA-512 are the HMAC function from FIPS 198-1 [31, 32], where 𝐻 is SHA-256 or SHA-512, respectively.

The functions in Sections 11.2.1 and 11.2.2 make use of a compressed version of \(\mathbf{ADRS}\) (see Figure 18). A compressed address (\(\mathbf{ADRS}^c\)) is a 22-byte string that is the same as an \(\mathbf{ADRS}\) with the exceptions that the encodings of the layer address and type are reduced to one byte each and the encoding of the tree address is reduced to eight bytes (i.e., \(\mathbf{ADRS}^c = \mathbf{ADRS}[3] \parallel \mathbf{ADRS}[8:16] \parallel \mathbf{ADRS}[19] \parallel \mathbf{ADRS}[20:32]\)). For implementations of the SHA2 parameter sets that store addresses in compressed form (i.e., 22 bytes), the member functions (Section 4.3) are as shown in Table 3 rather than Table 1.

Figure 18. Compressed address (\(\mathbf{ADRS}^c\))

Table 3. Member functions for compressed addresses

\(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_\ell\) shall be instantiated as follows for the SLH-DSA-SHA2-128s and SLH-DSA-SHA2-128f parameter sets:

\(\mathbf{H}_{msg}\), \(\mathbf{PRF}\), \(\mathbf{PRF}_{msg}\), \(\mathbf{F}\), \(\mathbf{H}\), and \(\mathbf{T}_\ell\) shall be instantiated as follows for the SLH-DSA-SHA2-192s, SLH-DSA-SHA2-192f, SLH-DSA-SHA2-256s, and SLH-DSA-SHA2-256f parameter sets:

[1] National Institute of Standards and Technology (2023) Digital Signature Standard (DSS). (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publications (FIPS) NIST FIPS 186-5. https://doi.org/10.6028/NIST.FIPS.186-5.

[2] National Institute of Standards and Technology (2024) Guideline for Using Cryptographic Standards in the Federal Government: Cryptographic Mechanisms. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-175B, Rev.

[3] National Institute of Standards and Technology (2024) Recommendation for Obtaining Assurances for Digital Signature Applications. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-89, Rev. 1. [Forthcoming: will be available at https://csrc.nist.gov/publications].

[4] Aumasson JP, Bernstein DJ, Beullens W, Dobraunig C, Eichlseder M, Fluhrer S, Gazdag SL, Hülsing A, Kampanakis P, Kölbl S, Lange T, Lauridsen MM, Mendel F, Niederhagen R, Rechberger C, Rijneveld J, Schwabe P, Westerbaan B (2020) SPHINCS+ – Submission to the NIST post-quantum project, v.3.

[5] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-56B, Rev. 2. https://doi.org/10.6028/NIST.SP.800-56Br2.

[6] National Institute of Standards and Technology (2015) SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 202. https://doi.org/ 10.6028/NIST.FIPS.202.

[7] Kelsey JM, Chang SjH, Perlner RA (2016) SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-185. https://doi.org/10.6028/NIST.SP.800-185.

[8] National Institute of Standards and Technology (2015) Secure Hash Standard (SHS). (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 180-4. https://doi.org/10.6028/NIST.FIPS.180-4.

[9] National Institute of Standards and Technology (2024) Recommendation for Key Management: Part 1 – General. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 1, Rev 6. [Forthcoming: will be available at https://csrc.nist.gov/publications].

[10] Aumasson JP, Bernstein DJ, Beullens W, Dobraunig C, Eichlseder M, Fluhrer S, Gazdag SL, Hülsing A, Kampanakis P, Kölbl S, Lange T, Lauridsen MM, Mendel F, Niederhagen R, Rechberger C, Rijneveld J, Schwabe P, Westerbaan B (2022) SPHINCS+ – Submission to the NIST post-quantum project, v.3.1. Available at https://sphincs.org/data/sphincs+-r3.1-specification.pdf.

[11] Hülsing A, Butin D, Gazdag SL, Rijneveld J, Mohaisen A (2018) XMSS: eXtended Merkle Signature Scheme. (Internet Research Task Force (IRTF)), IRTF Request for Comments (RFC) 8391. https://doi.org/10.17487/RFC8391.

[12] Cooper DA, Apon D, Dang QH, Davidson MS, Dworkin MJ, Miller CA (2020) Recommendation for Stateful Hash-Based Signature Schemes. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-208. https://doi.org/10.6028/NIST.SP.

800-208.

[13] Merkle RC (1979) Secrecy, Authentication, and Public Key Systems. Ph.D. thesis. Stanford university, .

[14] Barker EB, Kelsey JM (2015) Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1. https://doi.org/10.6028/NIST.SP.800-90Ar1.

[15] Sönmez Turan M, Barker EB, Kelsey JM, McKay KA, Baish ML, Boyle M (2018) Recommendation for the Entropy Sources Used for Random Bit Generation. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90B. https://doi.org/10.6028/NIST.SP.800-90B.

[16] Barker EB, Kelsey JM, McKay KA, Roginsky AL, Sönmez Turan M (2022) Recommendation for Random Bit Generator (RBG) Constructions. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-90C 4pd. https://doi.org/10.6028/NIST.SP.800-90C.4pd.

[17] Kannwischer MJ, Genêt A, Butin D, Krämer J, Buchmann J (2018) Differential Power Analysis of XMSS and SPHINCS. Constructive Side-Channel Analysis and Secure Design, eds Fan J, Gierlichs B (Springer International Publishing, Cham), pp 168–188. https://doi.org/10.1007/978-3-319-89641-0_10.

[18] Castelnovi L, Martinelli A, Prest T (2018) Grafting Trees: A Fault Attack Against the SPHINCS Framework. Post-Quantum Cryptography, eds Lange T, Steinwandt R (Springer International Publishing, Cham), pp 165–184. https://doi.org/10.1007/978-3-319-79063-3_8.

[19] Genêt A, Kannwischer MJ, Pelletier H, McLauchlan A (2018) Practical Fault Injection Attacks on SPHINCS, Cryptology ePrint Archive preprint. https://ia.cr/2018/674.

[20] Amiet D, Leuenberger L, Curiger A, Zbinden P (2020) FPGA-based SPHINCS+ Implementations: Mind the Glitch. 2020 23rd Euromicro Conference on Digital System Design (DSD), pp 229–237. https://doi.org/10.1109/DSD51259.2020.00046.

[21] Genêt A (2023) On Protecting SPHINCS+ Against Fault Attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems 2023(2):80–114. https://doi.org/10.46586/tches.v2023.i2.80-114.

[22] Groot Bruinderink L, Hülsing A (2018) “Oops, I Did It Again” – Security of One-Time Signatures Under Two-Message Attacks. Selected Areas in Cryptography – SAC 2017, eds Adams C, Camenisch J (Springer International Publishing, Cham), pp 299–322. https://doi.org/10.1007/978-3-319-72565-9_15.

1007/978-3-319-72565-9_15.

[23] Housley R (2009) Cryptographic Message Syntax (CMS). (Internet Engineering Task Force (IETF)), IETF Request for Comments (RFC) 5652. https://doi.org/10.17487/RFC5652.

[24] National Institute of Standards and Technology (2024) Recommendation for Additional Stateless Hash-Based Digital Signature Parameter Sets. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-230. [Forthcoming: will be available at https://csrc.nist.gov/publications].

[25] National Institute of Standards and Technology (2016) Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

[26] Alagic G, Apon D, Cooper DA, Dang QH, Dang T, Kelsey JM, Lichtinger J, Liu YK, Miller CA, Moody D, Peralta R, Perlner RA, Robinson A, Smith-Tone D (2022) Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8413-upd1, includes updates as of September 26, 2022. https://doi.org/10.6028/NIST.IR.8413-upd1.

[27] Hülsing A, Kudinov M (2022) Recovering the Tight Security Proof of SPHINCS+. Advances in Cryptology – ASIACRYPT 2022, eds Agrawal S, Lin D (Springer Nature Switzerland, Cham), pp 3–33. https://doi.org/10.1007/978-3-031-22972-5_1.

[28] Stern J, Pointcheval D, Malone-Lee J, Smart NP (2002) Flaws in Applying Proof Methodologies to Signature Schemes. Advances in Cryptology — CRYPTO 2002, ed Yung M (Springer Berlin Heidelberg, Berlin, Heidelberg), pp 93–110. https://doi.org/10.1007/3-540-45708-9_7.

[29] Cremers C, Düzlü S, Fiedler R, Janson C, Fischlin M (2021) BUFFing Signature Schemes Beyond Unforgeability and the Case of Post-Quantum Signatures. 2021 IEEE Symposium on Security and Privacy (SP) (IEEE Computer Society, Los Alamitos, CA, USA), pp 1696–1714. https://doi.org/10.1109/SP40001.2021.00093.

[30] Moriarty K, Kaliski B, Jonsson J, Rusch A (2016) PKCS #1: RSA Cryptography Specifications Version 2.2. (Internet Engineering Task Force (IETF)), IETF request for comments (RFC) 8017. https://doi.org/10.17487/RFC8017.

[31] National Institute of Standards and Technology (2008) The Keyed-Hash Message Authentication Code (HMAC). (Department of Commerce, Washington, DC), Federal Information Processing Standards Publication (FIPS) NIST FIPS 198-1. https://doi.org/10.6028/NIST.FIPS.198-1.

[32] Krawczyk H, Bellare M, Canetti R (1997) HMAC: Keyed-Hashing for Message Authentication. (Internet Engineering Task Force (IETF)), IETF request for comments (RFC) 2104. https: //doi.org/10.17487/RFC2104.

[33] Stern M (2021) Re: Diversity of signature schemes. Available at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/2LEoSpskELs/m/LkUdQ5mKAwAJ.

[34] Antonov S (2022) ROUND 3 OFFICIAL COMMENT: SPHINCS+. Available at https://groups. google.com/a/list.nist.gov/g/pqc-forum/c/FVItvyRea28/m/mGaRi5iZBwAJ.

[35] Perlner R, Kelsey J, Cooper D (2022) Breaking Category Five SPHINCS+ with SHA-256. Post-Quantum Cryptography, eds Cheon JH, Johansson T (Springer International Publishing, Cham), pp 501–522. https://doi.org/10.1007/978-3-031-17234-2_23.

This standard is based on Version 3.1 of the SPHINCS+ specification [10] and contains several minor modifications compared to Version 3 [4], which was submitted at the beginning of round three of the NIST PQC Standardization process:

This standard also differs from the Version 3 specification in its method for extracting bits from the message digest to select a FORS key. This change was made in order to align with the reference implementation that was submitted along with the round three specification. The description of the method for extracting indices for FORS signature generation and verification from the message digest was also changed due to ambiguity in the submitted specification. The method described in this standard is not compatible with the method used in the reference implementation that was submitted along with the round three specification. Additionally, line 6 in both wots_sign and wots_pkFromSig were changed to match the reference implementation, as the pseudocode in [10, 4] will sometimes shift \(csum\) by the incorrect amount when \(lg_w\) is not 4.

This standard approves the use of only 12 of the 36 parameter sets defined in [10, 4]. As specified in Section 11, only the ‘simple’ instances of the SHA2 and SHAKE parameter sets are approved.

The differences from Version 3 of the SPHINCS+ specification described in Appendix A were included in the draft version of this standard (FIPS 205 ipd) that was posted on August 24, 2023. Based on comments that were submitted on FIPS 205 ipd, the SLH-DSA signature generation and verification functions were modified to include domain separation cases in which the message is signed directly and in which a digest of the message is signed. The changes were made by modifying the inputs to the signing and verification functions (see Algorithms 22, 23, 24, and 25).