# Hash collision resistance requirements for Lamport signatures

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?

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!

-

## 1 Answer

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.

-

Thanks! So, in general, for Lamport signatures with ~s-bit security for both collisions and preimages, k=2s, n=s+log2(4s), which for 128-bit security is 256 and 137. – dchest Oct 8 '12 at 17:14
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8969996571540833, "perplexity_flag": "middle"}