Lamport signature: How many signatures are need to forge a signature?

Question

Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never publish or use. Preferably she should delete them; otherwise, others gaining access to them would later be able to create false signatures.

If Lamport's signature scheme would be used incorrectly, say you would use it more than once. How many signatures of distinct messages would you need to forge a signature?

I'm thinking if you have one signature and then the "opposite" message (not really message but the message's hash sum) so every 0 in the first message is a 1 and 1 is 0. If you had those two signatures you would have everything you needed from Alice's private key.

But that's probably not realistic to think that you get exactly those two messages. Is there some general formula for how many signatures you would need?

Thanks!

Answer 1

Each additional signature halves the security level.

A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer.

So if you use 256 pairs, which is a reasonable level, since it offers 256 bit security against second-preimage attacks, and 128 bits against collisions, practical attacks are possible once you use the same key three times, and it's trivial to find messages-signature pairs once you use it four times.

Note that at this point the attacker can't fully determine the message he wants to sign, he needs to try $2^{64}$ (after three sigs) or $2^{32}$ (after four sigs) different messages to find one that he can sign. This usually isn't a problem for the attacker, since many things he might want to sign have parts the attacker can choose freely.

Why does it halve after every signature?

When you observe a single signature, you know one hash from each pair. So to create a signature you need to have a message hash that matches every single bit of the signature.

When you observe two signatures, you know both hashes from half of the pairs, and only one hash from the other half. So the message hash only needs to match the half where you only know one.

When you observe three signatures, you know both hashes from 3/4 of the pairs, and only one hash from the remaining 1/4. Now you only need to match 1/4th of the original bits.

etc.

Answer 2

What do you mean by forge? If you are asking about (the common) existential forgery, then two message, signature pairs are enough, given that the messages differ in at least two bits.

As an example consider that you have the signatures for $m_1 = 1111$ and $m_2 = 1100$. Considering the preimages you now have, you can forge signatures for $m_3=1101$ and $m_4=1110$.