The Lamport signature scheme shows how to construct a signature scheme for one use from any one-way function.

Keys

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

For $1\backslash leq\; i\backslash leq\; k,\; j=0,1$ let $y\_\{ij\}\backslash in\; Y$ be chosen randomly and $z\_\{ij\}=f(y\_\{ij\})$.

The key $K$ consists of $2k$ $y$s and $z$s. $y$s are secret, $z$s are public.

Signing of a message

Let $x\; =\; x\_1\backslash ldots\; x\_k\; \backslash in\backslash \{0,1\backslash \}^k$ be a message.

$sig(x\_1\backslash ldots\; x\_k)=(y\_\{1,x\_1\},\backslash ldots,\; y\_\{k,x\_k\})=(a\_1,\backslash ldots,a\_k)$ - notation and $ver\_K(x\_1\backslash ldots\; x\_k,\; a\_1,\backslash ldots,\; a\_k)\; =\; true\; \backslash Leftrightarrow\; f(a\_i)\; =\; z\_\{i,x\_i\},\; 1\backslash leq\; i\backslash leq\; k$

Eve cannot forge a signature because she is unable to invert one-way functions.

Note: A Lamport signature can only be used to sign one message. However combined with hash trees, it is possible to only publish a single hash instead of $(z\_\{ij\})$ making the signing of many messages more efficient space-wise.

When used in Merkle trees, Lamport signatures form a digital signature scheme that is secure against quantum computers, the only known digital signature scheme to do so.

See also

• Hash tree

External links

• Efficient Use of Merkle Trees - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.

Cryptography | Asymmetric-key cryptosystems