The encryption time bomb brought on by quantum computers

The internet has been a game-changer to our societies and how we do business for decades. We rely on the web so much that it became second nature for many of us to use it and expect it to work all the time, but it might be in danger now, or so tells many current articles and headlines.

The suspected culprit in this is quantum computing, a cutting-edge technology built up to change the whole game. There is a lot of fuss about quantum computing making our current types of encryption obsolete. If true, that would kill current cyber-security, making this technology a ticking time bomb that might change how we think about the internet and privacy forever.

Considering the dangerous ramifications of losing the effectiveness of encryption, the response to the threat seems underwhelming. So, let us take a deeper look at quantum computing, what makes it a threat to encryption, and what to do to protect us against it.

Not zeros and ones anymore

Almost every computing device relies on the same fundamental unit today, the bit. The bit is one of two values, either a zero or a one, put eight bits together, and you get a byte. From there, you can go to kilo, mega, gigabytes, and beyond. Yet, quantum computers do things differently; they use the quantum bit (or qubit for short) as their unit.

Like bits, the qubit can be a zero or a one, but it can be some mixture of the two values and not exactly determined until we observe it. Quantum computing is built to take advantage of quantum physics pioneered in the early twentieth century, and like quantum physics, you cannot explain it within a few lines or a few pages, for that matter.

The important thing to know is that quantum computers do things differently, so they can do some tasks that seem impossible or at least take astronomical lengths of time to do traditionally. Yet, quantum computers need special conditions, such as temperatures near the ultimate zero (minus 273.15 on the Celsius scale) for that.

As they are hard to operate and have no use for the general public, it is improbable to see quantum computers replacing regular ones or even spreading out of research institutes in universities, large corporations, or government agencies.

Quantum computing vs. encryption

Cryptography is the science of turning information into incomprehensible code and back, and it is an old practice designed to make communications as secure as possible. For example, the Caesar cipher named after the Roman emperor Julius Caesar; is an ancient cipher that replaces every letter with another one with some fixed number of positions away in the alphabet. If we replace each letter with another two positions ahead, “Caesar” becomes “Ecguct” a meaningless word unless you know the key for decoding it.

Current ciphers are far more complicated than something like the Caesar cipher. Yet, most of them still rely on a public-private key duo to decipher the information. Such encryption systems are not impossible to break, but they are impractical enough to be considered safe. A cryptographic system using a 256-bit key would take 2²⁵⁶ steps to break, which would need billions of years to crack using all the traditional computing power we have today. Yet, using special algorithms, future quantum computers could break it within minutes.

As they work differently, quantum computers are very effective against many PKC (Public Key Cryptography) systems. RSA, Diffie-Hellman, and ECDSA encryptions rely on the intractability of integer factorization and discrete log problems; they are hard for traditional computers but easy for quantum computers.

Are we doomed then?

According to Dr. Michele Mosca, from the Institute for Quantum Computing at the University of Waterloo, there is a one-in-seven chance that some fundamental public-key cryptography will be broken by quantum computers by 2026, and a one-in-two chance of the same by 2031. Such a timeline seems daunting, but all hope is not lost yet.

Dr. Mosca’s estimates are not the only ones, and the timeline is continuously shifting as we go forward. Some predictions say we are on the verge of a cryptography collapse, while others say it may take decades if it ever happens. Either way, we are not sitting idle waiting for encryption to die.

We already have multiple types of post-quantum encryption schemes. For example, AES-256 is considered quantum-safe as it will still provide 128 bits of security against quantum attacks. Other than AES-256, we have lattice-based, code-based, hash-based, isogeny-based, and multivariate systems as quantum-resistant encryptions.

Even though we have a plethora of quantum-resistant cryptography systems, we are not out of the woods yet. The main hurdle in front of us now is standardization; the internet is massive and far from unified, so we are in a race against time to migrate to quantum-safe encryption systems before it is too late.

IEEE (Institute of Electrical and Electronics Engineers) and ANSI (American National Standards Institute) have already published their schemes for post-quantum encryption systems. American NIST and European ETSI have also followed suit publishing their reports on post-quantum cryptography. That is far from the global transformation we need, but it is a step forward nonetheless.

At any rate, the internet encryption apocalypse is still an issue of the future, as NIST predicts that RSA encryption, one of the most endangered, will not be cracked before 15 years. Even considering bureaucracy and the fragmentation of the internet, 15 years is a long time for us to prepare, but we must not procrastinate.