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 are the most commonly used) but Lamport signatures are unique because they are formed using a hash function. Many cryptographers believe that this makes them resistant to attacks made possible by quantum computers.

How Does a Lamport Signature Work?

Here’s the long version. This is the short copy without all the parameterization:

  1. Come up with 2 sets (set A and set B) each containing 256 random 256-bit numbers. Keep these secret! They’re your private key.
  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 i of the hash from 0..256: if the bit is a 0, publish the ith number from secret set A; if it is a 1, publish the ith number from secret set B. 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 that define whether the value of each bit is 0 or 1).

Because hashes are one-way functions, it is computationally hard to forge the secret random numbers you created in step 1 that would allow an attacker to change your signature. In other words, it takes an impractically huge amount of processing power for an adversary to produce verifiable proof that you signed something other than what you actually signed.

There are two snags with using Lamport signatures in practice:

  1. This is a one-time signature. You can’t sign anything else with the same public key. Doing so reveals more of your secret numbers and would allow an attacker to forge your signature for other documents. Fortunately, this is easily solved with a hash tree that merges many public keys down to a single “root”—this is called the Merkle signature scheme.
  2. The signatures are enormous compared to ECDSA or RSA. Signing an N-bit hash requires N hashes of N bits each. That’s 8 KiB for signing a 256-bit hash or 32 KiB for a 512-bit hash—around 1000× the size of a comparable ECDSA signature.

How to Shorten Lamport Signatures

The Wikipedia article outlines ways to shorten the private key using a cryptographically secure pseudorandom number generator and compress the public key with a hash list. No solution for shortening the public signature itself is published. That’s what I hope to contribute with this article!

The Other End of the Spectrum: A Hash Ladder

First, I present a toy demonstration of the algorithm. It is impractical to implement for a number of reasons, but it shows the functionality. After we go through this, I’ll modify it to make it usable in practice.

Assume you have a 3-bit signature of a document, H_3bit(document) = 6. Pick two random 5-bit values, 12 and 29, as your private key. Hash each value 2^signed_hash_bits + 2 = 2^3 + 2 = 10 times with a perfect random 5-bit oracle called H_5bit. Each possible value of your 3-bit hash has a corresponding index in these chains of 5-bit hashes:

hash ix:  [0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]
A: 12 -->  5 --> 24 -->  9 -->  1 --> 15 --> 10 -->  8 --> 11 --> 27
B: 23 <-- 19 <-- 20 <--  4 <-- 13 <-- 17 <--  3 <-- 14 <-- 28 <-- 29
                                                     ^

A starts on the left and repeated hashes are listed to the right. B starts on the right and repeated hashes are listed to the left. This forms the “ladder” metaphor, with pairs of hashes making the “rungs”. The hash is 5 bits to accommodate at least 20 unique non-colliding hashes. In this example, I made up a perfect random oracle hash function with no collisions. In practice, the hash values are incredibly unlikely to collide because their range is 256+ bits rather than 5.

The values at the end of each chain—(A=27, B=23)—are your public key.

To sign your document with hash 6, find the pair of values at that index: [6] = (A=8, B=14). By publishing these values, anyone with the public key (A=27, B=23) can verify that the pair (A=8, B=14) corresponds to the value 6:

An adversary cannot create a valid signature for another value without inverting one of the hashes. For example, to change the pair to sign the value 7, the adversary must be able to solve H_5bit(x) = 14 for x in order to produce the pair (11, 28). Similarly, to sign the value 5, the adversary must invert H_5bit(x) = 8 and produce the pair (10, 3). I call this construct a hash ladder because every pair of hash values in the two rows locks each other in place and defines a distinct location on the number line.

We can’t actually use this in practice without some modification. Real hashes are at least 256 bits. Creating a signature in this way for a 256-bit value would require a 257-bit hash function to be executed 2×2256+2 times just to make the public key. Not only would one signature take longer to compute than the age of the universe, it isn’t secure without a hash function that is a perfect random oracle—and any machine that could actually compute this would be able to invert hashes by brute force anyway.

To shorten Lamport signatures with a hash ladder in practice, we need to chop up the hash to be signed into chunks with not very many bits (8–16) and create a ladder for each. With between 28 and 216 positions on the ladder, each ladder is short enough to be both computable and to have a very low probability of hash collisions within it.

The Implementable Algorithm

While this can be parameterized to use different chunk sizes and hash sizes, I present the algorithm here using 8-bit chunks and 256-bit hashes.

Signing

  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 64 numbers are your private key.
  4. Hash each of these numbers 258 times. This final set of 32 pairs of hashes is your public key. (Note: use a hash chain and this public key compresses to just 256 bits.)
  5. To create your signature, examine each chunk again. Let the value of the chunk be n in the range [0, 255]. For the pair of private key numbers associated with that chunk: let a equal the first number hashed n+1 times, and let b equal the second number hashed 256−n times. Publish the result (a, b). This is your signature for this 8-bit chunk.
  6. Collect the 32 chunk signatures. You now have a 32×2×(256/8) = 2 KiB signature—4× smaller than the standard Lamport signature.

Verifying

  1. Take the SHA-256 hash of the document you want to verify.
  2. Split the 256-bit hash of the document into 32 8-bit chunks.
  3. For each chunk, let V be the chunk’s value from the hash, (a, b) be the signature pair, and (Pa, Pb) be the corresponding public key pair.
  4. Hash a and count iterations until it equals Pa, or until it has been hashed 256 times. If 256 iterations pass without reaching Pa, the signature is invalid. Save the iteration count as i_a.
  5. Repeat step 4 for b, saving the iteration count as i_b.
  6. If 256−i_a ≠ i_b−1 or 256−i_a ≠ V, the signature is invalid.
  7. If there are more chunks, continue from step 3.
  8. The signature is valid if all chunks pass.

Details

We trade storage size for computation. Rather than computing 256 hashes to verify a 256-bit signature, we now compute at least 256/8 × 256 = 8,192 hashes. Given that hash functions are intended to be fast, this is likely a good tradeoff for cacheable chunk sizes.

If n is the number of bits in the hash function and k is the chunk size in bits:

Hash bits Chunk bits Public key size Relative size Hashes to verify Time @ 100 kHps
256Lamport4096 bytes100%2562 ms
25682048 bytes50%8,1928 ms
25612~1400 bytes~30%~90,000~1 s
256162048 bytes25%1,048,576~10 s
512Lamport32768 bytes100%5124 ms
51288192 bytes25%16,348160 ms
51212~5500 bytes~17%~176,128~1.8 s
512164096 bytes13%1,048,576~21 s

100 kHps (100,000 hashes per second) was chosen from this hardware comparison as a conservative baseline; most CPUs can do SHA-256 at at least the megahash-per-second level.