1
$\begingroup$

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/
$\endgroup$
  • $\begingroup$ Would generating hashes for the 0 bits actually make any observable difference? $\endgroup$ – Ilmari Karonen May 7 at 10:43
  • $\begingroup$ Perhaps to confirm the length of the message to be signed? E.g. by generating the hashes for the 0's and adding this to the public key, the verifier knows the length of the message which was/is going to be signed. $\endgroup$ – TotalCare May 7 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.