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 Ladders for Shorter Lamport Signatures.md

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 if the value of a bit is 0 or 1 for each bit of the signature).

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, which is around 1000x the size of a comparable ECSDA 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 an 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:

• Take the A part of the signature pair, 8. Hash it until it equals 27, the A part of the public key. This takes 2 hashes.
• Take the B part of the signature pair, 14. Hash it until it equals 23, the B part of the public key. This takes 7 hashes.
• The length of each hash chain when producing the public key is 8. This is public knowledge as an algorithmic constant.
• 8-2 = 6, which is the claimed hash. 7-1 = 6, which is also the claimed hash. These values equal each other, and are thus the value that was signed by the owner of the public key (A=27, B=23)

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 change the pair and sign the value 5, the adversary must be able to 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.

Now, 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*2^256+2 times just to make the public signature. 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 perfect random oracle. Any machine that could actually compute this function would be able to invert hashes by brute force anyway.

To use shorten Lamport signatures with a hash ladder in implementation, 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 2^8 and 2^16 positions on the ladder, the ladder is short enough to be both computable and to have a very low probability of having hash collisions anywhere in the ladder itself.

The Implementable Algorithm

While this can be parameterized to use different ladder chunks and different hash sizes, I present this actual algorithm 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 2 hashes each are your public key. (Note: Use a hash chain and this public key becomes just 256 bits)
5. To create your signature, examine each chunk again. Let the value of this chunk be n with the range [0, 255]. There are 2 256-bit numbers of the private key associated with that chunk. Let a equal the first of these numbers hashed n+1 times. Let b equal the second of these numbers hashed 256-n times. Publish the result (a,b). This pair is your signature for this 8-bit chunk.
6. Collect up the 32 signatures from each chunk, and you have a 32*2*(256/8) = 2kb signature! This is 4x smaller than the usual 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 the chunk's value from the hash be V, the signature pair of numbers be (a, b) and the corresponding public key pair be (Pa, Pb)
4. Hash a and count the iterations until it equals Pa or it has been hashed 256 times. If it was hashed 256 times without reaching Pa, the signature is invalid. Save the number of iterations it took to reach Pa from a as i_a.
5. Repeat step (4) for b, saving the number of iterations to reach Pb from b as i_b.
6. If 256-i_a != i_b-1 or 256-i_a != V, this signature is invalid.
7. If there are more chunks, check the next chunk starting with step (3)
8. The signature is valid if all chunks are signed correctly.

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 intended to be fast this is likely to be a good tradeoff for cachable 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

Hash Bits	Chunk Bits	Public Key Size	Relative Size	Hashes to Verify	Time to Verify @ 100 kHps
256	Lamport	4096 bytes	100 %	256	2 milliseconds
256	8	2048 bytes	50 %	8192	8 milliseconds
256	12	~1400 bytes	~30 %	~90000	~ 1 second
256	16	2048 bytes	25 %	1048576	~ 10 seconds
512	Lamport	32768 bytes	100 %	512	4 milliseconds
256	8	8192 bytes	25 %	16348	160 milliseconds
256	12	~5500 bytes	~17 %	~176128	~ 1.8 seconds
256	16	4096 bytes	13 %	1048576	~ 21 seconds

100 kHps (100,000 hashes per second) was chosen from this list as most CPUs are able to do SHA-256 at at least the megahash-per-second level.

Hi shelby3,

I have been rewriting this page periodically to try to clarify the algorithm. It appears it still needs more work :)

The main thing that makes me think I haven't communicated it clearly is that the B leg of the ladder is absolutely critical to the algorithm. The fact that a single value hash-chains to the public key is, as you correctly called out, not at all secure. It is trivial to derive any value in that chain after the one provided by the signer and claim that corresponds to the value that was signed. What is impossible (computationally unfeasible) is changing its partner--the hash value in the other chain. Since the hash legs go in opposite directions, advancing the A leg requires inverting the hash on the B leg and vice-versa. There is exactly one location where the values from both legs of the ladder are public: the value that was signed. I think defining my random oracle and giving more thorough examples will help explain this.

In the toy example, the entire hash is 3 bits: i.e. the values of the hash can only be 0-7, so there is exactly 1 place that corresponds to that value on the hash ladder. In a real implementation, it is not feasible to have hash chains 2^256 bits long. So, the hash must be split into smaller chunks, each with their own ladder. That is what is shown in the implementable algorithm and the table at the end.

Just as with a Lamport signature, a CSPRNG can be used (but is not required) to derive the roots of the A and B ladders. I left off compression methods like this because they are the same as for the usual Lamport signature.

I'll work on this explanation when I get some time. Please check back!

I see now the bidirectional legs of the ladder insures that signing once doesn't reveal additional random values because signatures always need a pair.

This hinges on the fact that you don't place the "rungs" at the bit positions of the message hash, rather at the values of the message hash. If you instead placed them at the bit positions as I was thinking, then the bidirectional information in the signature would overlap and additional random values would be revealed. Thus this is not really a Lamport signature any more (except in the sense yours remain resistant to quantum computing), rather Lamport is your inspiration and comparative benchmark to improve upon.

In a minor correction I don't think you need the extra value for the seed of each leg of the ladder, just make that key value the lowest, leftmost message value (for leg A and greatest, rightmost for leg B) of the message hash, because if you reveal it in a signature it won't be reused again any way.

Your algorithm compresses the signatures much more than your performance table indicates now compared to Lamport, e.g. an 8-bit chunk size will reduce the size of the private key and public key by a factor of 8 (the two legs of the ladder are offset by not needing two sets of keys one each for 0 and 1 values of each bit), and signature by a factor of 4 (since a Lamport signature only reveals half of the private keys).

The increase in computation is [2^(chunk size in bits)/(chunk size in bits)] more hashes when computing the public key, signing, and verifying a signature. Thus an 8-bit chunk size increases computation by a factor of 2^8/8 = 32, a 16-bit chunk size by a factor of 4096.

I think you also didn't mention that your algorithm compresses the private key and doesn't require a CSPRNG rather only a cryptographic hash, because the bidirectional ladder legs insure against revealing additional chained random values from the private key because a leg pair is required to sign.

I've added your algorithm to the Wikipedia page.

https://en.wikipedia.org/wiki/Lamport_signature#Short_keys_and_signature

Congratulations on finding a way to trade computation for space. This will be much appreciated by the community assuming it is correct, which it appears to be.

Wow, thank you!! My first Wikipedia citation, that's so cool!

I really appreciate you taking the time to review my work.

I agree that the extra value on each leg is probably not needed. My original motivation for adding doing so was that no information about the private keys is revealed. If the PRNG used to create the roots of each leg of the ladder were not cryptographically secure, it would be a problem to reveal any of those root values. But if a CSPRNG is used (as it should be), the extra hash is likely unnecessary.

I'll double-check my math for the compression and computation and update this paper.

Thanks again for the reference!

I just announced your discovery to the bitcointalk.org forum which will probably induce more peer review.

My understanding is a CSPRNG differs from a cryptographic hash in that it requires among other properties the impossibility of computing the next random output if you know the current output but don't also know the seed, i.e. a CSPRNG in this respect is functionally analogous to a cryptographic hash whose output is XORed with the original seed (which is not necessarily the input). As far as I can see your algorithm doesn't need a CSPRNG and a cryptographic hash will suffice, even if you make the initial seed the first value in the ladder leg as I suggested. A cryptographically insecure PRNG would be unaccepted for many reasons, not just if you don't hide the seed, e.g. it might possible to find the private key values that were not revealed using cryptographic analysis (such as a birthday attack on the seed entropy).

I hereby generalize your original algorithm to N dimensions.

Note your ladder is a one-dimensional line (with my prior suggested minor improvement).

PK     [0]    [1]    [2]    [3]     PK
    A: 12 -->  5 --> 24 -->  9 -->  1
23 <-- 19 <-- 20 <--  4 <-- 13 :B

Here I show a two-dimensional ladder grid.

PK     4 |
       ^ |
    A  | |
    9 13 |        [2]    [3]
    |  ^ |
    v  | |
    1 17 |        [0]    [1]
    |  B |
    v    | PK                   PK
