Join Log in
Score:3
Rígille S. B. Menezes avatar Crypto

Making WOTS+ public keys shorter

cn flag
Rígille S. B. Menezes

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?

74
1 + 1
ca flag
MaiaVictor
According to [this Wikipedia article](https://en.wikipedia.org/wiki/Lamport_signature#Short_public_key), 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?
1
Reply
Score:1
avatar Crypto
in flag
mephisto

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.

0 + 2
poncho avatar
my flag
poncho
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
0
Reply
in flag
mephisto
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
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.