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?
$\begingroup$
$\endgroup$
1
-
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$– MaiaVictorCommented Jul 9, 2021 at 0:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$– ponchoCommented Jul 15, 2021 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$– mephistoCommented Jul 15, 2021 at 12:01