Post-Quantum Certificates
Signs of Triviality
Opinions, mostly my own, on the importance of being and other things.
[homepage]<br>[blog]<br>[jschauma@netmeister.org]<br>[@jschauma]<br>[RSS]
Post-Quantum Certificates
June 27th, 2026
On June 24th, I gave a talk at the Troopers conference<br>discussing post-quantum cryptography and some lessons<br>from Akamai's rollout of PQC to our global Content<br>Delivery Network. While the industry's immediate<br>focus has been on deploying support for hybrid<br>Key Agreement for TLSv1.3 (specifically: X25519MLKEM768), I also covered<br>the current developments with respect to post-quantum<br>certificates.
Post-quantum certificates have been discussed to some<br>degree in various other blog posts, but doing the<br>research in preparation of my talk lead me to some<br>considerations I didn't see called out explicitly.<br>You can, of course, just skim the slides, if you<br>like, but I figured there's some value in writing<br>things down here as well.
Size Matters
Within the context of TLS certificates, size matters.<br>Specifically, the size of the public keys and<br>signatures. (Key generation, encap/decap, and signing<br>performance of the PQC algorithms is either on par<br>(for EC) or much better (for RSA), so not a bottleneck<br>here.) The table below shows the respective sizes for<br>the ECDSA, RSA, and ML-DSA algorithms:
Algorithm<br>Public Key<br>Signature
ECDSA P-256<br>64<br>64
ECDSA P-384<br>96<br>96
RSA<br>256<br>256
ML-DSA-44 (NIST Level 1 / 128-bit)<br>1,312<br>2,420
ML-DSA-65 (NIST Level 3 / 192-bit)<br>1,952<br>3,309
ML-DSA-87 (NIST Level 5 / 256-bit)<br>2,592<br>4,627
When a client connects to a server, how many bytes do<br>we need for the public key and signature bits of the<br>TLS handshake? Let's take a look:
That is, the server has to send a leaf certificate,<br>which contains a public key and a signature by the<br>intermediate certificate as well as (at least) two<br>Signed Certificate Timestamps (SCTs) from the<br>Certificate Logs; an intermediate certificate, again<br>with a public key and a signature by a root cert; as<br>well as the transcript hash signature.
So for a typical ECDSA P-256 leaf cert with, say, an<br>ECDSA P-384 intermediate, that adds up to: 64 (leaf public<br>key) + 2 * 64 (SCT sigs) + 64 (transcript hash signature)<br>+ 96 (intermediate public key) + 2 * 96 (intermediate<br>and root signature) = 544 bytes.<br>(For RSA: 7 * 256 = 1,792 )
If we use ML-DSA-44 certificates instead, then we end<br>up with 2 * 1,312 + 5 * 2,420 = 14,724 bytes.<br>Ouch. This increase in size is why we need a<br>different approach, and why people have suggested to<br>use Merkle<br>Tree Certificates (MTCs). (Obligatory Merkel Tree pun.)
Merkle Tree Certificates
Now the main goal of MTCs is to avoid having to send<br>multiple large signatures. How we try to accomplish<br>this is interesting and with many parallels to Certificate<br>Transparency logs. These MTCs come in two flavors:<br>standalone and<br>landmark-relative certificates.
Standalone MTCs
To issue a new standalone MTC, the given CA<br>will, somewhat simplified, log the information,<br>construct and sign<br>subtree heads (called "landmarks"), and then collect<br>2+ co-signatures. So the breakdown of the number of<br>bytes we need for such a certificate is:
1 TLS transcript hash signature: 2,420 bytes +<br>1 public key: 1,312 bytes +<br>1 inclusion proof: 384 bytes +<br>2(+) cosignatures: 2 * 2,420 =<br>Total: 8,956 bytes
So that's quite a bit better than the 14,724 bytes<br>from the traditional cert, but still not great. But<br>do note that the inclusion proof is quite<br>small here, and what we'd like to do is get away with<br>fewer of those large signatures. So to that end, if<br>you were able to just hand the client an inclusion<br>proof relative to a landmark the client already<br>has, then you won't need to send the<br>co-signatures at all. Enter<br>landmark-relative MTCs.
Landmark-relative MTCs
Instead of signing each certificate individually, a CA<br>produces "signatureless" certificates in batches,<br>entering the information into logs and periodically<br>signing the inclusion proofs relative to a given<br>"landmark".
Landmarks (trust anchors) from trusted co-signers are<br>updated by clients periodically and the client signals<br>the availability of given landmark to server, which<br>then can return only:
1 TLS transcript hash signature: 2,420 bytes +<br>1 public key: 1,312 bytes +<br>1 inclusion proof: 736 bytes +<br>Total: 4,468 bytes
(The size of the inclusion proof depends on the<br>landmark presented and grows logarithmically based on<br>the number of hashes covered; the 736 bytes used here<br>is based on the draft's example of a landmark being<br>allocated by the given CA every hour, covering perhaps<br>4,4M certificates with 23 hashes in the inclusion<br>proof.)
No Free Lunch
Ok, so 4,468 bytes is a lot better than 14,724 bytes,<br>and is still better than the 8,956 bytes of a<br>standalone MTC, even if it's a far cry from the 544<br>bytes of an ECDSA cert. But alright. Let's roll with<br>MTCs. What does that mean?
Issuance delay
Clearly, we'll want to use landmark-relative MTCs, but<br>those are only signed in batches, so issuance is...