No. Now, thank you for your attention.

Last year, some security researchers were discussing a doomsday scenario, that without investing in quantum encryption, there would soon be no way to feel secure over the Internet. (I would add, that a feeling of security over the Internet is misleading at best.) Allow me to break down some of these security peculiarities, which could be worrisome.

So, what’s the buzz?

Let’s approach this from the very beginning. At the basis of modern encryption algorithms lies a so-called Diffie-Hellman key exchange [1]. It’s there at HTTPS when you submit a payment request, and when you send a personal email too.

A lot of boring math happens in there, but at the end of the day, all we have to know is that the only reason a third-party can’t guess the shared secret key is because classical computers struggle with factoring integers. Even last year, when a classical computer took a stab at it, it took at least 700 core-years for RSA-240 [2]. For RSA-1024 (that we don’t even consider secure enough for the Internet) it would take hundreds of times longer. This is why we use them. With a few simple steps, these algorithms work like a charm and bring safety and security for everyone involved. But are they really secure? Enter quantum computers.

Peter Shor, an American professor at MIT, devised an algorithm that solves this factoring problem in “polynomial time” on a quantum computer. That’s a deal-breaker. When compared to the thousands of years of computation on a classical computer, this means that on a quantum computer, it is actually possible to find the shared key that two machines have agreed upon in a secure key exchange, in a reasonable amount of time.

So, what you’re saying is, we’re doomed?

Not necessarily. Let’s remember that everything hinges on the fact that we use integer factorizations to encrypt things. But classical encryption isn’t limited to that! RLWE-KEX key exchange, for example, doesn’t need those numbers at all, since it’s operating on a completely different principle, namely ring polynomials with errors. And there are many other algorithms currently proposed and being considered that are also quantum-proof.

The elephant in the room, of course, is that there is no known quantum computer today that can execute Shor’s algorithm. Long live TLS-RSA. (At least for quantum. We are still looking for bugs in there too, but that’s a topic for another day.)

So, what you’re saying is, we’re not doomed?

Not necessarily. Let’s look at the past issues. Remember moving from MD5 to SHA-1? Then from SHA-1 to SHA-2? Now imagine the same scenario on steroids. Half of the companies would not be prepared for the inevitable revolution, after listening to people like me who think that there is no way to resolve the decoherence in a quantum computer, and the other half would buy into things that people would be selling as “quantum safe” while being the opposite of that.

And let’s not forget about the myriad IoT devices that would be left open in the wild due to their outdated tech. Si vis pacem, para bellum. We are safe right now, but who knows what’s lurking in the depths of high-tech corporate laboratories.

The biggest issue is, not a single one of the proposed classical quantum-safe algorithms can currently provide the same level of combined speed and security that are necessary for an Internet user to feel good.

So, are quantum computers such a force of evil?

Necessarily not! True quantum cryptography is theoretically unbreakable! This means that in a perfect world, where no one accidentally leaves a laptop open at the corner cafe, and no one has access to the proverbial “$5 wrench used for key extraction directly from a human”, the communication is perfectly secret. Quantum key distribution is based on fundamental laws of physics and guarantees that no one shall ever be able to eavesdrop in transport. And if they do, well, the quantum information is simply destroyed and vanished forever.

[1] Diffie-Hellman Key Agreement Method: https://tools.ietf.org/html/rfc2631

[2] 795-bit factoring and discrete logarithms: https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html