Split View: PQ 인증서가 아직 안 오는 이유 — ML-DSA 서명 크기, 10kB의 벽, 그리고 Merkle Tree Certificates

Why Post-Quantum Certificates Are Not Here Yet — ML-DSA Signature Size, the 10kB Wall, and Merkle Tree Certificates

• Introduction — Encryption Is Halfway There, Authentication Is Still at the Starting Line
• It All Comes Down to Size — the Numbers FIPS 204 Sets
• Why the Handshake Carries Five Signatures
• The 10kB Wall — Cloudflare's 2021 Measurements
• Merkle Tree Certificates — a Design That Removes Signatures Entirely
• The Conditions Attached to the Number 736 Bytes
• Where Things Stand Now — PLANTS, Chrome, Let's Encrypt
• Objections and Remaining Gaps in This Approach
• So What Should You Actually Do Right Now
• Closing
• References

Introduction — Encryption Is Halfway There, Authentication Is Still at the Starting Line

Over the past several years, the post-quantum cryptography (PQC) story has effectively been a key-exchange story. The logic was simple — an attack that stores today's ciphertext now and decrypts it later with a quantum computer, so-called harvest now, decrypt later (HNDL), is possible, so encryption has to change today. That's why the hybrid key exchange X25519MLKEM768 rolled out quickly in browsers and servers. Cloudflare said that as of October 2025, about 50% of the traffic hitting its edge network is protected against this threat (vendor-measured — the population is traffic reaching Cloudflare's edge, not the internet as a whole).

Authentication is a different story. Forging a signature isn't something you can store and do later — it has to happen while the connection is live. So signatures aren't an HNDL target, and the threat depends on whether a cryptographically relevant quantum computer (CRQC) actually exists. In Let's Encrypt's words, that fact has served as the "comfort" that let authentication be put off.

But the real reason lies elsewhere. Simply swapping in PQ certificates slows the web down. And it slows things down today, as the price of preparing for a threat that hasn't arrived yet. This post verifies the numbers behind that tradeoff from primary sources, then looks at the workaround the industry chose to avoid paying that price.

It All Comes Down to Size — the Numbers FIPS 204 Sets

Let's nail down the numbers first. Table 2 of NIST FIPS 204 specifies the key and signature sizes for ML-DSA in bytes.

Parameter set     Private key   Public key   Signature   (FIPS 204 Table 2)
ML-DSA-44         2560          1312         2420        Security category 2
ML-DSA-65         4032          1952         3309        Security category 3
ML-DSA-87         4896          2592         4627        Security category 5

For comparison: ECDSA P-256, today's most common web signature, is 64 bytes for the signature and 64 bytes for the public key. RSA-2048 is 256 bytes for the signature and 256 bytes for the public key. Ed25519 is a 32-byte key and a 64-byte signature (RFC 8032, the values the MTC draft cites).

That makes ML-DSA-44 roughly 20 times ECDSA P-256. Cloudflare put it as "roughly a 20-fold increase in size." What matters here is that ML-DSA-44 is the smallest option. For reference, the hash-based SLH-DSA (FIPS 205, formerly SPHINCS+) adds 39kB by Cloudflare's measurement and carries a heavy signing/verification compute cost too. Its advantage is that, relying on hashing alone, its security is far better understood — a tradeoff between size and confidence.

Why the Handshake Carries Five Signatures

Knowing the size is 20x on its own doesn't paint the full picture. What matters is how many signatures the handshake carries. Cloudflare's introduction to Merkle Tree Certificates (October 28, 2025, Luke Valenta, Christopher Patton, Vânia Gonçalves, Bas Westerbaan) builds this staircase step by step.

1. If the client already knows the server's public key, one signature is enough. But there are roughly a billion TLS servers on the web, and keys keep changing. Pre-loading every client with every server's public key is impossible. This scalability problem is where PKI design starts.
2. So certificates come in. The CA signs "this public key belongs to this domain." Signature +1, public key +1 → 2 signatures, 1 public key total.
3. Chains today are usually two or more certificates. CAs also have to rotate keys, and it takes time for a new public key to propagate into billions of clients' trust stores. To fill that gap, the old key issues a certificate for the new key and appends it to the end of the chain. Signature +1, public key +1 → 3 signatures, 2 public keys.
4. Finally, Certificate Transparency. Chrome, Safari, and Firefox only accept a certificate if it's logged in at least two trusted logs. Each log attaches one SCT signature. Signature +2 → final total: 5 signatures, 2 public keys.

Cloudflare's own framing captures the situation precisely — every time something in WebPKI needed fixing, one more signature got tacked on, and that strategy worked because classical cryptography was so cheap. Now that bill is coming due.

Multiply FIPS 204's sizes by Cloudflare's count and you get this (below is my own arithmetic combining the two primary sources, not a figure either one published).

Authentication data if everything is swapped for ML-DSA-44:
  5 signatures x 2,420 =  12,100 bytes
  2 public keys x 1,312 =  2,624 bytes
  ------------------------------------
  Total                  14,724 bytes

The same counts with ECDSA P-256:
  5 signatures x 64 + 2 public keys x 64 = 448 bytes
(real chains mix in RSA, so real-world values run higher than this)

The MTC draft itself offers a more conservative calculation too. Even if draft-ietf-tls-trust-anchor-ids shortens the chain by letting clients trust an intermediate certificate directly, it states that just 2 SCTs plus 1 leaf-certificate signature still adds 7,260 bytes of authentication overhead at ML-DSA-44, and 9,927 bytes at ML-DSA-65. In other words, even trimming the chain as short as possible, you're still in the neighborhood of ten thousand bytes.

The 10kB Wall — Cloudflare's 2021 Measurements

So why is ten-thousand-some bytes a problem? From here it's not theory — it's measurement. Cloudflare's Sizing Up Post-Quantum Signatures (Bas Westerbaan, published November 8, 2021) is a large-scale experiment that attached dummy certificates to real connections arriving at Cloudflare's network over the actual internet, and measured the size impact. It's vendor-measured, and the population is real client connections reaching Cloudflare's network.

One background concept is needed. To avoid congestion, TCP sends only a small number of packets at first — usually 10, about 14kB. This is the initial congestion window (initcwnd). Cross that threshold and you add an extra round trip.

The measurement produced two results (as Cloudflare itself summarized in a follow-up post).

• Failure: adding more than 10kB to the existing certificate chain sharply raised failure rates among clients and middleboxes. Spikes appeared in the graph at 10kB and 30kB, meaning some clients or middleboxes can't handle those sizes.
• Delay: adding under 9kB slowed TLS handshake time by about 15%. Cloudflare rated this "tolerable, but not ideal."

There's a commonly misunderstood point worth flagging here. Cloudflare's own initcwnd isn't the standard value of 10 — it's 30 packets. So adding even 35kB stays within the initial congestion window. And yet the median handshake was still 40% slower, and the slowest 10% took 60% longer. This is Cloudflare's conclusion — staying inside the congestion window is nowhere near making the extra data free.

There's a concrete substitution too. Dropping in Dilithium2 (the predecessor to ML-DSA-44) adds about 17kB, which under Cloudflare's 30-packet window produced a 20% median slowdown. And it noted it would expect a 60-80% slowdown under the standard initcwnd of 10 — that's an estimate from Cloudflare, not a measurement.

The browser-side baseline is worth noting too. Chrome caps its TLS handshake time regression budget at 10%, and reported already taking a 4% hit when it rolled out PQ key agreement — the price of adding 1.1kB server-to-client and 1.2kB client-to-server. Cloudflare pointed out that this ratio is proportionally larger than its own "15% at 9kB," and interpreted it as possibly reflecting that uploads are slower than downloads.

Cloudflare's practical conclusion from 2021 came down to one line — the transition would be easiest if 6 signatures and 2 public keys fit within 9kB. The 14,724 bytes calculated above is well outside that target.

One honest caveat: this measurement is from 2021. Both middleboxes and clients may have changed since then, and even Cloudflare, while continuing to cite this data in later posts, hasn't presented a new, updated large-scale measurement.

Merkle Tree Certificates — a Design That Removes Signatures Entirely

With numbers like that, there are three options: (1) accept that it's slower, (2) delay until Q-day gets close, (3) reduce the actual number of signatures the handshake carries.

(2) is dangerous. Migrations always take longer than expected, and in Cloudflare's words, it's "playing with fire." The industry chose (3).

The core idea is this: instead of signing each certificate individually, batch them and sign only the head of a single tree (tree head). Each certificate becomes a leaf of that tree, and internal nodes are hashes of their children. Then what gets sent to the browser as a "certificate" isn't a heavy signature chain, but a lightweight inclusion proof that I'm in this tree. In Google's own words: the CA signs a single tree head representing millions of certificates, and the certificate sent to the browser is just a lightweight inclusion proof against that tree.

For terminology, it's more accurate to follow the definitions in draft-ietf-plants-merkle-tree-certs-05 (July 6, 2026, 100 pages — David Benjamin/Google, Devon O'Brien/Apple, Bas Westerbaan and Luke Valenta/Cloudflare, Filippo Valsorda/Geomys).

