# Tag Info

3

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, ...

2

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort 2^n, then breaking the Lamport signature scheme with G having k-bit digests requires effort (2^n)/(2k). So strictly speaking, with F truncated to 128 bits and G having 256 bits (2k=512=2^9), you will have 128-9=119 bits of ...

1

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible