How does the KeyGen of Merkle's improvement of Lamport's OTS work?

Question

In his paper [1] on page 17 and 18, Merkle proposes an improvement on Lamport's OTS by only signing the 1's in the message in combination with a checksum of the amount of 0's in the message. I get the intuition, and why this would, on average, approximately reduce the signature size by half. However, I am not sure what the private/public key should look like?

I feel like if key's are generated in the same way as 'default' Lamport's OTS, the public/private keys would be unnecessarily large.

In this blog [2], I found this is indeed not the case, and the author states that the pk/sk are also cut in half, since only 1's are included. For me it is not clear if for every bit (both 0's and 1's) in the message only a single random string generated $sk_{i,1}$ and hashed in the public key, or if for every 1-bit in the message a pair of strings $(sk_{i,0},sk_{i,1}) $ generated, and nothing for 0-bits?

Also, I think that 0-bits of the checksum are signed as well and only the 0-bits of the message are omitted, is this correct?

1. http://www.merkle.com/papers/Certified1979.pdf
2. https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/

Answer 1

You only need to store the hash values for the 1s. The checksum bits at the end (which encode the number of 0s) ensure that messages cannot be crafted in such a way to flip 1s down to 0s as doing so would create additional 1s into the checksum part which would require revealing additional preimages from the private key.