# How is SPHINCS Hash-based signature “stateless”?

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

• Just a note: You can format your posts here with mathjax if you like. It can help make something like σ=f_Sx0(α),V_x0,auth_x0 look much nicer and more readable. – Ella Rose May 28 '19 at 16:25
• You're right... let me figure out how to do so.. – Mona May 28 '19 at 16:40

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".

• Thank you very much for clearing this. I was confused because in the third age of Sphincs paper,they mentioned Goldreich's binary certification tree, and I thought that's what they did. – Mona May 28 '19 at 17:19
• But the when Sphincs signs a message with one of the HORST at the bottom layer, how do they generate the authentication paths of all above trees, i think they generate all the WOTS+ keys from G(1^n) and i think it is deterministic? – Mona May 28 '19 at 17:22
• @Mona: yes, all the WOTS+ keys (for both the bottom level Merkle trees, and the intermediate Merkle trees) are all deterministic, based on the secret seed (which is the private key) – poncho May 28 '19 at 17:28
• Indeed, thank you very much for your big help – Mona May 28 '19 at 17:30