Quantum computers will revolutionize cryptography. Here’s why.

Krijn Reijnders

22-11-2018

Quantum computers will revolutionize cryptography. Here’s why.

Sufficiently strong quantum computers will seriously disrupt the confidentiality and integrity of secure digital communication everywhere. They will effectively break most of the current methods to securely exchange data, and quantum-resistant alternatives are not yet mature. Even though the development of such quantum computers may take years, you are running risks you are not aware of. In this blog, we will explain how quantum computers will revolutionize your data security and why you should be aware and prepare.

Data is everywhere, and everyone is sharing data. If you want to securely share and exchange data, proper data security is fundamental. One of the pillars of data security is cryptography, the practice of encrypting and decrypting data using cryptosystems to enable secure communication. But the development of quantum computers is weakening this pillar: it’s showing cracks already.

Quantum computers will break current cryptosystems

A quantum computer with enough computing power would shatter the current security of public key cryptosystems (see frame A) upon which the digital exchange of data is based. The security of these cryptosystems is based on only a few mathematical problems (see frame B below). Our trust in digital security relies upon the fact that up until today no one has been able to solve these problems efficiently. A paper by Peter Shor, written in 1994, explains how a quantum computer would be able to do so. The development of quantum computers has seen quite a bit of progression in recent years, with IBM reaching 50, Intel 49 and Google even 72 qubits. Estimating when a large enough quantum computer arrives remains difficult. However, experts[i] agree that we should start looking at how to prepare for such an arrival. By discussing three fundamental questions, we will explore this world of Post Quantum Cryptography (PQC).

A. Quick introduction to cryptosystems:

There are two main branches of cryptography that we use to ensure safe exchange of data.

1. Symmetric cryptography

In symmetric cryptography two parties exchange data using the same encryption key. Party A encrypts his data using some key X, party B decrypts this data using this same key X. Symmetric cryptography is fast, but the problem is exchanging the key, which needs to be done before any encrypted exchange can ensue.

2. Asymmetric cryptography

In asymmetric cryptography (public-key cryptography), the two parties use different keys to exchange data. By some nifty mathematics, this enables a secure exchange of data without the need to exchange a key first. The downside is that asymmetric cryptography is slow in comparison to symmetric cryptography.

In general, to exchange data we use asymmetric cryptography to exchange the key that will be used in symmetric cryptography. However, this carries the risk that “breaking” asymmetric cryptography also “breaks” this key exchange for symmetric cryptography.

A visualisation of Post Quantum Cryptography

1. How will we securely exchange data in a world with quantum computers?

In a quantum world, we will exchange data securely using new cryptosystems, that replace the currently used ones. To ensure that we have such quantum-resistant cryptosystems in the (near) future, the National Institute of Standards and Technology (NIST), an authority on cryptosystems, initiated a process to develop, analyse and standardise such systems. Their goal is to release quantum-secure standards somewhere in 2022/2024[ii], built on mathematical problems that quantum computers cannot solve efficiently. Such cryptosystems should enable us to securely exchange data in a world with quantum computers.

2. What do we need to securely transition to these new cryptosystems?

To prepare for this transition, we’ll need to analyse which systems currently use what cryptographical standards and to what standards they need to be upgraded. Security experts will need to be educated on these new standards and will need to know how they should be implemented. Much of this work can already be started, to ensure that this time-consuming transition would be completed before we start running major security risks. This is comparable to the Y2K problem; a race against the clock. Therefore, some experts call this transitioning problem and the time until quantum computers Y2Q (years to quantum).

B. Current asymmetric cryptosystems

The two main current approaches to asymmetric cryptography are RSA and ECC. There are some differences between these two approaches: The security of RSA is based on the mathematical problem of finding divisors of numbers, i.e. finding that 5 divides 15; the factoring problem. This problem is easy for small numbers but becomes very hard when the number is very large. ECC bases it security on a problem that is a bit harder to explain: the elliptic curve discrete logarithm problem (ECDLP). In practice, the difference between these two approaches lies in the length of the key. To achieve the same security against current attacks, RSA needs keys that are much larger than ECC needs. ECC is therefore preferred in applications where processing power is limited.

Both the factoring problem and ECDLP are efficiently solved by quantum computers, with current research indicating that ECDLP will be the easiest of these two to be attacked by a quantum computer.

3. Why is the exchange of highly secure data at risk today?

Even if we transition into these new (hopefully) quantum-resistant cryptosystems in time, there is a more urgent issue we should address. Imagine a malevolent party saving loads of your encrypted data today. They (the party) keep this data stored somewhere until they have access to a quantum computer that is strong enough to decrypt this data. Quickly they will have a huge pile of your data in which they might find nuggets that were meant to be secure for decades, with an impact on your business. Although such a quantum computer may lie more than a decade away, this poses a threat for highly secure data today. If you have data which needs to remain private for years, you need to start thinking about how you store and exchange that data now.

What you can do to be aware and prepare for Y2Q.

So, there we have it. There is currently no great long-term option to exchange highly secure data. The transition into new cryptosystems will take huge amounts of time, effort and resources. Even then, trust in these new systems will need time to develop. But there are some things that we can do already:

Look at using hybrids of current cryptostandards and new cryptostandards;
Catalogue how you use current cryptostandards in your systems and products;
Develop a strategy for the transition into these new cryptostandards, specifically when developing long-term products which use quantum-vulnerable cryptography;
Develop knowledge in the area of post quantum cryptography, which will be a necessity in coming years;
Carefully analyse the different sensitivities of different sets of data. Then adapt your data exchange security to that, especially for data that needs to stay secure for more than 5 years.

We do not know when a large enough quantum computer will be ready. But we do know that doing nothing is not an option. If you would like to know more about how post-quantum cryptography or how cryptography can help protect your organisation, please contact Vincent Jansen.

---

[i]Dr. Michele Mosca estimated the chance that a cryptosystem will be broken before 2026 as one in seven, and before 2031 as one in two. He calls this moment Y2Q (Years 2 Quantum). He made these estimates in 2016, before the major advancement in numbers of qubits by IBM, Intel and Google were made public.

[ii]https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Workshops-and-Timeline