1
$\begingroup$

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?

Here is the diagram from SPHINCS+ paper showing the hypertree

$\endgroup$

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Andrew
    Commented Nov 14, 2022 at 11:32
  • $\begingroup$ I've added an extra section hopefully answering your questions. $\endgroup$
    – Daniel S
    Commented Nov 14, 2022 at 16:58
  • $\begingroup$ Thank you its clear now :) $\endgroup$
    – Andrew
    Commented Nov 15, 2022 at 4:51
  • $\begingroup$ 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) $\endgroup$
    – Andrew
    Commented Nov 15, 2022 at 9:46
  • $\begingroup$ I'll try and say something on your other question later today. $\endgroup$
    – Daniel S
    Commented Nov 15, 2022 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.