Lamport signature

In cryptography, a Lamport signature or Lamport one-time signature scheme is a method for constructing a digital signature. Lamport signatures can be built from any cryptographically secure one-way function; usually a cryptographic hash function is used.

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. Unfortunately, each Lamport key can only be used to sign a single message. However, combined with hash trees, a single key could be used for many messages, making this a fairly efficient digital signature scheme.

The Lamport signature cryptosystem was invented in 1979 and named after its inventor, Leslie Lamport.

Alice has a 256-bit cryptographic hash function and some kind of secure random number generator. She wants to create and use a Lamport key pair, that is, a private key and a corresponding public key.

To create the private key Alice uses the random number generator to produce 256 pairs of random numbers (2×256 numbers in total), each number being 256 bits in size, that is, a total of 2×256×256 bits = 16 KiB in total. This is her private key and she will store it away in a secure place for later use.

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. (Also 16 KiB in total.) These 512 numbers form her public key, which she will share with the world.

Later Alice wants to sign a message. First she hashes the message to a 256-bit hash sum. Then, for each bit in the hash, based on the value of the bit, she picks one number from the corresponding pairs of numbers that comprise her private key (i.e., if the bit is 0, the first number is chosen, and if the bit is 1, the second is chosen). This produces a sequence of 256 random numbers. As each number is itself 256 bits long the total size of her signature will be 256×256 bits = 8 KiB. These random numbers are her signature and she publishes them along with the message.

...
Wikipedia