The Quantum Threat To Cryptography

In one of our previous posts, we have already discussed quantum computing as technology and how it is different from classical computers while also pondering about its influence on our future. Today, we are going to talk about one area specific, cryptography. But before discussing the potential influence of quantum computing on cryptography, let’s remind ourselves what quantum technology is.

Defining The Technology

Quantum computers work with particles that can be in superposition. Rather than representing bits, such particles would represent qubits, which can take on the value 0, or 1, or both simultaneously. It allows them to be exponentially faster than today’s classical computers which are limited to handling only one set of inputs and one calculation at a time.

Transforming Cryptography

Cryptography is the science of encrypting and decrypting data, and it ensures that the private online communication of both individuals and organizations is confidential.

Typically, there is a combination of two techniques used for online encryption: symmetric-key cryptography and public-key cryptography. In the former, the sender and the recipient have to know (and, of course, keep secret from everyone else) a shared encryption key – it is used to both encrypt and decrypt the messages to be sent. Public-key cryptography, on the other hand, does not require any prior sharing of keys for sending and receiving encrypted messages. It is public-key cryptosystems that allow us to connect securely with anyone in the world no matter if we’ve exchanged data before or not.

Since quantum technology enables performing multiple calculations simultaneously, quantum computers have the potential to break any classical public-key encryption algorithm. When we say “break,” what we really mean is that they be able to calculate the private key just with the knowledge of the public key. In the early 1990s, Dr. Peter Shor at AT&T Bell Laboratories discovered an algorithm of doing so, but there is one thing that prevents the technique from being applicable today – Shor’s Algorithm can defeat the RSA and EEC encryptions, but only when there is a sufficiently powerful quantum computer.

Some Food For Thoughts

Let’s consider a simple practical example for a better understanding of the potential power of quantum computing. So, let’s imagine we managed to develop a quantum computer with 4099 qubits that are completely stable and error-free. Such a computer would be able to execute a modest one million operations per second. With its help, instead of spending 317 trillion years to break RSA 2048 on a classical computer, it could be executed in a matter of 10 seconds! Now it’s quite obvious why the world is racing toward developing powerful quantum computing, isn’t is? ?

Should I Worry Already?

Yes, and…no. It’s complicated. Several studies show that quantum technology is likely to catch up with today’s encryption standards much sooner than expected. Previously thought of as unbreakable systems, they might be an easy target for a quantum computer once it reaches the required power. Yes, the moment of breaking today’s public-key technology is still fairly far out as qubits are highly susceptible to almost undetectable amounts of thermal and electromagnetic interference that are difficult to eliminate (the “decoherence” problem). But still, the risk in on the horizon. Once there are enough stable qubits in a quantum computer, it will be able to break nearly every practical application of cryptography in use today. It means that e-commerce, as well as other digital applications, will have to be significantly transformed to stay afloat and secure their users.

Post-Quantum Cryptography

To address the aforementioned threat, several institutions such as the US National Institute of Standards and Technology established the goal to protect cryptographic algorithms from potential quantum computing attacks. To this end, they are planning to identify new secure cryptographic algorithms and then standardize them for broad use.

An important fact to mention is that while quantum computing is indeed a threat for current public-key algorithms, most symmetric cryptographic algorithms, like AES, and hash functions are considered to be relatively secure against quantum threats if their key is long enough – e.g. AES-256 or larger. While quantum technology does speed up attacks against symmetric ciphers, simply doubling the key size can effectively block the attacks. Thus post-quantum symmetric cryptography does not have to differ significantly from today’s symmetric cryptography.

Summing Up

Quantum computing is a promising technology that presents great opportunities in science, healthcare, business, and other various areas. However, while one side is so bright and positive, another is that when a quantum computer is in the wrong hands, it can cause a lot of damage, the brightest example being a threat to current cryptography. At the same time, it’s obvious that the implementation of quantum computers will be wide and it’s hard to predict all the areas when it would be used – the cryptography isn’t an exclusion. Although current quantum computers are far from being real trouble, it is better to be prepared once the technology gains enough strength.

‍