Scaling of Memory and Bandwidth Requirements of Post-Quantum Signatures with Message Size

In this work we analyse the qualitative memory and bandwidth efficiency properties of the currently standardised post-quantum signatures as such, and of their protocol integrations mainly in the X.509 context. The term qualitative in this respect refers to how memory and bandwidth requirements scale with the size of the signed message.

Specifically, we address the question of how far the algorithms support online computations, also known as streaming, with respect to the signed message in the signing and verification operations. Further, we review the possibilities for the pre-computation of a short message representative outside the cryptographic module responsible for the signing or verification operation of the different signature schemes. We also give a preview of the corresponding cryptographic API of the PKCS#11 standard, which introduces numerous PQC signature algorithms in the upcoming version 3.2.

We demonstrate that for specific realistic use cases, the qualitative memory and bandwidth efficiency of the PQC signature schemes in protocol use varies widely and tends to be substantially degraded compared to the traditional signature schemes based on RSA and elliptic curves, which always allow for the pre-computation of a short message representative in the form of a hash value. Our results are relevant to PQC migrations of existing applications using traditional RSA or elliptic curve schemes.