1
$\begingroup$

Some applications may require quick transition to post-quantum signatures, and stateful hash-based signatures fill that role (cf. CNSA 2.0).

My question is (ignoring statefullness, focusing on space/time efficiency), how do these schemes (e.g. LMS/XMSS) compare to whatever is used now (RSA, DSA, ECDSA)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

My question is (ignoring statefullness, focusing on space/time efficiency), how do these schemes (e.g. LMS/XMSS) compare to whatever is used now (RSA, DSA, ECDSA)?

Even if we ignore the elephant in the room (state management), it's somewhat hard to give a definitive answer; state based schemes have a number of parameters (size of the hash, the Winternitz parameter, the size of a Merkle tree, the number of levels of Merkle trees), and they (except for the size of the hash) don't actually impact the security, but instead practical aspects (the total number of signatures that can be signed; the speed of the key generation/signature/verify operations).

In addition, in terms of speed, there isn't a unique signature generation algorithm; instead, there are clever ways to store intermediate nodes during the signature generation operation; depending on how much memory you dedicate to storing intermediate nodes, you can speed up the signature generation performance significantly.

If I were to overgeneralize:

  • Public keys are small; about the same size as ECDSA keys of the same classical security level

  • Signatures are large; from perhaps 600 bytes to several kilobytes (depending on the parameters I mentioned above).

  • Signature generation can be fast (similar to or faster than RSA/DSA/ECDSA signature generation); this is assuming that you use one of the clever 'state saving schemes' I mentioned (and the Winternitz parameter you selected isn't too large; this will make the signatures larger, of course)

  • Signature verification can also be fast; my sense is that it'll likely beat DSA/ECDSA (again, if you use a moderately small Winternitz parameter); I suspect it wouldn't be quite as fast as RSA, though...

Improve this answer
$\endgroup$
2
  • $\begingroup$ On the internet context, it's possible to sign more messages using batch/asynchronous signatures with hash-based signatures, that is, instead of signing individual messages, we asynchronously gather some messages and sign them in batch by signing their merkle root, so the signature for each message become the merkle root signed together with an authentication path. It could be regarded akin how the Facebook/GraphQL dataloader library works. $\endgroup$
    – Marco Aurélio da Silva
    Feb 18 at 0:58
  • $\begingroup$ @MarcoAuréliodaSilva: you can, of course, do that with any signature algorithm. The issue with stateful hash-based signatures is not the limit on the number of signatures (which you can easily make quite large), but the requirement to reliably keep state - signing a number of messages at once doesn't help with that $\endgroup$
    – poncho
    Feb 18 at 3:05

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.