## Lamport Signatures

Lamport's signature scheme constructs a digital signature from a cryptographic
hash function. The scheme is pretty simple but the basic version of it has
serious constraints which can be mitigated through extra cleverness.

### Informal Explanation

A Lamport signature relies on:
* Generating a lot of pieces of random data as the private key
* Publishing hashes of those pieces of random data as the public key
* Using the bits of the hash of the message being signed to decide which
  bits of the private key (the original random data) to reveal

This produces a working signature scheme:
* An attacker can't sign a message, because they won't have the private data
  they need to reveal to make a signature
* Anyone can verify a signature, by checking that:
  1. The revealed private data matches the previously-known public key
  2. The revealed private data is the right set for the signed message

With the following cool properties:
* It can be implemented in very little code, and doesn't require any advanced
  math
* Its security rests entirely on the security of a cryptographic hash function,
  which is a well-studied problem, and therefore...
* Unlike most signature schemes, it is resistant to quantum cryptanalysis

But there are severe drawbacks:
* The private key, the public key, and the signature are all very large compared
  to other signature schemes
* Signature verification requires hundreds of hash operations
* A given key pair can be used to sign at most one message, since the act of
  signing a message inherently reveals half of the private key; if a second
  message is signed, most of the private key will have been revealed, allowing
  anyone to likely sign other messages

### Syntax

Let:
	R()  return a cryptographically random value of sufficient length to
	     be unguessable
	H(m) return a cryptographic hash of m
	n    be the length of the output of H

### The Lamport Primitive

Lamport signatures work like this:

The signer S chooses a random private key, which is a sequence of n pairs
of random numbers, each itself cryptographically random. So, let the private
key Kp be:

	Kp = { Kp[0], Kp[1], ..., Kp[n] }

where each Kp_i is:

	Kp[i] = { R(), R() }

Then the public key Ku is the hashes of all these values:

	Ku = { Ku[0], Ku[1], ..., Ku[n] }

where each Ku[i] is:

	Ku[i] = (H(Kp[i][0]), H(Kp[i][1]))

The signer then signs a message m thus:

	let { s[0], s[1], ..., s[n] } = H(m) (s is the bits of the hash of m)
	sig = { Kp[0][s[0]], Kp[1][s[1]], ..., Kp[n][s[n]] }

so the signature is a sequence of n of Kp values.

A verifier can validate a signature like so:

	let { sig[0], sig[1], ..., sig[n] } be the signature from above
	let { s[0], s[1], ..., s[n] } = H(m)
	let u[i] = Ku[i][s[i]] for i in 0 to n (i.e. use the i'th bit of s to
	                                        choose an element from the pair
	                                        Ku[i])
	for each u[i]:
		check that H(sig[i]) = u[i]

### A C Implementation

Here is a **non-cryptographic** demonstration of the algorithm, in C. It uses
a fake RNG, a fake hash function, a non-constant-time signature verifier (which
opens it to easy timing attacks), and keys that are far too small to be
practical.

To run this example, do:

$ sed -e '1,/^>>>/d' -e '/^<<</,$d' < THISFILE | cc -x c -o lamport -
$ ./lamport foobar

>>>
/* lamport.c */

#include <stdint.h>
#include <stdio.h>

uint32_t random() {
	static uint32_t r = 0;
	return r++;
}

uint32_t hashv(uint32_t r) { return r * 2; }
uint32_t hashm(const char *m) {
	uint32_t h = 0;
	while (*m)
		h += *(m++);
	return h;
}

#define NBITS(t) (sizeof(t) * 8)

typedef uint32_t randval;
typedef uint32_t hashval;

#define KEYLEN (NBITS(hashval))

typedef randval privkey[KEYLEN][2];
typedef hashval pubkey[KEYLEN][2];
typedef randval sig[KEYLEN];

void genkey(privkey pk, pubkey uk) {
	for (int i = 0; i < KEYLEN; i++) {
		pk[i][0] = random();
		pk[i][1] = random();
	}

	for (int i = 0; i < KEYLEN; i++) {
		uk[i][0] = hashv(pk[i][0]);
		uk[i][1] = hashv(pk[i][1]);
	}
}

void sign(privkey pk, sig s, const char *m) {
	hashval h = hashm(m);
	for (int i = 0; i < KEYLEN; i++)
		s[i] = pk[i][(h >> i) & 1];
}

int verify(pubkey uk, sig s, const char *m) {
	hashval h = hashm(m);
	for (int i = 0; i < KEYLEN; i++) {
		hashval u = uk[i][(h >> i) & 1];
		if (hashv(s[i]) != u)
			return 0;
	}
	return 1;
}

int main(int argc, char *argv[]) {
	privkey pk;
	pubkey uk;
	sig s;

	if (argc < 2)
		return 0;

	genkey(pk, uk);
	sign(pk, s, argv[1]);
	printf("sig starts: %08x %08x %08x %08x\n", s[0], s[1], s[2], s[3]);
	return !verify(uk, s, argv[1]);
}
<<<

### Improvement 1: Smaller Private Keys

The private key can be compacted down by generating it with a CSPRNG or any
other key expansion method. For example, we could compute the private key from
a single random key K and an HMAC function HMAC as:

	Kp[i] = HMAC(K, i)

That reduces the size of the private key, but we unfortunately can't do the
same technique for the public key, since it's unlikely we'll be able to find
any f such that:

	f(i) = H(HMAC(K, i))

for all i (or indeed any useful set of i).

### Improvement 2: Smaller Public Keys

The "public key" can instead be the hash of all the public key hashes, like so:

	Ku = H(Ku[0][0] + Ku[0][1] + Ku[1][0] + Ku[1][1] + ... + Ku[n][1])

Then the signature must include all the "unused" parts of the public key, so
the signature becomes for example:

	{ Ku[0][0], Kp[0][1], Kp[1][0], Ku[1][1], Ku[2][0], Kp[2][1], ... }

so that the verifier can compute:

	{ Ku[0][0], H(Kp[0][1]), H(Kp[1][0]), Ku[1][1], ... }

to verify that the hash of that sequence is the smaller hash public key.

### Improvement 3: Key Trees

It's possible to use a Merkle tree of keys to allow a single private/public key
pair to sign a fixed (but arbitrarily large) number of messages; I'll write
about how this is done in a subsequent post because it's pretty involved and
Merkle trees deserve their own post :)