How does signing with FORS work in SPHINCS+?

Andrew

11/12/23, 5:23 AM

I was reading the SPHINCS+ paper and got confused in the signing with FORS (forest of random subsets) part.

I understand how we can sign a message using FORS but I couldn't understand how we choose the corresponding WOTS+ key to sign the FORS root node with.

If we are going to choose only one of the XMSS trees in the bottom layer, does that mean the remaining trees are going to be redundant?

153

1 + 0

post-quantum-cryptography

one-time-signature

hash-based

Score:1

Crypto

Daniel S

11/12/23, 12:37 PM

If by redundant you mean not relevant to the signature being verified, then yes. If by redundant you mean unusable for other signatures, then no.

All of the square values in the tree represent WOTS+ public keys that we would happily make public, but this would be an unnecessarily large transmission and storage burden to share, especially for clients who only want to verify a few signatures. Likewise we would happily reveal the circular nodes which simply compress our proof of knowledge of the values directly below them at the time that the public key was produced. Revealing the private value necessary to produce a square node at the base of the tree, means that square node should never be chosen for two $m$ values, but revealing a node value is information that we would be happy to reveal anyway and does not compromise the use of the private data that produces other nodes at the base of the tree.

ETA 20221114: In answer to questions in the comments:

WOTS+ private signing keys are generated using a pseudo-random function applied to a secret seed which is securely stored by the signer. The WOTS+ secret keys can then be reconstructed as required by re-applying the PRF to the seed. See section 3.5 The SPHINCS+ key pair.
The WOTS+ public key will be calculated by the verifier as part of the signature verification process and it should only be possible for someone in possession of the WOTS+ signing key to generate this signature.
The index of the node chosen to sign the message is chosen pseudo-randomly by making both the message digest and index be components of the output of a hash of a randomiser, public key values and message: $(MD||\mathrm{index})=H(\mathrm{randomiser},\mathrm{public\ key\ values}, M)$. See section 3.5. ** The SPHINCS+ signature** second paragraph.

+ 6

Andrew

11/14/23, 11:32 AM

Thank you so much for the detailed explanation! I want to make sure my understanding so if WOTS+ public keys are stored in the square nodes, where are the WOTS+ private keys are stored? When we sign the root node of the tree below it, do we use the WOTS+ public key to sign it? Another question is that when we choose the FTS node to sign the message do we randomly choose it?

Daniel S

11/14/23, 4:58 PM

I've added an extra section hopefully answering your questions.

Andrew

11/15/23, 4:51 AM

Thank you its clear now :)

Andrew

11/15/23, 9:46 AM

I have one more question if you don't mind. I am very confused with the tweakable hash function. I understood that we use it to compress the WOTS+ public keys. So by doing that, we use the node address information as well so that we won't generate the same hash function output for two nodes that has the same data. Am I right with this or is there anything more to that for the tweakable hash functions? (couldn't clearly understand the math part)

Daniel S

11/15/23, 9:49 AM

I'll try and say something on your other question later today.

Andrew

11/15/23, 1:01 PM

OK, thank you very much.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How does signing with FORS work in SPHINCS+?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.