PK 15    |     A: 12 -->  5 --> 24
         | 23 <-- 19 <-- 20 :B

Compared to standard Lamport, the private key and public are reduced by factor 2 × chunk bit size ÷ (2 + (N - 1) × 2), and the signature by a factor chunk bit size ÷ (2 + (N - 1) × 2), where N is the number of ladder dimensions.

Compared to standard Lamport, the computation increases by (N × Nth root of (2^chunk bit size)) ÷ chunk bit size.

However what we see is this is equivalent to changing the chunk bit size, i.e. we get same results for a 256-bit hash whether we set chunk bit size=8, N=1 or chunk bit size=256, N=32.

So what I've shown is the chunks can be visualized as a multi-dimensional ladder space.

Also I believe your algorithm is still Lamport and is a generalization of Lamport, since chunk bit size=1, N=1 is standard Lamport, if note only need to reveal A or B in that degenerate case thus computation factor increase is 1 not 2. Which requires you to accept my suggested minor improvement, otherwise the prior sentence isn't true.

If anyone wants to acknowledge my contribution, my name is Shelby Moore III.

Could you link the bitcointalk thread? I read stuff on there occasionally but couldn't find it, and I'd be interested in getting more feedback on my little invention.

I like the generalization to N dimensions and how you showed that chunking is just changing the dimensionality of the hash ladder. That is a very elegant way of describing it, and lends itself more easily to analysis. It does seem that the usual Lamport signature is a degenerate case of this algorithm. I had had that intuition in the past, but I was missing the generalization to N dimensions that makes it easier to describe. Thanks!

I mentioned as a potential solution to the quantum computing and crypto-analysis threat, but most of the people there who are knowledgeable enough are resistant to any insinuation of a Bitcoin weakness. Perhaps you won't get significant feedback until perhaps someone employs your algorithm in an altcoin or if some other academic cryptography paper cites yours.

You could speed it up if you used a non-standard version of the hashing algorithm.

SHA-256 uses 64 rounds but there is no limit to the number of rounds.

You could count in rounds instead of the full hashing steps.

To ensure that you get the full SHA256 security, you would need to do at least 64 rounds every time.

Hash(A, N) means use N rounds to hash A

Pick A and B

compute H1 = Hash(A, 320) and H2 = Hash(B, 320)

H1 and H2 are your public keys and A and B are your private keys.

To encode an 8 bit number x, you send M = H(A, x) and N = H(B, 255 - x).

To verify, you compute

H(M, 256 + 64 - x) and H(N, 65 + x)

You do have to send the internal state of the hashing function though, so maybe it wouldn't really work.

TierNolan, your proposal is insecure because 1 round of SHA-256 is not secure against pre-image attacks, thus the prior rungs of the ladder could be obtained from cryptanalysis after the first signature enabling signatures to be forged.

The ability to forge a Lamport signatures normally only becomes less secure after the second signature:

http://crypto.stackexchange.com/questions/2640/lamport-signature-how-many-signatures-are-need-to-forge-a-signature

I made a fork of your gist that fixes a number of typos and minor issues.

You should cite Winternitz signatures as a prior art.

As far as I can see there is no protection in Winternitz against signing a different message which has a chunk value greater than the one revealed in the signature.

The hash ladder provides this protection, because each "rung" (sic, i.e. leg) accumulates in the opposite direction.

I see only a single pair (and not two pairs of) secret and verification key(s) generated for each chunk of w bits:

http://www.e-reading.ws/bookreader.php/135832/Post_Quantum_Cryptography.pdf#page=45

Thus as far as I can see there is no "hash ladder" with two legs for each chunk.

Winternitz encoding guarantees that if there is any difference at least one codeword must be higher in position; resulting in slightly more than half the size of the encoding described here.

