Welcome to LWN.net
The following subscription-only content has been made available to you by an LWN subscriber. Thousands of subscribers depend on LWN for the best news from the Linux and free software communities. If you enjoy this article, please consider subscribing to LWN. Thank you for visiting LWN.net!
There has been ongoing discussion in the Internet Engineering Task Force (IETF) about how to protect internet traffic against future quantum computers. So far, that work has focused on key exchange as the most urgent problem; now, a new IETF working group is looking at adopting post-quantum cryptography for authentication and certificate transparency as well. The main challenge to doing so is the increased size of certificates — around 40 times larger. The techniques that the working group is investigating to reduce that overhead could have efficiency benefits for traditional certificates as well.
Authentication
When a browser connects to LWN.net, it first establishes an ephemeral encryption key to protect the session. This is key exchange, and some browsers and servers are already using the post-quantum cryptography standardized in 2024 to avoid "store now, decrypt later" attacks. Attacks of this kind store encrypted traffic for later, in the hope that future quantum computers will be able to break the key-exchange mechanisms used. The possibility of these kinds of attacks makes it important to deploy quantum-resistant key-exchange mechanisms well in advance of quantum computers becoming practically usable.
Next, the server provides the browser with a certificate that proves it actually is LWN.net — authenticating the connection. That certificate is made up of a chain of signatures, where each signature comes from a "more trusted" organization, and verifies that the next public key in the list is valid. In our case, this means that the server will send three signatures to the browser: one from LWN.net, one from Let's Encrypt, and one from the Internet Security Research Group's (ISRG) X1 Root certificate. With traditional cryptography, this certificate is approximately 3.5KB, which is roughly one third of the entire LWN front page's HTML content, after compression. These signatures aren't subject to "store now, decrypt later" attacks in the same way encryption keys are, because compromising an authentication key later doesn't impact the correctness of the connection now. Therefore, while key-exchange mechanisms need to defend against future quantum computers to keep communications private, authentication mechanisms only need to defend against current computers.
Depending on the algorithm in question, post-quantum cryptography can produce signatures much larger than comparable traditional algorithms. ML-DSA-44, which is a standardized post-quantum signature scheme thought to have security similar to Ed25519 signatures, produces signatures 37 times larger. Naively adopting post-quantum signatures for authentication could cause certificate chains to take up more data than the actual content of the web site in question, at least for small, text-heavy web sites like LWN. To ensure that certificate authorities are issuing certificates according to their stated policies, many certificates also include signatures from certificate-transparency logs, which publish a list of all certificates being issued. Browsers will typically refuse to trust a certificate authority that does not participate in certificate transparency, since it is much harder to tell if the certificate authority is issuing certificates that it shouldn't. The extra bandwidth overhead that would be incurred by a direct switch to post-quantum signatures for authentication would have a measurable impact on the overall latency of connections.
Logging
The solution that the new working group (called "PKI, Logs, and Tree Signatures" or PLANTS) has been discussing inverts the relationship between signatures from certificate authorities and the transparency logs. Currently, a certificate authority first creates a certificate, then logs it in a certificate-transparency log, and then optionally includes the signature from the log in the certificate as a piece of additional information. This is, in some sense, redundant: the information that the certificate is valid is already present in the certificate-transparency log, so why send the client any information other than proof that it appears in the log?
The mechanism PLANTS proposes would have each certificate authority maintain its own append-only issuance log, containing a list of every certificate it has issued. The same organizations that run certificate-transparency logs today would monitor and mirror each certificate authority's log to ensure compliance. They primarily check that the log is actually append-only, so that a certificate authority can't backdate changes to issued certificates. That way, if there is a security problem caused by a misbehaving certificate authority it will be easy to prove that and revoke trust in the authority. Instead of having a chain of signatures in a certificate to represent some transitive relationship between a certificate authority and a root of trust, the third-party observers would add their signatures to a certificate authority's log as they validate it. A browser can choose its own criteria for which third-party observers it trusts, and whether it requires a quorum of them before accepting the state of an issuance log.
The certificate seen by the client would therefore no longer be a chain of signatures leading back to a root of trust: it would be a set of signatures from the certificate authority and any relevant observers attesting to the state of the issuance log, plus a proof that the web server's public key was included in the issuance log. This constitutes what PLANTS calls a "full" certificate. For an individual web site, a full certificate doesn't decrease the number of needed signatures; but since the issuance logs are append-only, if a browser has already verified the issuance log for a certificate authority up to some checkpoint, it doesn't need to see the signatures for that checkpoint again. Instead, it can ask the server to just send the proof that the server's public key appeared in the log prior to that point — a "signatureless" certificate that should be substantially smaller.
Merkle trees
Those proofs use Merkle trees, a cryptographic commitment scheme which uses a small number of hashes to show that a leaf node belongs to a binary tree. That way, a certificate authority can batch up a large number of certificates into a single tree that only needs to be signed once. The overall number of signatures to be made and verified becomes independent of the number of issued certificates. The idea is that each internal node of the tree stores the hash of its children, all of the way up to the root.
![[A diagram of a Merkle tree]](https://static.lwn.net/images/2026/merkle-tree.png "A diagram of a Merkle tree")
To prove that a leaf node (such as node 10, above) belongs to a tree with a given root node, it suffices to provide the hashes of the other nodes that are "adjacent" to the path from the leaf to the root (nodes [8,10), 11, and 12). This lets a verifier reconstruct what the root hash would be if 10 were included, and then check that this matches what the root hash actually is. In the above example, the browser would calculate the hash of 10, then the hash of [10,12), then the hash of [8,12), before finally calculating the root hash and ensuring that it matches. The number of additional hashes to provide grows logarithmically with the size of the tree. And, since cryptographic hashes aren't vulnerable to the same kinds of quantum attacks as public-key cryptography, the size of a Merkle inclusion proof like this doesn't change when switching to post-quantum cryptography.
Let's Encrypt issues around six million certificates per day (although that number is expected to go up as the standardized certificate lifetime goes down over the next several years). If it adopted the new system and created a new checkpoint every minute (meaning that a server could obtain a full certificate right away, but would need to wait up to one minute to obtain a signatureless certificate), each certificate would need to include twelve hashes (totaling 384 bytes for SHA-256 hashes). That is only 16% the size of a single ML-DSA-44 signature. Of course, servers will ideally have both: a full certificate for clients that have not seen a recent checkpoint, and a signatureless certificate for clients that have. The full certificate will be significantly larger than current certificates (around 133KB using ML-DSA-44), but it hopefully only needs to be used by a small fraction of connections.
To prevent an issuance log from growing without bound, older entries are periodically pruned as they expire. This might seem to be at odds with the append-only nature of an issuance log, but since expired certificates shouldn't validate correctly anyway, the certificate authority can delete the corresponding leaf nodes and any internal nodes that are therefore no longer usable in actual proofs. The tree maintains the same conceptual size, but the on-disk storage requirements remain proportional to the number of active certificates.
Revoking mistakenly issued certificates, which don't have the decency to expire at known times, is a little more complicated: along with the issuance log, a certificate authority also maintains a set of revoked certificates. This set of revocations is also covered by the signatures of each checkpoint, so a browser will obtain an updated set of certificate revocations every time it validates a full certificate from a given certificate authority.
Adoption
The PLANTS working group is still in the early stages of the standardization process — a draft standard exists, but it has not yet been proposed for standardization, and probably won't be within the next year, since several details remain to be worked out. Despite that, Google has announced a plan to evaluate the performance impacts of Merkle-tree-based certificates in Chrome, and to deploy an experimental post-quantum certificate-authority system based on the PLANTS draft by the end of 2027. Most likely, certificate authorities, server operators, and users won't need to update any of their configurations until 2029 or 2030.
The key question Google hopes to answer, which will impact the usability of the protocol, is whether clients will actually stay up-to-date enough (by occasionally verifying a full certificate) to benefit from signatureless certificates on average. The whole protocol only provides a bandwidth and latency advantage if actual browsers visit enough distinct web sites with certificates issued by the same certificate authority. Over the next several months, the Google Chrome team will hopefully provide empirical data on that question. Users of non-Chrome browsers will go unmeasured, at least for now. Hopefully other browser projects will either join the experiment, or have browsing patterns that are statistically similar enough to Chrome's userbase to draw reasonable conclusions.
Changes in web infrastructure often take a significant amount of time. Between running experiments, standardizing the protocol, and rolling out the changes to certificate authorities and browsers, it may be a long time before we see real connections authenticated with post-quantum cryptography. Still, even the most pro-quantum-computing estimates suggest that the system will be in place before quantum computers can pose a real threat to the security of authentication. In a world that is increasingly hectic, it's nice to occasionally have a security concern that is handled well before it becomes an actual problem.