0
$\begingroup$

The length of WOTS+ private key is an array of length "len" of n-Byte strings. Meaning, for w=16 and n=32, the len is 72. So the WOTS+ max length of the private key is 72, meaning only 72 messages can be signed.

Now my problem is, when you read about XMSS Keys, it says that the private key is defined by 2^h OTS private keys, h is usually 20 so 2^20 keys. What do I generate first? With the first definition I can only have 72 private WOTS+ keys and the second one extends it to over a milion.

Do I have to ignore the fact of array[len] n-Byte private keys and generate just 2^h WOTS+ keys using the chaining function?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Do I have to ignore the fact of array[len] n-Byte private keys and generate just 2^h WOTS+ keys using the chaining function?

In practice, what we do is follow the recommendations of section 4.1.11 of RFC 8391, and generate all the WOTS+ private keys dynamically as needed from a single secret seed.

The RFC recommends a two step process; you use the PRF function (with the ADR with the index of the WOTS+ key you're retrieving) to generate an n-byte value they denote as S_ots; then for each WOTS+ chain, you run the PRF function again on the S_ots value to generate the starting value for that chain.

And, if you're implementing XMSS^MT, you'll also want to pay attention to section 4.2.6, which adds a third layer to distinguish between different XMSS trees. I suspect that step isn't needed (the ADR structure already distinguishes that); on the other hand, it's fairly cheap to follow the RFC's recommendations.

Improve this answer
$\endgroup$
10
  • $\begingroup$ thanks, btw. you meant RFC 8391 right? Dont I MUST generate all WOTS+ private keys before I start computing the tree? If I dont generate 2^h WOTS+keys, I cant create the L-Trees leaves, which will create leaves for the merkle tree and so on. The XMSS root, the xmss public key, is the hash value of last two nodes combined, and these nodes are made each of the hashes of half wots+ keys. $\endgroup$
    – user86443
    Commented Jan 26, 2021 at 19:11
  • $\begingroup$ in other words, I still need to compute the whole merkle tree to create PK of XMSS, then just save all nodes hashes in order to put them into the authpath, so the verifier doesnt have to recompute the whole tree, thus making veryfing faster than signing $\endgroup$
    – user86443
    Commented Jan 26, 2021 at 19:36
  • $\begingroup$ the "len" of WOTS+ becomes 2^h, length of XMSS key $\endgroup$
    – user86443
    Commented Jan 26, 2021 at 19:42
  • $\begingroup$ "I still need to compute the whole merkle tree to create PK of XMSS"; yes, you do (but you need to compute to top XMSS tree in XMSS^MT); however you don't have to save all the node hashes; you can save a couple, and recompute the rest on the fly using a Merkle tree traversal algorithm. And, yes, I meant RFC 8391; I must have looked at the wrong window when writing the RFC number... $\endgroup$
    – poncho
    Commented Jan 26, 2021 at 19:46
  • $\begingroup$ I just wonder, why does one need a public SEED for? You create random values using prf_SEED(ADRS), which you then put into the public key. What does the verifier need the SEED for? He cant generate the same values, since prf_seed() generates random values, or does it generate the same values depending on the input? Is the public SEED also the key for hash functions? $\endgroup$
    – user86443
    Commented Jan 26, 2021 at 20:03

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.