Although the potential development of quantum computers threatens the security of many common forms of cryptography such as RSA, it is believed that Lamport signatures with large hash functions would still be secure in that event.
However, many Lamport signatures can be handled by one Merkle hash tree, thus a single hash tree key can be used for many messages, making this a fairly efficient digital signature scheme.
[1] Alice has a 256-bit cryptographic hash function and some kind of secure random number generator.
To create the public key she hashes each of the 512 random numbers in the private key, thus creating 512 hashes, each 256 bits in size.
These 512 hashes form her public key, which she will share with the world.
These (originally randomly picked) numbers are her signature and she publishes them along with the message.
[2] Then Bob wants to verify Alice's signature of the message.
Then Bob hashes each of the 256 random numbers in Alice's signature.
Note that prior to Alice publishing the signature of the message, no one else knows the 2×256 random numbers in the private key.
Thus, no one else can create the proper list of 256 random numbers for the signature.
Below is a short description of how Lamport signatures work, written in mathematical notation.
Note that the "message" in this description is a fixed sized block of reasonable size, possibly (but not necessarily) the hash result of an arbitrarily long message being signed.
In order to forge a message Eve would have to invert the one-way function
This is assumed to be intractable for suitably sized inputs and outputs.
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 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 yi,j and its corresponding zi,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 yi,j element was only 16 bits in length, it is trivial to exhaustively search all 216 possible private key combinations in 216 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 zi,j, the private key elements yi,j and the signature elements si,j must be no less than 2 times larger than the security rating of the system.
That is: 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.
[3] 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.
The single key can then be used as the seed for a cryptographically secure pseudorandom number generator (CSPRNG) to create all the random numbers in the private key when needed.
Note a cryptographically secure hash (or at least whose output is not XORed with the seed) can not be used instead of CSPRNG because signing a message would reveal additional random values from the private key.
If the adversary can access the signature before the intended recipients can, then he can forge a signature with a halving of security level for each doubling of the revealed random values from the private key.
Preferably then some kind of post-quantum secure random access CSPRNG should be used.
A cryptographically secure hash suffices instead of the requirement for a CSPRNG.
[5] A hash list could also be employed to shorten the public key to a single value at the expense of doubling the size of the signature as explained in the prior section.