The Cost of PQC Keys and Signatures

Cost = 6 x sig + 2 x pk

While I love elliptic curve and RSA methods in creating signatures, I know that their time is coming to an end. For this, we must look to the rise of PQC signature methods, and especially ML-DSA (Dilitium), FN-DSA (Falcon) and SLH-DSA (SPHINCS+). For this, NIST has been assessing new methods for signatures that use methods that differ from the lattice and hash-based approaches of the current PQC signature standards. One of these contenders is SNOVA, and which uses multivariate cryptography and has good characteristics of key size and performance.

One evaluation that is performed in the SNOVA paper [here] is to plot the signature size against the public key size:

With this, we can see that SPHINCS+ has relatively small public keys, but a large signature size. Falcon and SNOVA seem to have a good compromise of public key sizes and signature sizes. So why does this matter? Well, when we use TLS, the server must send the public key to the client, and then the server must sign requests using its private key. The transmission of these will have an overhead on the connection performance, such as using more bandwidth and possibly…