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$ – JamesTheAwesomeDude May 27 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 May 28 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$ – JamesTheAwesomeDude May 28 at 20:56

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.