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.

Mathematical description

Below is a short description of how Lamport signatures work, written in mathematical notation. For a plain English description see the next section. Note that the "message" in this description is a fixed sized block of reasonable size, possibly (but not necessarily) the hash result of an arbitrary long message being signed.

Keys

Let $k$ be a positive integer and let $P=\left\{0,1\right\}^k$ be the set of messages.Let $f:,Y ightarrow Z$ be a one-way function.

For $1leq ileq k$ and $jin \left\{0,1\right\}$ the signer chooses $y_\left\{i,j\right\}in Y$ randomly and computes $z_\left\{i,j\right\}=f\left(y_\left\{i,j\right\}\right)$.

The private key $K$ consists of $2k$ values $y_\left\{i,j\right\}$. The public key consists of the $2k$ values $z_\left\{i,j\right\}$.

Signing a message

Let $m = m_1ldots m_k in\left\{0,1\right\}^k$ be a message.

The signature of the message is $sig\left(m_1ldots m_k\right)=\left(y_\left\{1,m_1\right\},ldots, y_\left\{k,m_k\right\}\right)=\left(s_1,ldots,s_k\right)$.

Verifying a signature

The verifier validates a signature by checking that $f\left(s_i\right) = z_\left\{i,m_i\right\}$ for all $1leq ileq k$.

In order to forge a message Eve would have to invert the one-way function $f$. This is assumed to be intractable for suitably sized inputs and outputs.

Plain English description

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

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.) This is her public key, which she will share with the world.

Signing the message

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 sum she picks the corresponding number from her private key. If for instance the first bit in the hash sum is a 0, she picks the "first" number in the first pair. If the first bit instead is a 1, then she uses the "second" number in the first pair. And so on. This gives her 256 random numbers. That is, 256×256 bits = 8 KiB in total. These random numbers are her signature and she publishes them along with the message.

Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never publish or use. Preferably she should delete them. Otherwise others will later be able to create false signatures.

Verifying the signature

Then Bob wants to verify Alice's signature of 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 something is wrong.

Note that prior to that Alice has published the signature of a 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 fits other message hashes.

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 a n-bit message digest, the ideal preimage and 2nd preimage resistance on a single hash function invocation implies on the order of 2^n operations and 2^n 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( 2^(n/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_\left\{i,j\right\}$ and its corresponding $z_\left\{i,j\right\}$ 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_\left\{i,j\right\}$ 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.

Based on Grover's algorithm, a quantum secure system, the length of the public key elements $z_\left\{i,j\right\}$ , the private key elements $y_\left\{i,j\right\}$ and the signature elements $s_\left\{i,j\right\}$ 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 2^(3n/5) preimages are searched, the full cost per preimage decreases from 2^n to 2^(2n/5) [Bart Preneel, "Design Principles for Iterated Hash Functions Revised" [http://csrc.nist.gov/pki/HashWorkshop/2005/Nov1_Presentations/preneel_nist_v2.pdf] ] . 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.

Optimisations and variants

Short private key

Instead of creating and storing all the random numbers of the private key a single key of sufficient size can be stored. (Usually the same size as one of the random numbers in the private key.) 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.

In the same manner a single key can be used together with a CSPRNG to create many Lamport keys. Preferably then some kind of random access CSPRNG should be used, such as BBS.

Short public key

A Lamport signature can be combined with a hash list, making it possible to only publish a single hash instead of all the hashes in the public key. That is, instead of the $2k$ values $z_\left\{ij\right\}$. To be able to verify the random numbers in a signature against the single hash all the unused hashes in the public key then needs to be included in the signatures, resulting in signatures of about twice the size, but results in significantly shorter public keys. That is, the values $\left(z_\left\{ij\right\}\right)$ for all $j eq m_i$ needs to be included.

Public key for multiple messages

Each Lamport public key can only be used to sign one single message, which means many keys have to be published if many messages are to be signed. But a hash tree can be used on those public keys, publishing the top hash of the hash tree instead. This increases the size of the resulting signature, since parts of the hash tree have to be included in the signature, but it makes it possible to publish a single hash that then can be used to verify any given number of future signatures.

Hashing the message

Unlike some other signature schemes (e.g. RSA) the Lamport signature scheme does not require that the message "m" is hashed before it is signed. A system for signing long messages can use a collision resistant hash function h and sign h("m") instead of "m".

References

* L. Lamport, "Constructing digital signatures from a one-way function", Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2003 Efficient Use of Merkle Trees] - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.

* [http://www.flexiprovider.de Flexiprovider] - Open source java implementation of Merkle tree signature.
* [http://web.iiit.ac.in/~parminder/lamportSignature.tar.bz2 Lamport Signature] - Open source python implementation of Lamport's Signature

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Lamport-Diffie Einmal-Signaturverfahren — Das Lamport Diffie Eimal Signaturverfahren (engl. Lamport Diffie One Time Signature Scheme, kurz: LD OTS) ist ein Signaturverfahren, dass 1979 von Leslie Lamport und Whitfield Diffie entwickelt wurde. Es verwendet eine Einwegfunktion , welche… …   Deutsch Wikipedia

• Leslie Lamport — Infobox Scientist name = Leslie Lamport image width = 150px caption = birth date = February 7, 1941 birth place = New York City, New York death date = death place = residence = citizenship = nationality = ethnicity = field = Computer Science work …   Wikipedia

• Merkle signature scheme — The Merkle signature scheme is a digital signature scheme based on hash trees (also called Merkle trees) and one time signatures such as the Lamport signature scheme. It was developed by Ralph Merkle in the late 70s and is an alternative to… …   Wikipedia

• Quantum digital signature — A Quantum Digital Signature (QDS) refers to the quantum mechanical equivalent of either a classical digital signature or, more generally, a handwritten signature on a paper document. Like a handwritten signature, a digital signature is used to… …   Wikipedia

• Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… …   Wikipedia

• Digital Signature Algorithm — The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature… …   Wikipedia

• Topics in cryptography — This article is intended to be an analytic glossary , or alternatively, an organized collection of annotated pointers.Classical ciphers*Autokey cipher *Permutation cipher*Polyalphabetic substitution **Vigenère cipher*Polygraphic substitution… …   Wikipedia

• Quantum computer — A quantum computer is a device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, information is… …   Wikipedia

• One-time pad — Excerpt from a one time pad In cryptography, the one time pad (OTP) is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit …   Wikipedia

• Hash tree — A binary hash tree In cryptography and computer science Hash trees or Merkle trees are a type of data structure[citation needed] which contains a tree of summary information about a larger piece of da …   Wikipedia