I describe a method for making Lamport signatures take up less space. I haven't seen anyone use hash chains this way before, so I think it's pretty cool.

Hash Chains for Shorter Lamport Signatures.md

work in progress

What's this all about?

Digital cryptography! This is a subject I've been interested in since taking a class with Prof. Fred Schneider back in college. Articles pop up on Hacker News fairly often that pique my interest and this technique is the result of one of them.

Specifically, this is about Lamport signatures. There are many signature algorithms (ECDSA and RSA come to mind as popular choices) but Lamport signatures are unique because they are formed around a hash function. Many cryptographers believe that, as such, they are immune to attacks made possible by quantum computers.

How does a Lamport Signature work?

Here's the long version. I'll give you the short copy without all the parameterization:

1. Come up with 2 sets (set 0 and set 1) of 256 random 256-bit numbers. Keep these secret!
2. Take the SHA-256 hash of each of your secret numbers. These 512 hashes are your public key.
3. Get the SHA-256 hash of whatever document you want to sign
4. For each bit of the hash: If it is a 0, publish the corresponding number from secret set 0. If it is a 1, publish the corresponding bit from secret set 1. Destroy all unused numbers.
5. You now have a signature (the 256 random numbers from step 4 corresponding to the bits of the hash from step 3) and a public key (the 512 hashes from step 2).

Because hashes are un-invertible, there is no way other than brute force to forge the secret, random numbers you created in step 1 that would allow an attacker to change your signature.

There are two snags with using this scheme in practice:

1. This is a one-time signature. You can't sign anything else with the same public key, because doing so would reveal more secret numbers and potentially compromise your signatures. This is easily solved with a hash tree, which is called the Merkle signature scheme.
2. The signatures are huge compared to ECDSA or RSA. Signing an N-bit hash requires 2N hashes of N bits each... that's around 16kb for signing a 256-bit hash. Fortunately, the security factor for hash functions is better than that for other signature schemes so we need fewer bits to achieve the same security, but the size of the signature itself is still comparatively enormous. Moreover, the fact that it is quadratic in the number of bits of the hash is less than desirable.

How to Shorten Lamport Signatures

The Wikipedia article outlines ways to shorten the private key using a random number generator and compress the public key with a hash list, but no solution for shortening the public signature is published. That's where this article comes in! (cue trumpets)

Let's jump right into how it works first, then I'll give a description of its properties and how I came up with it. This whole thing can be parameterized, but I am going to use real numbers for clarity.

The Algorithm

1. Take the SHA-256 hash of the document you want to sign
2. Split the 256-bit hash of your document into 32 8-bit chunks
3. For each chunk, generate a pair of (secret) random 256-bit numbers. These are your private key.
4. Hash each of these numbers 257 times. This final set of 64 hashes are your public key. Use a hash chain and this public key becomes just 256 bits.
5. To create your signature, examine each chunk again. Each chunk has a range [0, 255], so let's say it has the unsigned integer value 152. There are 2 256-bit numbers of the private key associated with that chunk. Hash the first of these numbers 152+1=153 times and publish it. Hash the second of these numbers (256-(152)) = 105 times and publish it. These two numbers are your signature for this 8-bit chunk.
6. Collect up the 32*2 signatures from each chunk, and you have a 32*2*(256/8) = 2kb signature! This is 8x smaller than the usual Lamport signature.

How it Works

The two hash chains for each chunk form what I call a hash ladder. An easy way to visualize it is the following. In this notation, H_1(x) = H(x) , H_2(x) = H(H(x)), H_3(x) = H(H(H(x))) and so on.

   SECRET 1A --> H_1(1A)   --> H_2(1A)   --> ... --> H_256(1A) --> PUBLIC 1A = H_256(1A)
   PUBLIC 1B <-- H_256(1B) <-- H_255(1B) <-- ... <-- H_1(1B)   <-- SECRET 1B

If the chain is 256 hashes long, the pair (H_2(1A),H_255(1B)) represents the number 1. For an attacker to forge this and represent the number 1 or 3, a hash function in either the first or second chain repsectively must be inverted. Given that this is considered computationally hard, I claim that this scheme offers comparable security to the large-form Lamport signature.

It's easy to verify that the signature is valid. For each chunk, simply hash each part of the provided signature pair the expected number of times and see if the results match the public key.

Details

We trade off storage size for computation. Rather than having to compute 256 hashes to verify a 256-bit signature, we now must compute at least 256/8 * 256 = 8192 hashes. However, given that hash functions are much faster than access to main memory, this is likely to be a good tradeoff for moderate chunk sizes.

Specifically:

if n is the bits of the hash function and k is the bit size of each chunk:

(n/8)*2*(n/k) bytes is the size of the public key

n/k * 2^k is the number of hashes that must be computed to verify the key

The usual Lamport algorithm is essentially a special case of k=1: every group is 1 bit, and the second part of each pair is implied since there is only 1 option.