In the previous article, we introduced several hashbased postquantum digital signatures. Now we move on to discuss more recent digital signatures, among which SPHINCS+ is included in the third round of NIST recommended signature schemes.
Hash to Obtain Random Subset
Hash to Obtain Random Subset (HORS) is an FTS (fewtimes signature) signature algorithm. An FTS algorithm can be used to sign messages for a few times, each time it is used, some information is exposed, reducing the key’s security.
HORS divides a hashed message into chunks. If a message is divided into
As a result, we can generate
In the above example, a message
A HORS signature will be computed as follows:
 Compute the decimal values of each message chunk from the message digest. For example, the decimal value of the first chunk is 5.
 Compute the signature of the
th chunk using its decimal value. In the above example, the signature of the first chunk is .  Generate signature of this message with
To verify the signature, hash the signature chunks one time and check whether the results are consistent with the public keys.
HORS Tree
It’s not difficult to see that HORS public keys are very long. HORS Tree (HORST) was introduced in the SPHINCS paper to reduce HORS public key size with Merkle tree style technique.
Like HORS, HORST also divides the message into groups. We will use the same example as in HORS — generate
Bitmasks are used in HORST. Before applying the hash function, the two values will XOR with their corresponding bitmasks. Each level of the tree has two diferent bitmask values
To sign a message, HORST will select the corresponding private key based on the decimal value of each message chunk — same as in HORS. Then an authentication path
Intermediate nodes can also serve as authentication roots of HORST. In the example below,
Let’s denote the authentication nodes as
The lower on the tree we move
Lastly, when verifying a signature, the verifier computes the hash based on
SPHINCS
Now based on HORST and WOTS+, a new stateless hashbased signature algorithm called SPHINCS can be constructed.
Note that although previous key management schemes like WOTS+ and HORST can manage large numbers of keys, keys must be pregenerated in order to compute the Merkle root. This limits the number of keys that can be managed. SPHINCS is able to manage a significantly larger number of keys without precomputing all leaves by leveraging two techniques:
 Hypertree
 Random key path addressing scheme
A hypertree is a tree of trees. Assume the height of the hypertree is
Given such a large structure, one may ask two questions: (1) what are all these trees used for, and (2) what does an authentication path look like across the hypertree?
One important thing to know first is that the hypertree described by SPHINCS is a conceptual structure — we don’t have to build all the subtrees on the hypertree at once. Trees covering a specific path on the hypertree need to be generated only when signing a message.
At the very bottom level of the SPHINCS hypertree, there is a level of HORS trees which contain private keys to sign messages. When there is a message, SPHINCS selects a HORST to sign the message, and then generates a signature
The level above HORST — level
You might have noticed the following features of hypertree:
 There is only one tree on level