Okay I see that (but I didn't digest the math yet as to your claim that it provides the same protection), there are more than n/w codewords because t = t1 + t2.

So this is just trading more computation for space. The hash ladder can do this by increasing decreasing w.

I need to study more to see if one is more efficient than the other.

Okay I see now. The checksum of the t1 codewords (chunk of w bits) is accumulated in the opposite direction pow(2,w) - bi, then the checksum is signed which requires t2 codewords. Thus any attempt to forge a signature would require all t1 chunks have greater or equal values to the one-time signature's t1 chunks. And thus the checksum would have a lower value since it is accumulated in the opposite direction, which would require inverting the one-way cryptographic hash. Thus Winternitz is indeed more efficient— the other leg of the ladder is a checksum.

What pisses me off at myself is that when I was studying this gist months ago, I thought of using a checksum for the other leg of the ladder, but I was in such a rush I didn't do the math correctly in head (given how delirious I was at the time with my CFS and peripheral neuropathy which is much improved now due to the AHCC)— two chunks added together require one additional bit not w bits (thus the log2(t1) in the equation for t2)!

@karlgluck I think that what you're talking about has already been described. This is a derivative idea of Merkle-Winternitz signatures (or MW-chains).

See section 4.6 of http://www.monarch.cs.rice.edu/monarch-papers/ndss03rev.pdf

I think if your ladder is 256 hashes then you can sign one byte with ladder.
Then create 32 ladders to sign 32bytes (to sign arbitrary large message its enough to sign hash of message ).
Then sort the final values and put them to merkle tree.
Then you can do probabilistic checks. Select two random bytes from message hash, run the scheme 256 times, then check if final values are ordered.

Necrobump!

This is phantasm! Fantastic! Has this or is this been/being researched? I am willing to code up example implementations in various languages.

@operator-DD3, I'd like to know about more about progress an this kind of signature Scheme, too. @shelby3, @karlgluck, any news for us?

https://github.com/operator-DD3/lamport-signatures-lua
Simple Proof-of-concept coded in lua. Lua should be easy to port to nearly any language.

@operator-DD3 @MaiaVictor Hey folks, for some reason I don't get email about replies here--sorry for the long delay on a reply.

In doing more research, as @Bren2010 mentioned, this is very similar to a Merkle-Winternitz signature. The implementation is fairly straightforward, as you found, and I didn't see more immediate opportunity for optimization. The signatures are still too large for practical use at the moment.

I think relaxing the constraint of a perfect signature and instead looking for a probabilistic check like @anlhord suggested is really promising. If I were to continue my research, this is the direction I'd pursue.

Hello all, I have implemented this in C#: https://github.com/jdluzen/lamport. Would appreciate any comments, especially if I have done anything insecurely.

Edit: added 16 bit chunks.

I found nice Go implementation of Winternitz signatures
https://godoc.org/github.com/dchest/wots

In https://eprint.iacr.org/2011/191.pdf there are interesting conclusions:

In this paper we show that weaker assumptions are sufficient for the security of W-OTS. We show that W-OTS is existentially unforgeable under adaptive chosen message attacks [11] when instantiated with a family of pseudorandom functions (PRF). Since the PRF property is not affected by birthday attacks, hash functions with shorter output length can be used which in turn reduces the signature size. This result is especially meaningful because the main issue with hash-based signatures is the signature size.

We use the output of the function f_k_ as key for the next iteration. The function is always evaluated on the same input x. This is in contrast to the original construction, where the output of the function is used as input for the next iteration and the key remains fixed.

So chaining can be done with 128 bits instead of 256 reducing total signature size two times (1kb -> 0.5 kb). The final zipping function still needs to be collision resistant (256 bit).

Can AES be used for chaining?

I think relaxing the constraint of a perfect signature and instead looking for a probabilistic check like @anlhord suggested is really promising. If I were to continue my research, this is the direction I'd pursue.

@karlgluck @anlhord Can you elaborate on the approach with sorting, please?
I can not understand this part: "Then you can do probabilistic checks. Select two random bytes from message hash, run the scheme 256 times, then check if final values are ordered."

There may be a bug with step 6 of the verification process:

If 256-i_a != i_b-1 or 256-i_a != V, this signature is invalid.

It should be modified to

If 258-i_a != i_b-1 or 257-i_a != V, this signature is invalid.

@karlgluck