Merkle Tree Certificates: Solving the Post-Quantum Certificate Problem in TLS
Benjamin Rothenberger (consultant · Zühlke)
Swiss Cyber Storm 2026 · Day 1 · Scenario
Overview
In this insightful talk from Swiss Cyber Storm, Benjamin Rothenberger, a consultant at Zühlke with a PhD from ETH Zurich, addresses one of the most pressing challenges facing the internet's security infrastructure in the era of quantum computing: the problem of post-quantum cryptography (PQC) for TLS authentication. While quantum-resistant encryption schemes (Key Encapsulation Mechanisms or KEMs) are making significant progress and are already being deployed, the transition to quantum-safe digital signatures for authentication presents a far more complex hurdle due primarily to their substantially larger size. Rothenberger argues that while PQC signatures are technically "ready to be used," the internet's current architecture cannot afford them.

Key moments
- 6:00 Post-quantum signatures' massive size problem in TLS
- 10:00 Understanding Merkle trees: hashing certificates into a log
- 14:00 Verifying certificates with Merkle tree inclusion proofs
- 16:00 Landmark optimization: offloading signed checkpoints for efficiency
- 20:00 Merkle tree certificates: fundamental changes and ecosystem challenges
- 23:00 Chrome, Let's Encrypt, Apple adopting Merkle tree certificates
- 30:00 Why not just fix TCP? The fundamental problem explained
Merkle Tree Certificates: Solving the Post-Quantum Certificate Problem in TLS
Speakers: Benjamin Rothenberger, Consultant, Zühlke
Conference: Swiss Cyber Storm
YouTube: https://www.youtube.com/watch?v=xcEw9otFUVY
Overview
In this insightful talk from Swiss Cyber Storm, Benjamin Rothenberger, a consultant at Zühlke with a PhD from ETH Zurich, addresses one of the most pressing challenges facing the internet's security infrastructure in the era of quantum computing: the problem of post-quantum cryptography (PQC) for TLS authentication. While quantum-resistant encryption schemes (Key Encapsulation Mechanisms or KEMs) are making significant progress and are already being deployed, the transition to quantum-safe digital signatures for authentication presents a far more complex hurdle due primarily to their substantially larger size. Rothenberger argues that while PQC signatures are technically "ready to be used," the internet's current architecture cannot afford them.
The core of Rothenberger's presentation introduces Merkle Tree Certificates (MTCs) as a groundbreaking solution. MTCs propose a fundamental shift in how the Web Public Key Infrastructure (PKI) operates, moving away from individual certificate signing to a model where Certificate Authorities (CAs) sign logs of certificates. This innovative approach aims to drastically reduce the data transmitted during a TLS handshake, particularly for authentication, by leveraging out-of-band transmission of trusted information. The talk highlights the urgency of this problem, the technical intricacies of MTCs, and the significant implications for the future of internet security and its underlying economics.
Background
▶ Watch: Post-quantum signatures' massive size problem in TLS (6:00)
The advent of quantum computers poses an existential threat to much of our modern cryptographic infrastructure. As Rothenberger explains, while symmetric ciphers like AES can largely be defended by merely doubling key sizes (e.g., from AES-128 to AES-256), asymmetric cryptography is fundamentally broken by Shor's algorithm. This includes widely used algorithms like RSA and Elliptic Curve Cryptography (ECC), which underpin both confidentiality and authentication in protocols like TLS.
Within TLS, two primary cryptographic problems are addressed: confidentiality and authentication. For confidentiality, the threat is immediate via "harvest now, decrypt later" attacks, where encrypted traffic today is recorded with the intent of decrypting it once quantum computers are available. Fortunately, a robust solution exists in the form of Key Encapsulation Mechanisms (KEMs). These are already supported by modern browsers and web servers, with Rothenberger noting that roughly 67% of human traffic to Cloudflare already utilizes a hybrid cipher combining classical and post-quantum KEMs. The overhead for KEMs is manageable, adding approximately 1 kilobyte in each direction to the handshake.
However, the picture for authentication is far more challenging. While not subject to "harvest now, decrypt later" (as you can only attack the system once a quantum computer is available), there is currently no readily available PQC solution that seamlessly integrates into the existing Web PKI. The migration is immensely complex, requiring changes across the entire ecosystem, from root CAs to programs and logs. Crucially, the overhead introduced by current PQC signatures becomes a significant problem.
Rothenberger details the components of a typical TLS handshake related to authentication. In the third step of the handshake, the server transmits:
- The leaf key (public key securing the connection).
- The intermediate key (public key verifying the leaf).
- Two chain signatures (root CA signing the intermediate CA, and intermediate CA signing the leaf).
- Two Signed Certificate Timestamps (SCTs), which provide evidence that the certificate has been published in at least two Certificate Transparency (CT) logs (each SCT involves a signature).
- A certificate verify signature over the entire handshake conducted so far.
In total, this amounts to the transmission of two public keys and five signatures. Using classical ECC, this data totals approximately 450 bytes. This is a negligible amount, allowing for efficient handshakes. However, when plugging in PQC algorithms like Dilithium (one of the leading PQC signature schemes being standardized by NIST), the picture changes dramatically. The signature and public key sizes for Dilithium are significantly larger, inflating the authentication data to a staggering 14.7 kilobytes.
This increase has critical implications:
- TCP Congestion Window: The initial TCP congestion window is typically 14.6 kilobytes. Exceeding this means the connection cannot fully utilize the initial window, leading to delays and slower connection establishment.
- QUIC Amplification Protection: For transport protocols like QUIC (which uses UDP), there's an amplification protection mechanism that prevents the server from sending more than three times the data received from the client in the initial handshake. Large PQC signatures can trigger this protection, further slowing down the connection.
While other PQC signature algorithms exist, such as Falcon, they also present trade-offs. Falcon offers smaller signature and public key sizes compared to Dilithium but is computationally more complex and costly. Furthermore, Falcon is not yet fully standardized, whereas Dilithium is considered "the best we have" in terms of readiness and standardization progress. The conclusion is clear: PQC signatures are technically ready, but their sheer size makes them economically unviable for the current internet's TLS authentication model.
Key Findings
▶ Watch: Verifying certificates with Merkle tree inclusion proofs (14:00)
The central problem identified by Rothenberger is that post-quantum signatures, while cryptographically sound, are simply too large for the existing TLS handshake and the broader internet ecosystem. Their biggest weakness is their size, which leads to performance degradation and breaks fundamental assumptions about network efficiency.
The surprising fix proposed is not to make the signatures smaller, but to fundamentally alter how certificates are managed and validated. The core finding is that Merkle Tree Certificates (MTCs) can effectively solve the size issue by removing the bulk of signature data from the TLS handshake itself. Specifically, the goal is to eliminate four out of the five signatures currently transmitted.
This is achieved by shifting the paradigm of certificate issuance and validation:
- From individual certificate signing to log signing: Instead of a CA directly signing each certificate, the CA inserts certificates into a continuously growing issuance log (structured as a Merkle tree) and then signs the root of this log at regular intervals.
- From certificate chain validation to inclusion proof: Clients no longer validate a chain of individual signatures but instead verify an inclusion proof that demonstrates a specific certificate is part of a CA's cryptographically signed log.
- Leveraging client trust and out-of-band transmission: By having clients pre-fetch and store trusted "snapshots" of CA logs (landmarks), the need to transmit large signatures or extensive proof paths during every TLS handshake is significantly reduced.
This approach represents a fundamental change in the Web PKI, allowing the internet to adopt post-quantum authentication without incurring crippling performance penalties.
Technical Deep Dive
▶ Watch: Landmark optimization: offloading signed checkpoints for efficiency (16:00)
The solution proposed by Benjamin Rothenberger hinges on Merkle Tree Certificates (MTCs), a concept that re-architects the Web PKI to accommodate the large sizes of post-quantum signatures. Merkle trees themselves are not new, having been around for over 30 years in cryptography, but their application to the PKI in this manner is novel.
At its core, a Merkle tree is a hash tree where every leaf node is a hash of a data block (in this case, a certificate), and every non-leaf node is a hash of its child nodes. This process continues up the tree until a single root hash is produced.
- Hashing Certificates: When a CA issues a certificate for
alice.comorbob.com, the first step is to hash each certificate using a strong cryptographic hash function like SHA-256. These become the leaf nodes of the tree. - Building Intermediate Nodes: Pairs of leaf hashes are then concatenated and hashed again to form intermediate nodes. This process is repeated, combining intermediate nodes, until a single top-level hash, the root hash, is generated.
- Checkpoints: The Merkle tree continuously grows as new certificates are issued. Periodically, the CA creates a checkpoint, which consists of the current tree size and the root hash of the tree at that moment. This checkpoint is then signed by the CA's post-quantum signature. The specification envisions CAs signing these roots roughly every 2 seconds, effectively creating a verifiable, immutable record of all certificates issued up to that point. One significant advantage is that a single CA signature on a checkpoint can cover thousands or millions of individual certificates within the tree.
The crucial element for client-side validation is the inclusion proof. Instead of receiving a full chain of signatures, a client verifies that its specific leaf certificate is indeed part of a known, signed Merkle tree checkpoint.
- Client-side Hashing: The client first hashes its own leaf certificate (e.g., for
alice.com). - Sibling Nodes: To reconstruct the path to the root, the client needs specific sibling nodes (hashes) from the server. For example, if the client knows its own hash (blue dot) and receives the hash of its sibling (green dot), it can compute their parent hash. This process is repeated, requesting the necessary sibling hashes at each level, until the client can compute the root hash.
- Verification: If the computed root hash matches a known, trusted, and signed checkpoint root hash, the inclusion proof is successful, verifying the certificate's authenticity. For a tree with 16 entries, this process typically requires transmitting four sibling hashes as part of the inclusion proof.
The initial MTC structure would include the leaf certificate, the necessary sibling hashes for the inclusion proof, and the signed checkpoint at the root. While this reduces the number of signatures, the signed checkpoint itself can still be large with PQC signatures. To further optimize this, Rothenberger introduces Landmarks.
Landmarks are an ingenious optimization designed to completely remove the signed root checkpoint from the TLS handshake for online clients.
- Periodic Snapshots: Instead of relying solely on the continuously growing global Merkle tree, CAs compute and sign "landmarks" at fixed time intervals, for example, every hour. A landmark represents the root hash of a sub-tree containing all certificates issued within that specific hour (e.g., Landmark 40 for certificates issued in hour 40).
- Out-of-Band Transmission: These signed landmarks are then transmitted to clients via an out-of-band transmission channel. The CA provides these landmarks through an authenticated update mechanism (the exact details of which are still a "moving part" in the specification, as noted in the Q&A, but could resemble public repositories similar to CRLs).
- Client Trust Store: Browsers and clients receive these authenticated landmarks and store them locally in their trust store.
- Landmark-Relative Proof: When a client initiates a TLS handshake, it can perform a landmark-relative proof. Instead of proving inclusion to the massive, globally signed Merkle tree, it only needs to prove inclusion to a much smaller, locally stored and trusted landmark. This means the server only needs to send the leaf certificate and the small set of sibling hashes required for the landmark-relative inclusion proof.
This optimization yields two types of certificates:
- Standalone Certificate: This is a full certificate, including the CA's post-quantum signature and co-signatures, proving inclusion to the entire Merkle tree. It's comparable in size to a traditional PQC certificate and serves as a fallback for offline clients or those unable to fetch landmarks.
- Landmark-Relative Certificate: This is the highly optimized version. For online clients who have successfully fetched landmarks, the TLS handshake only needs to transmit the leaf certificate and the Merkle inclusion proof (the green sibling dots). Crucially, no signatures are transmitted over the wire for the landmark itself, as the landmark is already trusted locally. This brings the total authentication data down to approximately 4.5 kilobytes, well within the initial TCP congestion window and avoiding issues with QUIC amplification protection.
The adoption of MTCs fundamentally alters the Web PKI:
- Logging: Instead of relying on a few large, centralized CT logs, each CA will need to operate its own Merkle tree-based log.
- Signing: The CA no longer signs individual certificates but rather the root of its log (the checkpoints). One signature secures many certificates.
- Validation: Traditional chain validation is replaced by inclusion path validation.
Despite the significant benefits, MTCs introduce new complexities:
- Two Certificates per Endpoint: Servers may need to store both standalone and landmark-relative certificates for each endpoint to cater to all client types.
- Hourly Updates: Clients must regularly (e.g., hourly) fetch landmark updates to benefit from the optimization.
- Browser State: Each CA will contribute to the browser's local state, with an example given of 11 kilobytes per CA for 7-day certificates. With potentially many CAs, this could accumulate.
- Early Stage Drafts: While the core MTC concept is stable, related specifications (e.g., for naming) are still in early draft stages.
- Ecosystem Complexity: The overall ecosystem becomes more complex with more "moving parts," including the authenticated update channel for landmarks and the need for a reliable time source for checkpoints and landmarks.
Demo / Proof of Concept
▶ Watch: Chrome, Let's Encrypt, Apple adopting Merkle tree certificates (23:00)
The talk did not feature a live demonstration of Merkle Tree Certificates in action. However, Benjamin Rothenberger highlighted significant real-world movement and ongoing experiments that serve as a strong proof of concept for the viability and potential of MTCs.
Early in 2023, Chrome and Cloudflare announced a large-scale experiment involving MTCs. In this collaboration, Chrome provides the necessary browser support, while Cloudflare acts as a "meta CA," re-encoding existing certificates into the MTC format for testing purposes. This experiment is crucial for evaluating MTCs' performance, compatibility, and integration into the existing internet infrastructure. Furthermore, Let's Encrypt, which issues over half of all public certificates, has publicly named MTCs as their preferred way forward for post-quantum authentication, a highly significant endorsement. More recently, Apple has also stated its intention to use MTCs for server authentication. These developments underscore the industry's commitment to exploring and implementing MTCs as the solution to the post-quantum certificate problem. The plan is to begin bootstrapping the entire MTC ecosystem, including logs and mirrors, in early 2024.
Defensive Implications
▶ Watch: Why not just fix TCP? The fundamental problem explained (30:00)
The impending quantum threat necessitates a proactive and fundamental re-evaluation of current cryptographic practices, especially for authentication in TLS. Merkle Tree Certificates offer a crucial pathway for defenders to transition to post-quantum authentication without incurring crippling performance costs.
For Certificate Authorities (CAs), the implications are profound. They will need to transition from signing individual certificates to operating and cryptographically signing their own Merkle tree-based issuance logs. This requires significant architectural changes to their infrastructure, including new log management systems and processes for generating and distributing signed checkpoints and landmarks. The question of how to provide an "authenticated update" channel for landmarks, which is currently an open specification point, will be a critical design decision for CAs to ensure the integrity and trustworthiness of these out-of-band transmissions.
Browser vendors and client software developers must integrate support for MTCs. This includes implementing the logic for verifying Merkle inclusion proofs and, crucially, developing robust mechanisms for fetching, authenticating, and storing landmarks in the client's trust store. The need for hourly landmark updates implies a continuous background process for online clients, which must be efficient and secure.
Server operators will likely need to manage and serve two types of certificates per endpoint: standalone certificates for broad compatibility (especially for offline clients or those not supporting landmarks) and landmark-relative certificates for optimized online performance. This adds a layer of complexity to certificate management and deployment. The shift towards potentially shorter-lived certificates (e.g., 7-day lifetimes, as mentioned in the Q&A as an example) could also become a more widespread practice, demanding more automated certificate management solutions.
Overall, the adoption of MTCs implies a distributed, log-centric PKI model that moves significant cryptographic overhead out of the real-time TLS handshake. Defenders should prepare for:
- Architectural Shifts: Expect fundamental changes in how certificates are issued, validated, and managed across the internet.
- New Trust Models: Understanding and securing the new "out-of-band" channels for landmark updates will be paramount.
- Increased Client-Side State: Be aware of the increased storage requirements on client devices due to multiple CA landmarks.
- Ecosystem Collaboration: The success of MTCs hinges on widespread adoption and collaboration between CAs, browser vendors, and other ecosystem participants. Monitoring the progress of industry experiments (Chrome, Cloudflare) and commitments (Let's Encrypt, Apple) is essential for planning future deployments.
Key Takeaways
- PQC Signature Size is a Critical Bottleneck: While post-quantum signatures are cryptographically ready, their large size (e.g., 14.7 KB for Dilithium authentication data) significantly exceeds current TLS handshake limits and network performance assumptions, such as the 14.6 KB TCP initial congestion window.
- Merkle Tree Certificates (MTCs) Offer a Solution: MTCs address the size problem by fundamentally re-architecting the Web PKI to move authentication data out of the real-time TLS handshake, reducing the number of on-the-wire signatures from five to one (the certificate verify) plus an inclusion proof.
- Paradigm Shift in Web PKI: MTCs change how certificates are issued and validated: CAs sign logs of certificates (Merkle tree roots) rather than individual certificates, and clients validate using inclusion proofs instead of traditional certificate chains.
- Landmarks Enable Significant Optimization: The "landmarks" mechanism allows clients to pre-fetch and store signed snapshots of CA logs out-of-band. This enables "landmark-relative proofs," reducing the handshake authentication data to approximately 4.5 KB for online clients, making PQC authentication viable for the internet's scale.
- New Ecosystem Complexities Introduced: While solving the size problem, MTCs introduce new challenges, including the need for two certificate types per endpoint, hourly landmark updates for clients, increased browser state (e.g., 11 KB per CA), and a more complex ecosystem with new moving parts like authenticated update channels.
- Industry Adoption is Gaining Momentum: MTCs are not yet ready for widespread deployment but are undergoing significant experimentation and endorsement from key players, including Chrome, Cloudflare, Let's Encrypt, and Apple, with ecosystem bootstrapping planned for early next year.
About the Speaker(s)
Benjamin Rothenberger holds a PhD from ETH Zurich and works as a consultant for Zühlke. His expertise lies at the intersection of cryptography, security, and internet protocols, as demonstrated by his detailed exploration of post-quantum challenges and innovative solutions like Merkle Tree Certificates.
Reviews
Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT
PQC signatures are a slow-moving trainwreck for network engineering because algorithms like Dilithium blow out the TCP initial congestion window. Rothenberger breaks down the industry's escape hatch: Merkle Tree Certificates. It's a necessary, sobering look at how we're going to have to rip out and replace the entire WebPKI just to keep TLS handshakes from choking.
Heather Calloway (CISO) — MUST SEE
A mandatory look at how post-quantum cryptography will actually be deployed without breaking internet routing. The shift to Merkle Tree Certificates will fundamentally alter Web PKI, and infrastructure leaders need to understand how this impacts enterprise TLS inspection and client trust updates.