Lamport Signature - Security Parameters

Security Parameters

The security of Lamport signatures is based on security of the one way hash function, the length of its output and the quality of the input.

For a hash function that generates an n-bit message digest, the ideal preimage and 2nd preimage resistance on a single hash function invocation implies on the order of 2n operations and 2n bits of memory effort to find a collision under a classical computing model. According to Grover's algorithm, finding a preimage collision on a single invocation of an ideal hash function is upper bound on O(2n/2) operations under a quantum computing model. In Lamport signatures, each bit of the public key and signature is based on short messages requiring only a single invocation to a hash function.

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 216 possible private key combinations in 215 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.

Based on Grover's algorithm, a quantum secure system, the length of the public key elements z_i,j, the private key elements y_i,j and the signature elements s_i,j must be no less than 2 times larger than the security rating of the system. That is:

• A 80-bit secure system uses element lengths of no less than 160 bit;
• A 128-bit secure systems uses element lengths of no less than 256 bit;

However caution should be taken as the idealistic work estimates above assume an ideal (perfect) hash function and are limited to attacks that target only a single preimage at a time. It is known under a conventional computing model that if 23n/5 preimages are searched, the full cost per preimage decreases from 2n/2 to 22n/5. Selecting the optimum element size taking into account the collection of multiple message digests is an open problem. Selection of larger element sizes and stronger hash functions, such as 512-bit elements and SHA-512, ensures greater security margins to manage these unknowns.