• Cosignature: a signature the CA or another cosigner makes over a checkpoint or subtree.
• Landmark: a sparse subset of tree sizes used to pre-distribute trusted subtrees to relying parties.
• Standalone certificate: an inclusion proof into some subtree, plus one or more cosignatures over that subtree.
• Landmark-relative certificate: an optimized certificate that carries only an inclusion proof into a landmark subtree, and no signature at all.

That last item is the heart of the design. If the client already knows the landmark, the server doesn't need to send a signature at all.

There's a bonus too. Certificate Transparency is built into the design. Today's CT is bolted on after the fact — the CA issues, separately logs it, and the SCT signature attesting to that gets tacked onto the handshake. In MTC, a certificate simply cannot exist outside the Merkle tree. In Google's words, it's impossible to issue a certificate without putting it into the public tree. So today's CT security properties come by default, while the SCT overhead riding on the handshake disappears.

The draft also notes gains on the log-operating cost side. Since log entries replace public keys with a hash and carry no signature, log entry size no longer grows in proportion to public-key and signature size. And long-expired entries can be pruned, so log size is set by retention policy rather than the log's lifetime — which meshes with the trend toward shorter certificate lifetimes.

The Conditions Attached to the Number 736 Bytes

The number articles love to quote when introducing MTC is 736 bytes. This number's source isn't a Google or Cloudflare blog post — it's Section 6.5, Size Estimates, of the draft — and it comes with a dense set of conditions attached. Quoting it without the conditions is misleading.

