Quantum Computing and its Impact on Cryptography

“Quantum computing” is computation performed using a computing device based on the strange, counter-intuitive physical properties of matter at very small scales, known as quantum mechanics.

Unlike a classical computer based on transistors that encodes data in binary digits (or “bits”) that can only be a “1” or a “0” (think “on” or "off"), a quantum computer uses “qubits,” where a single qubit is able to encode more than two states. (Technically, each qubit can store a superposition of multiple states, but the mathematics is far too complex for the purposes of this article!)

Note: Quantum computing should not be confused with “quantum cryptography”, which is the science of exploiting quantum mechanical properties to perform cryptographic tasks. A prime example of this is “quantum key distribution,” which enables a secret cryptographic key to be shared between two remote parties such that any interception can be reliably detected.

This technology, while less complex than quantum computing, is also relatively immature, with many existing practical implementations proving unable to live up to their theoretical promise.

Do Quantum Computers Exist?

Yes, simple, small-scale quantum computers have been built and successfully demonstrated. Currently, these are laboratory instruments that are large, expensive, complex to use, and have very limited capabilities. But they do prove the underlying physical principles are sound.

The challenge is to build one that is big enough (in terms of qubit capacity) to perform useful tasks better than classical computers.

Many universities, companies, and government agencies around the world are racing to do this, using a variety of different experimental techniques; some techniques may turn out to be more viable than others or have specific properties that are useful for certain classes of applications.

Why are Quantum Computers Useful?

It is possible to create algorithms that run significantly faster on a quantum computer than a classical computer, due to the unique properties of qubits. These algorithms could be used for a number of different scientific and business applications, and will bring many benefits. Some of these algorithms have already been tested and proven on prototype quantum computers, but they will not be practically useful or economical until larger quantum computers have been built.

How are Quantum Computers Relevant to IT Security?

Encryption and public-key cryptography are important for e-commerce and keeping secret electronic information safe. They are also used in many important parts of IT security.

These techniques are based in turn on mathematical algorithms that are very difficult to "break." Modern algorithms with suitable key lengths (e.g., AES-128, RSA-2048, ECDSA-256, etc.) are not susceptible to brute force attack; even with massive amounts of computing power, they would take centuries or, in some cases, even longer than the lifetime of the universe to break.

However, it is possible to create unique algorithms for quantum computers (e.g., “Shor’s algorithm”) that dramatically reduce the time it takes to break these algorithms.

Symmetric algorithms used for encryption, like AES, are still thought to be safe (with sufficient key length, e.g., AES-256 or larger); however, current asymmetric algorithms like RSA and ECDSA will be rendered essentially useless once quantum computers reach a certain scale.

This will break nearly every practical application of cryptography in use today, making e-commerce and many other digital applications that we rely on in our daily lives totally insecure.

What is Preventing Large Quantum Computers Today?

Working at the limits of physics is challenging! While much of the theory is well understood, turning theory into practice at such small scales is a significant scientific and engineering challenge that is taxing many of the world’s best scientists.

Before large-scale quantum computers can be made, there are still a lot of fundamental problems that need to be solved. In particular, qubits are very sensitive to almost undetectable amounts of thermal and electromagnetic interference that are hard to get rid of (this is called the "decoherence” problem).

A further challenge will be making quantum computers affordable to anyone outside of academia and government.

So when will Large Quantum Computers Become Available?

The short answer is that no one knows. It depends on a number of scientific and engineering breakthroughs being made, which could come in the next 5–10 years, or 20–30 years, or maybe never. It may take many more years before such computers are generally affordable outside of large government agencies.

This uncertainty is the biggest worry facing governments and businesses alike.

What will Happen Then?

Many mathematicians in academia and the government are working on a number of possible "quantum-resistant" algorithms that quantum computers can't break.

However, it takes time to gain confidence that these algorithms don’t have other weaknesses—it typically takes many years to gain confidence in the safety of any new algorithm. Performance is also an issue that quantum-resistant algorithms will have to overcome.

New standards will have to be written and adopted, many of them national or industry-specific; applications will have to be adapted to make use of the new algorithms, which can be a real challenge in some industries (such as banking), where there is a huge amount of legacy infrastructure that cannot be easily upgraded, if at all.

Algorithms such as DES, MD5, SHA-1, and RSA-512 are still used in some places, yet are considered breakable using classical computing today or in the near future, simply because of the amount of inertia in large commercial systems where interoperability is essential.

So, if you consider the above and look at the most optimistic predictions of the availability of large quantum computers, there really isn’t any time to lose in starting to solve these problems!

Should I Worry?

Probably not - it is a global problem, and there are many people working on this. But that doesn’t mean you should ignore it. Keep an eye on the progress of quantum computing, the development of quantum-resistant algorithms, and the creation of new standards; ensure your applications and infrastructure are upgradeable; make a plan, and be ready to migrate at the right time.

(Note that the latest Elliptic Curve technology doesn’t provide any benefit – in fact, it’s even less secure in the face of quantum computing – so there’s no real point in moving from RSA to ECDSA, unless you need the speed advantages it offers.)

However, note that much encrypted information that is around today, or over the coming years, will probably be susceptible to decryption one day in the future once quantum computers are generally available – all an attacker needs to do is capture the encrypted data today, including the initial key exchange handshake, then wait until they have a quantum computer power enough to break it within a reasonable amount of computing time.

This is primarily a problem for governments, which have large amounts of secret data with a long “intelligence life,” i.e., data that needs to be kept secret for 25 years or more for national security reasons. This is why governments are at the forefront of the research effort—both to develop quantum computing for offensive cyber operations, and to develop quantum-resistant algorithms for defensive purposes. They may even have clandestine research efforts that are ahead of the academic world, as there is a significant military advantage to be had.

Commercial organizations with sensitive data that they wish to protect in the long term and that are attractive targets for hackers should look to use symmetric algorithms with long key lengths (e.g., AES-256 rather than AES-128 or 3DES) as soon as possible and, where Diffie-Hellman is used to negotiate symmetric keys, use perfect forward secrecy techniques to minimize the amount of data protected under each key.

They should also look to migrate to quantum-resistant algorithms sooner rather than later. However, given the infancy of such algorithms, it would be wise to initially use hybrid algorithms (which combine proven, established algorithms with unproven, quantum-resistant algorithms, such that an attacker has to break both to be successful).

For the most paranoid, safety can be found by eliminating the use of public key cryptography entirely and relying purely on symmetric cryptography. However, that introduces a different and perhaps more problematic security challenge, i.e. the secure sharing of secret key material. Perhaps quantum key distribution will provide the solution to that?

The Post-Quantum World

At the end of the day, the threat of quantum computing is reduced to an economic problem. Viable quantum computers will initially be very expensive and have limited power, so initially only governments will be able to afford them, and they will only have enough capacity to attack the most valuable secrets of other nation states.

Gradually, this capability will trickle down to organized criminals, but again, they will only have the capacity to attack the most lucrative targets (e.g., falsifying financial transactions, blackmailing large companies, or selling their sensitive data to the highest bidder). By the time quantum computing is generally available (if ever), hopefully the old, vulnerable algorithms will have all but disappeared.

Further Reading

• CSG
• IBM Research

• NIST

• Wikipedia

Photo: "Stock images of patterns and shapes" courtesy of Toperdomingo, license: Public Domain