Lamport signature

From Wikipedia, the free encyclopedia

In cryptography, Lamport signature or Lamport one-time signature scheme is a method to construct a digital signature. Lamport signatures can be built from any one-way function. Usually a cryptographic hash function is used as the one-way function.

Lamport signatures are believed to still be secure in the event that quantum computers become reality. Unfortunately each Lamport key can only be used to sign one single message. But combined with hash trees one single key can be used for many messages and then it becomes a fairly efficient digital signature scheme.

1 Keys
2 Signing a message
3 Verifying a signature
4 Optimisations
5 References
6 See also

[edit] Keys

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

For $1\leq i\leq k$ and $j\in \{0,1\}$ the signer chooses $y_{i,j}\in Y$ randomly and computes $z i, j = f (y i, j)$ .

The secret key $K$ consists of $2 k$ values $y i, j$ . The public key consists of the $2 k$ values $z i, j$ .

[edit] Signing a message

Let $m = m_1\ldots m_k \in\{0,1\}^k$ be a message.

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

[edit] Verifying a signature

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

In order to forge a message Eve would have to invert the one-way function $f$ . This is assumed to be intractable.

[edit] Optimisations

A Lamport signature can be combined with a hash list making it possible to only publish a single hash instead of $(z i j)$ . This requires that the values $z i j$ for all $j\neq m_i$ are also included in the signatures, thus resulting in signatures of about twice the size, but significantly shorter public keys.

Still, 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 hash all those public keys and then the top hash of the hash tree can be published instead. This too increases the size of the resulting signature since parts of the hash tree has to be included in the signature, but it makes it possible to publish one single hash that then can be used to verify millions of future signatures.

[edit] References

L. Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
Efficient Use of Merkle Trees - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.

[edit] See also

Hash tree - A method originally invented to be used together with Lamport signatures.

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

Public-key cryptography v • d • e
Algorithms: Cramer-Shoup \| DH \| DSA \| ECDH \| ECDSA \| EKE \| ElGamal \| GMR \| IES \| Lamport \| MQV \| NTRUEncrypt \| NTRUSign \| Paillier \| Rabin \| RSA \| Schnorr \| SPEKE \| SRP \| XTR
Theory: Discrete logarithm \| Elliptic curve cryptography \| RSA problem
Standardization: ANS X9F1 \| CRYPTREC \| IEEE P1363 \| NESSIE \| NSA Suite B Misc: Digital signature \| Fingerprint \| PKI \| Web of trust \| Key size
Cryptography v • d • e
History of cryptography \| Cryptanalysis \| Cryptography portal \| Topics in cryptography
Symmetric-key algorithm \| Block cipher \| Stream cipher \| Public-key cryptography \| Cryptographic hash function \| Message authentication code \| Random numbers