which is the top tree.  There are
trees on level , and the root of the tree in level will be signed by the WOTS+ private key of the tree on level .
It means that WOTS+ trees and HORS trees are independent from each other, even though they are selected on the same path to authenticate a signature. This useful feature helps avoid precomputing all trees during key generation, hence allowing a really big number of keys to be managed under a single SPHINCS public key. The large key space also makes SPHINCS practically stateless signature scheme.
As we mentioned earlier, SPHINCS only identifies specific paths in the hypertree when signing a message. You may ask, how is this path generated?
SPHINCS has an addressing scheme to locate the WOTS+ public keys in the hypertree. The address format is as follows: which level of hypertree, which tree on this level, which leaf from this tree. With this format, we can uniquely determine the WOTS+ public key’s location of each level of the hypertree.
Generate SPHINCS private key
When signing a message, first generate SPHINCS private key and public key. The private key consists of three parts:
(nbits) and (nbits). These two keys are generated by a PRG function. will be used to generate random seeds of HORST and WOTS+ priate keys. will be used to generate an unpredictable index and the hash of the message.  bitmasks
: Bitmasks are used in several primitives — FORS, HORST, Ltree, hypertree. FORS needs bitmasks, HORST needs bitmasks, and Ltree needs bitmasks. The hypertree needs bitmasks where .
Generate SPHINCS public key
The SPHINCS public key is the root of hypertree, which is a public key of the top level WOTS+ root. The address of the toplevel trees’ leaves (level
First, generate the seed
We use
Sign a message
Now we are ready to create SPHINCS signatures. To sign a message, first create a HORST, and then generate a specific SPHINCS hypertree path.
In order to generate the HORST key, first determine the address of the HORST key pair; then generate the corresponding random seed; then create HORST keys through the seed. Lastly use the HORST keys to sign message and generate all WOTS+ signatures in the same way: Address → seed → key pair → signature.
Here comes the details:

Generate two random nbits
and by  compute the message digest
 compute HORST address
and
 compute the message digest

Generate HORST key pair and HOTST signature
 generate HORST key pair seed by
 generate HORST signature and public key by
 generate HORST key pair seed by

Generate all WOTS+ signatures along the SPHINCS path
 compute all addresses of WOTS+ in the path
where is the level and  compute all the seeds
 generate WOTS+ signature
by where is the root of the tree of level. Also we need to generate the authentication path of corresponding WOTS+ public key.
 compute all addresses of WOTS+ in the path
The SPHINCS signature is
Verify signature
The verifier follows the following three steps to verify

check HORST signature:
 compute message digest
 verify
: , reject if the result doesn’t equal auth path root of HORST.
 compute message digest

check all WOTS+ signatures:
 check
by ;  check the
by where  reject if any one of the WOTS+ signatures cannot be validated.
 check

On hypertree level
, the verifier gets the root of the hypertree. If the , the is validated, otherwise reject.
Although the whole signature scheme looks complicated, the idea is simple: hypertree allows a much bigger key space without the need to precomputing all keys and intermediary nodes.
With an understanding of SPHINCS, we are now introducing the stateofart hashbased signature scheme — SPHINCS+. But before moving into SPHINCS+, we need to introduce one more primitive.
Forest of Random Subsets
Forest of Random Subsets (FORS) is an improvement of HORST.
Like HORST, it first splits the hashed message into many chunks. The private keys will be hashed and become leaves to construct a tree. The difference is, each tree has its own root. The FORS public key is simply the hash of the
When signing a message,
In the above example, each private key has a corresponding authentication path. The signature is
To verify a signature，the verifier computes all roots from
SPHINCS+
Among the latest hashbased signature schemes, SPHINCS+ has great advantages in speed, security and signature size. More specifically, SPHINCS+ is a signature framework rather than a single signature scheme, because there are many parameters which provide flexibility, allowing users to make applicationspecific tradeoffs in terms of signature size, signature speed, required number of signatures, and required security level.
In general, the ideas of SPHINCS+and SPHINCS are quite similar, but there are some differences in details:
 SPHINCS uses HORST to sign messages, SPHINCS+ uses the FORS to sign messages.
 Although the selection of leaf nodes by SPHINCS+ is random, it uses a publicly verifiable method.
 SPHINCS+ introduce a tweakable hash functions to further ensure security.
With an understanding of SPHINCS, we can directly explain the key generation of SPHINCS+ which is similar to SPHINCS.
The public key consists of two nbit values: the toplevel root node
In addition, the private key consists of two more nbit random seeds:
Generate signature
SPHINCS+ signature consists of a FORS signature on a digest of the message, a WOTS+ signature on the corresponding FORS public key, and a series of authentication paths and WOTS+ signatures to authenticate that WOTS+ public key. However, SPHINCS+ differs from the original SPHINCS in how the message digest is computed and how leaves are selected.
 SPHINCS+ pseudorandomly generates a randomizer
based on the message and . can optionally be made nondeterministic by adding additional randomness . This may counteract sidechannel attacks that rely on collecting several traces for the same computation. Note that setting this value to allzero string (or using a lowentropy value) does not negatively affect the pseudoran domness of . Here which is part of the signature.  Using R, we then derive the index of the leaf node that is to be used, as well as the message digest
where means message digest and means leaf index. is an additional keyed hash function to compress the message.
In contrast to SPHINCS, this method of selecting the index is publicly verifiable, preventing an attacker from freely selecting a seemingly random index and combining it with a message of their choice. Crucially, this counteracts multitarget attacks on the fewtime signature scheme. As the index can now be computed by the verifier, it is no longer included in the signature.
The SPHINCS+ signature is
To verify
 Check the FORS signature:
 Generate message digest
and leaf index using the same operation as in signing.  Check the signature by
.  To verify the signer’s
, verifier can also compute and compare it.
 Generate message digest
 Same as SPHINCS, check the WOTS+ signatures of each level in SPHINCS+.
Will hashbased signature schemes be actually useful?
As mentioned in the previous part of this article, there are several hashbased signature schemes that we haven’t included. However, by introducing Lamport, WOTS, XMSS, WOTS+, HORST, SPHINCS, and SPHINCS+, we have outlined the methodology and startofart developments of hashbased signature schemes.
It might seem odd for hashbased signature schemes to generate bags of private key strings, but this is a great advantage at the same time — the security assumption of hashbased signature schemes only rely on hash functions.
Other than hashbased signature schemes, there are a few other paradigms to create postquantum signatures (read this article for more benchmarks). We will cover some important nonhash based quantumsafe signature schemes soon.