In WOTS+ — as described in section 3 of RFC 8391 — public keys, private keys and signatures all consist of $len$ strings with $n$ bytes each, where $len, n \in \mathbb{N}$. Is it safe to use the hash of the concatenation of all $len$ strings as a short public key? Since you just need the message and the signature to compute the (long) public key, the process would be exactly as described in section 3.1.6 of the RFC, except the verifier would need to take an extra hash at the end and compare the result with the short public key. I'm specially puzzled why that possibility isn't mentioned in the document. I suspect they were more worried with the size of the signature than the size of the public key. Is that plausible?

  • 1
    $\begingroup$ According to this Wikipedia article, this optimization can be indeed applied, but will double the signature size, as you need to reveal unused hashes. The thing is, this is true for Lamport, but on WOTS, there is no such a thing as unused hashes. I wonder if the article is incorrect? $\endgroup$
    – MaiaVictor
    Jul 9 at 0:21

This is indeed possible. The L-trees in 4.1.5 of the RFC do exactly that in a way that prevents the requirement of a collision-resistant hash function. It is only described there, as the "hash function" is largely the same as the Merkle tree itself. So, you can simply use the L-tree as part of WOTS to compress the public key to an n byte value (for the n used in the RFC). If you want to use a single hash function call, you can either look into the way this is done in SPHINCS+ where they introduce tweakable hash functions (essentially a generalization of the concept of using pseudorandom bitmasks and keys in a hash function) or you can use a single call to a 2n byte collision resistant hash function. In the latter case the length has to be 2n as n is chosen to only protect against (2nd) preimage attacks. Especially, it is not sufficiently long to prevent birthday attacks.

  • $\begingroup$ I don't see why birthday attacks are relevant, as the attacker who is trying to generate a forgery doesn't get the option of picking data that goes into both sides. Now, multitarget collision attacks (where the attacker works on several public keys at once, and wins if he can generate forgeries to any one) are relevant; however that can be addressed cheaper than a 2n hash function $\endgroup$
    – poncho
    Jul 15 at 11:39
  • $\begingroup$ Well, you do not get a reduction from anything weaker than collision resistance if you just use a blank hash function. In the ROM I agree you can get down to (multi-target) second preimage attacks $\endgroup$
    – mephisto
    Jul 15 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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