Cloudflare is teaming up with Google on streamlining quantum security for the web.

According to a blog published on Cloudflare’s website, the two firms are tackling post-quantum cryptography (PQC) for the internet with the use of Merkle Tree Certificates (MTCs) to reduce the number of public keys and signatures needed to authenticate PQC protections.

PQC algorithms are being increasingly used across the network to safeguard data from the threat of harvest-now, decrypt-later attacks, including on the browser level. These attacks involve the hoarding of encrypted data in preparation for when large-scale quantum computers become available.

Recent solutions from Cisco, Palo Alto Networks, and Nokia have addressed the issue, on the assumption that "Q-Day" – when a quantum computer becomes powerful enough to break encryptions – is three to six years away.

Cloudflare noted that these tools “don’t bring any security benefit before Q-Day … but they do degrade performance. We could sit and wait until Q-day [but] migrations always take longer than expected, and by waiting we risk the security and privacy of the internet.”

The web giant added such new algorithms are lengthy by nature, with the security signature for the ML-DSA-44 algorithm being 2,420 bytes long, with its public keys numbering 1,312 bytes long.

This also has an impact on a server's TLS certificate, “adding up to tens-of-kilobytes of overhead” per the handshake between request and server, with a noticeable impact on the TLS performance.

“It's clear that we must find a way to make post-quantum certificates cheap enough to deploy today by default for everyone – not just those that can afford it,” Cloudflare's blog post states.

The firm also identified how one billion TLS servers means it’s “unrealistic to provision every client with the public key of every server.”

In the current setup of Web PKI (public key infrastructure), a security chain usually consists of two or more safety certificates rather than just one, which are authorized by a certification authority (CA) whose public key is already known to the client.

As CAs sometimes need to rotate their keys in the same manner as servers, requiring billions of clients to refresh their trust stores, the CA has to sometimes use the old key to issue a certificate for the new key and affix this certificate to the end of the security chain.

This results in a chain made up of +1 signature and +1 public key, totaling three signatures and two public keys in total.

On a public web level, browser certificate transparency adds on one signature per log to the TLS handshake, making for a total of five signatures and two public keys.

“5 signatures and 2 public keys on average for each TLS handshake is simply too much to cope with for the larger PQ signatures that are coming,” Cloudflare stated.

Automation can help, but Cloudflare noted “attacks are still possible, and mistakes are almost inevitable.”

To solve the various complexities, the firm partnered with Google's Chrome Security Team with a proposal to the Internet Engineering Task Force (IETF). The venture aims to use MTCs to redesign the web PKI to allow a seamless transition to post-quantum (PQ) authentication with no performance impact.

What are MTCs?

MTCs are validated through information that can be distributed outside of a primary channel. When the data is up-to-date, the TLS handshake only needs one signature, one public key, and one Merkle tree inclusion proof.

The MTC specification also elevates certificate transparency to a primary function of the PKI by mandating that each CA maintain its own log containing precisely the certificates it issues.

“Merkle Tree Certification Authority (MTCA) produces its signatureless certificates in batches rather than individually," Cloudflare researchers explained. "In place of a signature, the certificate has an inclusion proof of the certificate in a batch of certificates signed by the MTC … which arranges the unsigned certificates into a data structure called a Merkle tree."

Each certificate in a batch is represented as a leaf in the tree, while every inner node of it is constructed as the cryptographic hash of its child nodes.

When signing the batch, the MTCA applies its secret key to the tree's head (or root hash), which serves as proof for the integrity of the entire batch. This tree structure ensures that each certificate is verifiably signed by the MTCA; any modification to a certificate would alter the resulting tree head and invalidate the signature, preventing tampering from going undetected.​

To prove that a specific certificate is included in the batch, an inclusion proof is generated. This proof contains the hash of each sibling node along the certificate's path up to the “tree head.”

“Given a validated tree head, this sequence of hashes is sufficient to prove inclusion of the certificate in the tree. This means that, in order to validate an MTC, the client also needs to obtain the signed tree head from the MTCA,” Cloudflare explained.

Signed tree heads can be delivered to clients using out-of-band channels and validated offline. Once a tree head is confirmed it enables the client to validate any certificate included in that batch, removing the need for a unique signature for each individual server certificate.​

During the TLS handshake, the client provides the server with a list of validated tree heads it possesses. If the server holds a certificate that is covered by any of these tree heads, meaning that certificate is included in the signed Merkle tree, the server can present it for authentication without needing a separate signature. As a result, only a single signature, one public key, and one inclusion proof are required for each handshake when the server is authenticated.

“[This] doesn’t create a separate Merkle tree for each batch, but it grows a single large tree, which is used for better transparency. As this tree grows, periodically (sub)tree heads are selected to be shipped to browsers, which we call landmarks,” Cloudflare noted.

“In the common case, browsers will be able to fetch the most recent landmarks and servers can wait for batch issuance, but … MTC also supports certificates that can be issued immediately and don’t require landmarks to be validated, but these are not as small," Cloudflare added. “A server would provision both types of Merkle tree certificates, so that the common case is fast, and the exceptional case is slow, but at least it’ll work.”

With Google’s Chrome team, Cloudflare will explore protocol ossification, where inflexible or buggy network equipment can disrupt new features, as well as how to ensure clients and servers remain closely synchronized to ensure lower latency, lower CPU cost, and reduce fallback onto older certificates. The latter is an issue as MTC lifespans are brief by nature, meaning anything older than a week will trigger a fallback.

These areas will be explored by a trial that will see the MTCA mimicked with the issue of bootstrap certificates which re-encode an existing certification with Chrome using certificate transparency as validation.

Cloudflare plans to roll out MTCs to some free accounts by early 2025.