1
$\begingroup$

I refer to the LM-OTS specification in RFC8554.

It seems that after having hashed all the chains, including the checksum’s ones, the signature is essentially the concatenation of the hash results.

Apparently one can make the signature much shorter, by hashing the above again. Boneh and Shoup define Winternitz signatures in this way. Why the RFC doesn't?

$\endgroup$
1
  • $\begingroup$ Sorry, the question is a mistake. The final hash is applied to the public key, not to the signature. $\endgroup$
    – uk-ny
    Feb 8, 2021 at 18:34

1 Answer 1

2
$\begingroup$

Apparently one can make the signature much shorter, by hashing the above again. Boneh and Shoup define Winternitz signatures in this way

No, Bohen and Shoup do not; their Winternitz signature is a concatination of the hashes. This can be seen as the output of their $S(sk, m)$ algorithm on page 591 of version 0.5 of their book - the signature they generate is $(\sigma_1, ..., \sigma_n)$, that is, the concatination of the intermediate hashes $\sigma_1, ..., \sigma_n$

If you do generate a signature which is the hash of the intermediate hashes, it is not clear how the verification process is supposed to work. The procedure that Boneh and Shoup propose (which is what LM-OTS does) starts with the intermediate hashes $\sigma_1, ..., \sigma_n$, and follow the hash chains upwards to the tops of the Winternitz chains $y_1, ..., y_n$. It is not clear how one can rederive $y_1, ..., y_n$ given only $H(\sigma_1, ..., \sigma_n)$

Now, the public key they use is, in fact, the hash of all the tops of the chains $H( y_1, ..., y_n)$, and hence the public key is short. LM-OTS also follows this.

$\endgroup$
1
  • $\begingroup$ "a signature which is the hash of the intermediate hashes, it is not clear how the verification process is supposed to work" > the one-way property of hashes means that shouldn't be possible. To be able to go from an intermediary hash to a full signature would require you to either: know the secret key and "brute-force" until you find the same intermediary hash, not the goal and costly; or to have a way to reverse the hash from the intermediary hash to its original signature, which is not super compatible with the non-injectivity of hashes and would break the rest of the scheme $\endgroup$
    – Lery
    Feb 8, 2021 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.