Google quantum-proofs HTTPS by squeezing 15kB of data into 700-byte space

Google on Friday unveiled its plan for its Chrome browser to secure HTTPS certificates against quantum computer attacks without breaking the Internet.

The objective is a tall order. The quantum-resistant cryptographic data needed to transparently publish TLS certificates is roughly 40 times bigger than the classical cryptographic material used today. A typical X.509 certificate chain used today comprises six elliptic curve signatures and two EC public keys, each of them only 64 bytes. This material can be cracked through the quantum-enabled Shor’s algorithm. The full chain is roughly 4 kilobytes. All this data must be transmitted when a browser connects to a site.

The bigger they come, the slower they move

“The bigger you make the certificate, the slower the handshake and the more people you leave behind,” said Bas Westerbaan, principal research engineer at Cloudflare, which is partnering with Google on the transition. “Our problem is we don’t want to leave people behind in this transition.” Speaking to Ars, he said that people will likely disable the new encryption if it slows their browsing. He added that the massive size increase can also degrade “middle boxes,” which sit between browsers and the final site.

To bypass the bottleneck, companies are turning to Merkle Trees, a data structure that uses cryptographic hashes and other math to verify the contents of large amounts of information using a small fraction of material used in more traditional verification processes in public key infrastructure. Cloudflare has a much deeper dive into Merkle Trees here.

Merkle Tree Certificates, “replace the heavy, serialized chain of signatures found in traditional PKI with compact Merkle Tree proofs,” members of Google’s Chrome Secure Web and Networking Team wrote Friday. “In this model, a Certification Authority (CA) signs a single ‘Tree Head’ representing potentially millions of certificates, and the ‘certificate’ sent to the browser is merely a lightweight proof of inclusion in that tree.”

The issue of predicting quantum computing progress is that it's highly non-linear. We don't see many new factoring results not because they are not possible but because that's not the main goal right now. What people are currently doing are, for example, proving quantum computing is possible (e.g. Google's quantum supremacy experiments), implementing quantum error correction, scaling, etc. It's also not helping that you can bet that many goverments are spending a lot money on this problem without telling anyone, so even if they have good results they are not telling you.

So I do think we need to start preparing for quantum resistent cryptography. The current algorithms are not necessarily great (we don't know yet), but we need to prepare to be able to easily switch algorithms (from RSA and ECDSA to current or future quantum resistent algorithms).