Lamport signature - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Lamport signature
9 languages
Deutsch<br>Español<br>Français<br>עברית<br>日本語<br>한국어<br>Nederlands<br>Русский<br>Türkçe
Edit links
From Wikipedia, the free encyclopedia
Cryptographic signature scheme
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. Each Lamport key can only be used to sign a single message. 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.
The Lamport signature cryptosystem was invented in 1979 and named after its inventor, Leslie Lamport.[1]
Example<br>[edit]
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.
Making the key pair<br>[edit]
Diagram illustrating the key generation process in the Lamport one-time signature scheme.<br>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 = 128 Kibit 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 128 Kibits in total.) These 512 hashes form her public key, which she will share with the world.
Signing the message<br>[edit]
Diagram illustrating how a message is signed using the Lamport signature scheme.<br>Later, Alice wants to sign a message.
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 make up 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 numbers. As each number is itself 256 bits long, the total size of her signature will be 256×256 bits = 65536 bits = 64 Kibit.
These (originally randomly picked) numbers are her signature, and she publishes them along with the message.
Note that now that Alice's private key is used, it should never be used again. She must destroy the other 256 numbers that she did not use for the signature. Otherwise, each additional signature reusing the private key reduces the security level against adversaries that might later create false signatures from them.[2]
Verifying the signature<br>[edit]
Diagram illustrating how a verifier selects elements from a public key during Lamport signature verification.<br>Diagram illustrating the final hashing and comparison steps in Lamport signature verification.<br>Then Bob wants to verify Alice's signature on the message.
He also hashes the message to get a 256-bit hash sum.
Then he uses the bits in the hash sum to pick out 256 of the hashes in Alice's public key. He picks the hashes in the same manner that Alice picked the random numbers for the signature. That is, if the first bit of the message hash is a 0, he picks the first hash in the first pair, and so on.
Then Bob hashes each of the 256 random numbers in Alice's signature. This gives him 256 hashes. If these 256 hashes exactly match the 256 hashes he just picked from Alice's public key, then the signature is ok. If not, then the signature is wrong.
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. And after Alice has published the signature, others still do not know the other 256 random numbers and thus can not create signatures that fit other message hashes.
Formal description<br>[edit]
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.
Keys<br>[edit]
Let
{\displaystyle k}
be a positive integer and let
{\displaystyle P=\{0,1\}^{k}}
be the set of messages. Let
{\displaystyle f:\,Y\rightarrow Z}
be a one-way function.
For
{\displaystyle 1\leq i\leq k}
and
{\displaystyle j\in \{0,1\}}
the signer chooses
{\displaystyle y_{i,j}\in Y}
randomly and...