The assumptions the draft states are these.

• The log's hash function is SHA-256.
• Public statistics as of June 9, 2025: roughly 558 million valid certificates from Let's Encrypt alone as a single CA, roughly 2.1 billion total unexpired certificates across CT logs per MerkleTown, and an overall CA issuance rate of roughly 444,000 per hour.
• Assumes a web transitioned to short-lived certificates: a 7-day certificate lifetime, with subscribers renewing at 75% of that lifetime → reissuance every 126 hours → about 4.4 million per hour per CA, roughly 17 million overall.

The calculation follows from these assumptions.

If a landmark is assigned once per hour:
  the subtree contains about 4,400,000 entries
  -> 23 inclusion-proof hashes
  -> 736 bytes, no signature

Standalone certificate (checkpoints taken every 2 seconds):
  the subtree contains about 2,500 entries
  -> 12 inclusion-proof hashes = 384 bytes
  -> plus enough signatures on top to satisfy relying-party requirements

Proof size scales logarithmically:
  32 hashes = 1024 bytes covers up to 2^32 (about 4.3 billion) entries

A comparison the draft draws itself is striking — 736 bytes is smaller than even a single ML-DSA-44 signature (2,420 bytes), and nearly 10 times smaller than the 3 ML-DSA-44 signatures (7,260 bytes) needed to include a PQ SCT. This is where Let's Encrypt's claim comes from — that even while running post-quantum algorithms, this can end up smaller than today's handshake.

