How is SPHINCS Hash-based signature "stateless"?

Question

I really hope someone can help me with these questions related to SPHINCS.

I am trying to understand the concept of “stateless” vs. “stateful” signature scheme which is the basis of SPHINCS. I went to read Chapter 6.4 of Goldreich’s Foundations of Cryptography, Volume 2. In page 546, image attached with this question, he gives a small example of one parent node x authenticating two children nodes, x_0 and x_1.

Here are my questions:

Q1: node x generates (S_x, V_x) pair where S_x is the Secret Key and V_x is the Public Key. Then node x generates two additional pairs (S_x0,V_x0 ) and (S_x1,V_x1) for nodes x_0 and x_1, respectively. Is there is any relationship between S_x and S_x0,S_x1 other than the fact that they use the same G(1^n) ?

Q2: the public key is only V_x?

Q3: signing only occurs with children nodes. Say I sign α with S_x0, thus the signature is going to be σ=f_Sx0(α),V_x0,auth_x0 where auth_x0= f_Sx(V_x0) ?

Q4: In SPHINCS, can we assume that all private keys are also generated with the same G(1^n) ? and thus we are always going to generate the same private keys given the same seed? Thus the “stateless” came from?

Thank you very much

Answer 1

I don't have Goldreich in front of me, however it would appear that he is discussing something rather different from a Merkle tree (at least, as it appears in a hash based signature method).

In those Merkle trees, the trees are built bottom-up, not top-down. That is, the top nodes don't define the values that the child nodes hold; instead, the top node value is a (oneway) function of the child nodes. In addition, the value that a node has is potentially public (that is, we don't mind if someone learns it); there is no secret component to it. The only secrets are the private keys to the one time (or few time) signatures at the bottom of each Merkle tree.

As for the difference between stateful and stateless based based signature methods:

• Stateful schemes have a Merkle tree (or tree of trees) with a number of one-time signatures at the bottom; each one-time signature can be used (you guessed it) once; hence the signer needs to keep track of which ones he has used; that is, when he uses a one-time signature to sign a message, he must update his state.

• Stateless schemes (such as Sphincs) has a large tree-of-trees; but at the bottom, they have a number of few time signatures (Sphincs uses HORST); each such few time signature can sign several messages. So, when Sphincs signs a message, the signer picks a random few-time-signature, uses that to sign the message, and then authenticates that through the Merkle trees up to the root (which is the public key). Since we are using a few-time signature, we don't mind if we pick the same few-time signature multiple times on occasion; the few time signature scheme can handle it. And, since we don't need to update any state when generating a signature, this is considered "stateless".

Answer 2

I modified a picture from "The SPHINCS+ Signature Framework. In 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ’19)." according to my personal understanding.

Hope this can help clarifying the structure of SPHINCS+.

I think Goldreich’s tree structure was mentioned to explain the "layers of trees" in SPHINCS scheme. Although each tree in the picture is a Merkle tree (i.e. Hash relation between nodes to generate the root), the trees between layers are connected not by Hashes but by signature, i.e. the root of the lower layer tree is signed by some leaf node (which corresponds to a WOTS key pair) of an upper layer tree. In this way, generating the authentication path wouldn't cost so much as using a single Merkle tree. As you can see, by applying this layered structure, authentication path's (hash) caculation only involve a part of sub-trees rather than all the sub-trees in the picture.

As for how SPHINCS+ achieve "stateless", it uses both the message to be signed and public key as input of PRF, thus deterministically decide which leaf node of which tree in the bottom layer to be used (as a FTS key to sign the message). Since the collision probability that different messages coincidentally point to the same leaf node in the same tree is made negligible, and also even if this happens, FTS can still maintain security to some extent, SPHINCS+ claims its "statelessness" in this PRF generated way (needn't to keep a counter variable along with signature to memerize how many keys have already been used and which to use next, which is called "statefull").