Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.