One thing needs emphasis, though. This is an estimate built on stated assumptions, not a measurement. The draft itself notes that today's web PKI issuance rate may not represent the web after a transition to short-lived certificates. And 736 bytes applies only to the landmark-relative certificate — that is, only to clients that are up to date. In the draft abstract's own words, this optimization comes at the cost of "applying only to up-to-date relying parties, with older certificates for the rest."

Where Things Stand Now — PLANTS, Chrome, Let's Encrypt

The evidence that this design isn't slideware is the schedule and the code.

IETF. The PLANTS working group (PKI, Logs, And Tree Signatures) has been formed and is active. Its charter states a clear goal — reducing the cost of large post-quantum signatures, in PKI using CT (RFC 6962, RFC 9162), for interactive protocols like TLS (RFC 8446). The charter says size is the main motivation, but that the result should also be usable with classical signatures. The WG draft has reached -05 (July 6, 2026), as seen above.

Chrome. In February 2026, Google laid out its policy in Cultivating a robust and efficient quantum-safe HTTPS. For ecosystem scalability and efficiency, it has no immediate plan to add classical X.509 certificates carrying PQC to the Chrome Root Store. Instead, it's pushing MTC, with a three-phase rollout.

• Phase 1 (in progress): a feasibility study with Cloudflare. In this experiment, every MTC-based connection is backed by a classical, trusted X.509 certificate. Google calls this a "fail safe" — a mechanism meant to measure real performance gains and issuance reliability without putting user connection security or stability at stake.
• Phase 2 (targeting Q1 2027): inviting CT log operators who ran at least one "usable" log in Chrome before February 1, 2026, to bootstrap public MTC infrastructure. At the start of this phase, a new trust store, CQRS (Chrome Quantum-resistant Root Store), and the requirements for an MTC-only root program get finalized. It runs alongside the existing Chrome Root Program, and sites can opt in to downgrade protection.
• Phase 3 (targeting Q3 2027): onboarding additional CAs to CQRS.

