Hash collision resistance requirements for Lamport signatures

Question

According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key (and also for hashing signature elements when verifying it); the latter, $G$, is used to hash a message when signing and verifying to get the number of bits corresponding to the number of pairs in keys.

As far as I understand, the requirement for $F$ is that it must be resistant to preimage attacks, and $G$, in addition to this, must also have collision resistance.

Given the standard hash function that satisfies all these requirements, I assume that $F$ and $G$ can be the same, e.g. SHA-256, which provides 256 bit security against preimage attacks and 128 bits security against collision attacks. Using it, we have the following key and signature sizes (described as dimensional arrays):

 Private key: [256][2][32]byte   (16 KiB)
 Public key:  [256][2][32]byte   (16 KiB)
 Signature:   [256][32]byte      (8 KiB)

My question is: if we're aiming for overall 128 bit security, can we reduce the output of $F$ to 128 bits instead of 256 bits, leaving $G$ as is. Does $F$ require collision resistance?

For example, if we use SHA-256/128 for $F$ and SHA-256 for $G$, this will give us the following sizes:

 Private key: [256][2][16]byte   (8 KiB)
 Public key:  [256][2][16]byte   (8 KiB)
 Signature:   [256][16]byte      (4 KiB)

Will this give us 128-bit security?

On the Wikipedia page describing Lamport signatures, there's this paragraph:

For each private key $y_{i,j}$ and its corresponding $z_{i,j}$ public key pair, the private key length must be selected so performing a preimage attack on the length of the input is not faster than performing a preimage attack on the length of the output. For example, in a degenerate case, if each private key $y_{i,j}$ element was only 16 bits in length, it is trivial to exhaustively search all $2^{16}$ possible private key combinations in $2^{15}$ operations to find a match with the output, irrespective of the message digest length. Therefore a balanced system design ensures both lengths are approximately equal.

However I fail to understand it: what are input and output and what message digest length (is it the length of output of $G$, $F$, or both), which part refers to the number of elements in keys and which part refers to the length of a single element? I'd appreciate a better explanation. Thanks!

Answer 1

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

This is not an artifact of the security proof: since there are $256*2=512$ public keys, an attacker has 512x more chances to find a preimage compared to a normal, single preimage attack.

In the Merkle signature scheme, the result is the same but you would multiply k by the number of messages that can be signed. EG for 1 million $(2^{20})$ messages, the security level is $128-9-20=99$ bits.

The wikipedia article is about $F$ only: the "input" is one of the private keys, the "output" is the corresponding public key and "message digest size" is the output size of $F$. I think that it just attempts to say that when the private key is very short and regardless of the output size of $F$, it is trivial to find a preimage.