SPHINCS+: stateless hash-based digital signature
Introduction
The Forest Of Random Subset (FORS) scheme constitutes the last element needed in order to describe the complete structure of the SPHINCS+ digital signature algorithm, selected at the end of the third round of the NIST competition.
The use of FORS makes it possible to turn SPHINCS+ into a stateless digital signature algorithm, thus overcoming the main problems of other hash-based signatures such as XMSS and LMS. After describing the inner workings of FORS, we will focus on the general structure of SPHINCS+, underlining how the joint use of the cryptographic structures introduced in the two previous articles of this series allows us to build the scheme that is being standardized by NIST.
FORS
The final piece in the definition of SPHINCS+ is hence constituted by the Forest Of Random Subsets (FORS) signature. FORS is a Few Time Signature (FTS), which is a scheme that allows one to sign a limited number of different messages with the same private key. When the number of signatures grows, the scheme undergoes a gradual decrease in its security but without incurring the catastrophic and abrupt security loss that happens whenever two or more messages are signed using a one-time signature like WOTS+.
What follows is a high-level description of FORS.
In this scheme we have to define the parameters k, t=2^a and n in order to be able to sign ka-bit strings. The private key is composed of k sets of t strings of length n bytes, generated starting from a single secret seed. The public key is obtained by computing the digest, using a hash function, of all the kt secret strings and then using them as leaves of k Merkle Trees of height a. We recall that a generic node of the k trees is computed by hashing the concatenation of its children. Once the k roots of the resulting Merkle Trees are computed, the public key of FORS is obtained as the hash of their concatenation.
One example is depicted below where the case k=3 and t=2^2 is shown, in which we need 3 Merkle Trees of height 2. The private key is constituted by sk_{0,0},\dots,sk_{2,3}, while the public key is f\!pk.
Given a ka-bit message, we decompose in k a-bit strings l_0,\dots, l_{k-1}, each one interpreted as an integer in [0,t). The message signature is obtained by concatenating the k strings sk_{0,l_0},sk_{1,l_1},\dots, sk_{k,l_{k-1}}, one from each Merkle Tree, and the authentication paths [1] needed to recover the roots r_i and hence the public key f\!pk. In the following image, we highlight the authentication paths of the signature of the message 11\,01\,10, with k=3 and t=2^2.
We can now analyze more in detail the aspects that make FORS a few-time signature and that allow to sign more than one message with the same private key while maintaining a high level of security.
In most one-time signatures, a significant part of the signer private key has to be published every time a message is signed: a clear example in this context is the Lamport OTS [2], where half of the private key is published, thus rendering safely reusing it to sign a second message impossible. Let us note that even in FORS, every time a signature is computed, some parts of the private key have to be published: the main difference is that the information leakage is extremely lower compared to the one of Lamport signatures.
Looking at the picture above it is easy to see that computing a signature implies that a single secret string of each one of the three Merkle Trees has to be published (sk_{0,3}, sk_{1,1}, sk_{2,2} in this particular case). Given that in the FORS instances used inside SPHINCS+ t is usually between 2^6 and 2^{14}, it is clear that a signature, by publishing only a string from each one of the k Merkle Trees, is not enough to compromise the security of subsequent signatures made using the same private key. In fact, an attacker can forge a signature of a message, without knowing the private key, only if the digest of the message is composed by a-bit blocks that correspond to strings that have already been published, but this is extremely unlikely if he only knows a limited number of signatures. It should be noted, however, that the probability of an attacker being able to find a message for which it can forge a signature increases with the number of signatures made with the same private key.
The structure of FORS guarantees high security in the case of “weak messages”, which are messages where many digest blocks are equal. This could reduce the security of other FTS such as Hash to Obtain Random Subset (HORS), where instead of k Merkle Trees with t leaves we only use one. Furthermore, in FORS care is put towards the randomization of the message hash, so to prevent an attacker from building ad-hoc messages that could maximize the information leakage deriving from each signature.
SPHINCS+
Introducing FORS frees us from having to keep a state of the signatures that were made, as it has to be done in XMSS, and is thus fundamental in the design of stateless schemes required by the post-quantum NIST competition.
We can now define the SPHINCS+ signature algorithm as the combination of the main “ingredients” introduced in the last three articles of this series.
Given a message that has to be signed, this can be compressed into a ka-bit string using a hash function in accordance with the FORS parameters. Signing the digest, instead of the message itself, is needed in order to guarantee the security of FORS. In addition to that, this also has some advantages concerning the performance and it allows us to improve the signature dimension since it guarantees that the object that is signed has a constant length. The digest is then signed using FORS, while the corresponding public key f\!pk is authenticated by an XMSSMT signature, introduced in the previous blog post. We shall recall that the XMSSMT signature has a modular structure. More in detail, in the XMSSMT scheme the element that has to be signed is given in input to a WOTS+ scheme, whose public key is a leaf of a Merkle Tree. Such Merkle Tree is then part of a HyperTree structure, where multiple Merkle Trees are distributed in a certain number of levels and the root of a tree is signed by a leaf of a higher level tree. In the figure below, taken from [3], we can see a high-level representation of the complete scheme.
The SPHINCS+ private key is constituted by the seed used to generate the FORS keys signing the message digest and the WOTS+ keys forming the leaves of the Merkle Trees. The public key is the root of the HyperTree. The public and private keys are extremely small, and this surely represents a significant advantage of this algorithm.
A SPHINCS+ signature of a message is obtained as the concatenation of the FORS signature, the WOTS+ signatures of the FORS public key and the roots of the involved Merkle Trees, and the corresponding authentication paths.
Performance
The big signature size makes SPHINCS+ unsuitable for contexts with stringent memory or bandwidth requirements. Even when considering more general use case scenarios it is usually advisable to use some other schemes, such as CRYSTALS-Dilithium and Falcon, that for the same security level can guarantee signatures one order of magnitude smaller, as it is shown in the following graph.
Even though the big signature size limits its use in several scenarios, SPHINCS+ represents an extremely conservative choice because its security is entirely based on hash function properties. This could make SPHINCS+ the best choice in high-security scenarios where performance is not the main priority. Furthermore, in the context of hash-based signatures, SPHINCS+ represents an interesting option thanks to its stateless nature. In many hash-based stateful schemes, such as XMSS and LMS, messages are signed using an OTS, thus requiring to keep a state to avoid reusing the same secret key twice. In SPHINCS+, messages are signed using the FORS FTS. This implies that, if the number of signatures made with the same SPHINCS+ private key remains under a certain threshold (usually 2^{64}), the probability of reusing the same FORS private key several times that makes it insecure is negligible. Thus, it is possible to avoid the problems highlighted in a previous article of this series, concerning the need to keep a state of the computed signatures to avoid the reuse of the same private key.
[1] The set of necessary and sufficient nodes is needed to compute the roots of the trees, starting from the k secret strings.
[2] Leslie Lamport, Constructing Digital Signatures from a One Way Function, Rapp. tecn. CSL-98, 1979.
[3] Andreas Hülsing e Mikhail Kudinov, Recovering the tight security proof of SP HIN CS+, Cryptology ePrint Archive, Paper 2022/346, 2022.
This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.
For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.
The authors
Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at the end of 2020 focusing in particular on issues related to quantum technologies.
Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.