Google added that for private PKI (PKI that doesn't go into the Chrome Root Store), it expects to support "classical" X.509 using quantum-resistant algorithms within the year. That means the public web and private PKI are taking separate paths.

Cloudflare. The experiment design is clever. Becoming a proper CA takes years to earn browser trust, so Cloudflare isn't becoming a real CA for this experiment — it mocks the MTCA role. It runs an MTCA on top of Workers, built on a StaticCT log, but publishes an existing certificate issued by a trusted CA alongside every MTC it issues. This is called a bootstrap certificate. When Chrome's infrastructure pulls the MTCA log, it also fetches this bootstrap certificate, checks whether the two match, and only pushes the landmark to Chrome clients when they do. In short, Cloudflare is only "re-encoding" existing certificates (whose domain a trusted CA has already validated) as MTC, and Chrome keeps Cloudflare honest via CT. It's a way to test the design without changing any trust relationships. The target is a subset of free customers with enough traffic to be useful for measurement, and Chrome controls the rollout pace.

Let's Encrypt. On June 3, 2026, Andrew Gabbitas wrote A Post-Quantum Future for Let's Encrypt, announcing MTC as its chosen path. The goal is a staging environment issuing MTC by the end of 2026, and a production-ready environment in 2027. Let's Encrypt is clear that this isn't a small undertaking — the issuance infrastructure, the ACME protocol subscribers use, revocation and operational tooling, and the transparency-log infrastructure that MTC absorbs, all have to change across the stack. The asset it points to as a foundation is the CT log it has run since 2019 — that log is an append-only Merkle tree, the same data structure as MTC.

Adjacent standards and implementations. The convention for using ML-DSA in X.509 has already shipped as RFC 9881 (October 2025, Standards Track), and the TLS 1.3 side, draft-ietf-tls-mldsa, is in progress (at -05 as of July 8, 2026). Language runtimes are following too — Go is adding a new crypto/mldsa package implementing FIPS 204's ML-DSA, with crypto/x509 supporting ML-DSA keys and signatures, and crypto/tls supporting the MLDSA44/MLDSA65/MLDSA87 SignatureSchemes in TLS 1.3. Note, though, this is per the Go 1.27 release notes, and 1.27 hasn't shipped yet (the current stable is 1.26.x). Let's Encrypt cites this as "a signal that post-quantum signatures are becoming practical infrastructure."

Objections and Remaining Gaps in This Approach

By this point, MTC can look like a clean win. Let's be honest and look at the other side too. Interestingly, a good number of the objections below were written down by Cloudflare itself, in its own posts.

There's pushback on whether obsessing over handshake time is even the right frame. Two arguments back this up. First, with session resumption, you don't need to resend the certificate on every connection. Second, the data volume a typical website visit transfers dwarfs the few extra kB a PQ certificate adds. The example Cloudflare itself cites is a 2024 simulation paper by Amazon researchers, arguing that a typical connection sends multiple requests and transfers hundreds of kB, so handshake degradation gets buried in the noise for such connections. For reference, Cloudflare itself has also written that the TLS handshake is just one step accounting for roughly 5-20% of the long chain leading up to a rendered page.

MTC's benefit only shows up when the client is up to date. This is exactly the question Cloudflare wants answered from this experiment — "how many clients will actually stay up to date?" MTC's lifetime is expected to run around a week, and if the freshest landmark a client holds is older than that, the server has to fall back to a larger certificate. How often that fallback fires is central to tuning the protocol's parameters, and there's no answer yet. The real ratio between the rosy 736-byte number and standalone fallbacks won't be known until this experiment concludes.

A new trust store isn't free. CQRS is an MTC-only root program, separate from the existing Chrome Root Store. It's technically clean, but it also splits the ecosystem in two and requires CAs to go through a new onboarding path. The fact that Google itself calls this a "risk-managed transition" and says it will run both tracks in parallel also signals just how heavy the operational burden is.

All the timelines are predictions. And nobody knows the root of those predictions — Q-day. This is a place to be especially careful. Let's Encrypt wrote that "the timeline has moved up this year," noting that Google narrowing its CRQC-arrival estimate is why it announced migrating its own services by 2029, with Cloudflare following. This is those companies' prediction and declaration — not a fact that quantum computers are arriving in 2029.

The regulatory timeline is a draft too. The commonly cited NIST transition guidance, IR 8547, is an Initial Public Draft published November 12, 2024, and its comment period closed January 10, 2025. Its content is also more nuanced than the usual summary. The draft's table splits signature algorithm families by security strength: 112-bit strength (like RSA-2048) is marked deprecated after 2030, disallowed after 2035, while 128-bit and above is marked disallowed after 2035. In other words, a summary like "RSA and ECC all die by 2030" is cruder than what the draft's table actually says. And as Let's Encrypt points out, this kind of guidance doesn't directly bind the public web PKI — it does, however, push the vendors, libraries, and standards bodies the web PKI relies on to move on that clock. NSA's CNSA 2.0 has set a 2030-2035 timeline for national security systems since 2022, and the EU roadmap targets late 2030 for high-risk systems and 2035 for broad migration.

So What Should You Actually Do Right Now

This post's practical conclusion is a bit anticlimactic. What server operators need to act on right now is key exchange, not certificates.

That's exactly the recommendation Let's Encrypt left at the end of its post. The more urgent issue for the broader internet community is post-quantum encryption, because a TLS connection without PQ key exchange can be harvested now and decrypted later. If you run a server, make sure it supports hybrid PQ key exchange (X25519MLKEM768). Major browsers and OSes already support it, and in their words, turning it on server-side is the single highest-leverage thing you can do this year.

On the certificate side, standardization isn't finished, so there are three things you can do right now.

• Track. If you maintain an ACME client or run an ACME-based certificate pipeline, now is the time to watch the PLANTS working group and the mtcs@chromium.org mailing list. Let's Encrypt recommends this directly — some of the coming changes will require client-side support, and the ecosystem only works if clients are ready by the time issuance is ready.
• Inventory and crypto agility. No timeline means anything if you don't know where you're using which signatures. The public web PKI and private PKI take different paths — private PKI can move first to classical X.509 using PQC, and Chrome has said it will support that use case too.
• Accept that nothing changes right now. In Let's Encrypt's words, nothing is different today. Existing certificates get issued and renewed exactly as they always have.

That doesn't mean there's no need to hurry. It's that certificates aren't where the hurrying belongs.

Closing

To sum up: in the post-quantum transition, encryption is already about halfway there, and authentication has been stuck — not for cryptographic reasons, but for reasons of size. Multiply the 2,420-byte ML-DSA-44 signature set by FIPS 204 by the 5 signatures and 2 public keys today's handshake carries, and you land in the mid-14,000-byte range — well outside the wall Cloudflare measured in 2021: failure rates spike past 10kB, and even under 9kB you take a 15% slowdown.

Merkle Tree Certificates solves this not with a new algorithm but with structure — batch certificates and sign only a single tree head, carry just an inclusion proof over the handshake, and build CT into the issuance process itself so the SCT-signature overhead disappears. By the draft's estimate, that comes to 736 bytes and zero signatures for an up-to-date client. That's where the claim comes from that going post-quantum can actually end up smaller than today.

But it comes with conditions. That number is an estimate built on assumptions — a 7-day lifetime, hourly landmarks — and it only holds when the client is holding a fresh landmark; otherwise it falls back to something bigger. How often that fallback happens is exactly what Chrome and Cloudflare are measuring right now with real traffic, and until that answer is in, 736 bytes is a target, not a measurement. The standard is at draft -05, Let's Encrypt's production target is 2027, and Chrome's new root store is planned for Q3 2027. It's all still a plan.

The lesson an engineer should take from this is somewhat general. WebPKI tacking on one more signature every time something needed fixing over the past 20 years was only possible because classical cryptography was cheap, and that accumulated convenience came due the moment the algorithm got 20 times bigger. When size goes up 20x, the only way out is to cut the count by 20x. That's exactly what MTC does.

References

• FIPS 204 — Module-Lattice-Based Digital Signature Standard (NIST; ML-DSA sizes are in Table 2)
• draft-ietf-plants-merkle-tree-certs-05 — Merkle Tree Certificates (IETF, 2026-07-06; size estimates in Section 6.5)
• IETF PLANTS working group — PKI, Logs, And Tree Signatures
• Sizing Up Post-Quantum Signatures (Cloudflare, Bas Westerbaan, 2021-11-08 — the original source of the 10kB/9kB measurements)
• A look at the latest post-quantum signature standardization candidates (Cloudflare — measurement recap and the Amazon-side objection)
• Keeping the Internet fast and secure: introducing Merkle Tree Certificates (Cloudflare, 2025-10-28 — the five-signature staircase and the bootstrap certificate)
• Cultivating a robust and efficient quantum-safe HTTPS (Google Security Blog, 2026-02 — Chrome's three-phase plan and CQRS)
• A Post-Quantum Future for Let's Encrypt (2026-06-03 — staging by end of 2026, production in 2027)
• RFC 9881 — X.509 Algorithm Identifiers for ML-DSA (2025-10, Standards Track)
• NIST IR 8547 (Initial Public Draft) — Transition to Post-Quantum Cryptography Standards
• Go 1.27 release notes (unreleased) — addition of the crypto/mldsa package