Lamport signature

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 Kbits in total.) These 512 hashes 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 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]

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 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.

Let ${\displaystyle k}$ be a positive integer and let ${\displaystyle P=\{0,1\}^{k}}$ be the set of messages. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\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 computes ${\displaystyle z_{i,j}=f(y_{i,j})}$.

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

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

The signature of the message is

${\displaystyle \operatorname {sig} (m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})}$.

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

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

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. Note a cryptographically secure hash (or at least whose output is not XORed with the seed) can not be used instead of CSPRNG because signing a message would reveal additional random values from the private key. If the adversary can access the signature before the intended recipients can, then he can forge a signature with a halving of security level for each doubling of the revealed random values from the private key.

In the same manner a single key can be used together with a CSPRNG to create many Lamport keys. Preferably then some kind of post-quantum secure random access CSPRNG should be used. Notably, classic CSPRNG like BBS should not be used.

A Lamport signature can be combined with a hash list, making it possible to publish only the single top hash instead of all the hashes in the public key. That is, instead of the ${\displaystyle 2k}$ values ${\displaystyle z_{ij}}$. To verify against the single top hash, the signature must include the random numbers and the unused hashes from the hash list of the public key, resulting in signatures of about twice the size. That is, the values ${\displaystyle (z_{ij})}$ for all ${\displaystyle j\neq m_{i}}$ needs to be included.

The unused hashes do not need to be included in the signature if a cryptographic accumulator is used instead of a hash list.[4]

Winternitz signature compression reduces the size of the private key and public key by slightly less than a factor of the ${\displaystyle 2\langle {\text{chunk size in bits}}\rangle }$, and half that factor for the signature. The computation increases by slightly more than a factor of ${\displaystyle 2^{\langle {\text{chunk size in bits}}\rangle }/\langle {\text{chunk size in bits}}\rangle }$. A cryptographically secure hash suffices instead of the requirement for a CSPRNG.[5]

A hash list could also be employed to shorten the public key to a single value at the expense of doubling the size of the signature as explained in the prior section.

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 a branch of the hash tree has to be included in the signature, but it makes it possible to publish a single hash that then can be used to verify a large number of future signatures.