For the Lamport or Winternitz public keys, couldn't one just hash down the large public key to 256 bits in order to greatly reduce the public key size while still having basically the same security? Why isn't this done?

Thanks for your help. If you have any further readings, they are always welcome.

  • 1
    $\begingroup$ Mini-answer: doing so would triple the size of the signatures. If you only published an initial "fingerprint", commitment $F\left(F\left(k_1\right), \cdots, F\left(k_n\right))\right)$, then when it comes time to publish the select $k_i|i\in G(m)$, you'll have to also publish the full, originally-committed public key (netting you no savings, and in fact a very slight extra net data transfer). This may or may not be appropriate for you if storing the public key for a while would be more inconvenient than transmitting a larger key later on, but it's all just a few KiB so shouldn't matter. $\endgroup$ Commented May 27, 2021 at 21:34
  • 1
    $\begingroup$ I don't quite understand. For e.g. Winternitz in order to confirm the signature, one would just have to hash the message some number of times (simplified) to then see whether one receives the same public key. So hashing wouldn't do a difference here it would be just one more step in the confirmation process, would it? $\endgroup$
    – DaGammla
    Commented May 28, 2021 at 14:04
  • $\begingroup$ I think you're right for the Winternitz scheme, actually -- if you store and publish public key fingerprint $Y'=f(Y)$, the end user should be able to calculate it just fine per one step capping off the normal process. $\endgroup$ Commented May 28, 2021 at 20:56


Your Answer

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