In February, Google announced a solution: Merkle Trees. These hierarchical data structures use cryptographic hashes and other math to verify the contents of large amounts of information using a small fraction of their contents. The design, which Google and Cloudflare have been testing in limited pilot programs, drops the amount of handshake data to about 40 kilobytes, about the same as is processed now.
The current WebPKI relies on a multi-link chain of quantum-vulnerable signatures to prove a certificate’s authenticity. Since replacing the signatures with quantum-resistant ones is resource-prohibitive, the chains are replaced with compact Merkle Tree proofs. To complete such a proof, a certificate authority signs only a single “tree head” that can represent millions of certificates. In most cases, the data a browser handles is a “landmark,” a lightweight proof that the certificate is located somewhere in the tree.
Industry-wide rules require that TLS certificates be published in append-only distributed ledgers known as public transparency logs. Website owners check the logs in real time to ensure that no rogue certificates have been issued for the domains they use. The transparency programs were implemented in response to the 2011 hack of Netherlands-based DigiNotar, which allowed the minting of 500 counterfeit certificates for Google and other websites, some of which were used to spy on web users in Iran.
Once viable, Shor’s algorithm could forge classical encryption signatures and the public keys of certificate logs. Ultimately, an attacker could forge signed certificate timestamps used to prove to a browser or operating system that a certificate has been registered when it hasn’t.
Under the current PKI system, updates are handled by adding a new link to the signature chain. Merkle Trees provide proof of a signature chain without explicitly listing each individual link. The design has another major benefit. Under today’s system, transparency logs are a process that’s distinct from certificate issuance. With Merkle Tree Certificates, by contrast, the logging is a core part of the issuance. “By coupling issuance and logging, transparency becomes a requirement for operation, rather than an add-on,” Cloudflare engineer Mari Galicer said.
There are a host of other designs included in Cloudflare’s plan. One is Automated Certificate Management Environment (ACME), an open source mechanism for issuing certificates and continuously renewing them shortly before expiration. The quantum-resistant certificates will also provide a mechanism for signatures to be sent out-of-band—for instance, through a browser update—if a downed server or other technical problem prevents receiving a landmark update. Cloudflare said it expects to start issuing certificates in the first quarter of 2027.
