What is Post Quantum Cryptography and why should I care?

If you have been following the news on the development of commercial quantum computers, you may be getting worried that intelligence services and ambitious cyber criminals may soon be able break your encryption. Canadian company D-Wave already sells commercial quantum computers, if you’re willing to shell out 15 million dollars and have ample floor space available in your data centre. IBM recently reported building a prototype 50-qubit processor. Is it only a matter of time before quantum computers are able to break even the most complex encryption in an afternoon’s work?

The good news is that recent announcements about quantum computers are no reason to panic. Only specific types of quantum computers are suitable for running the algorithms required to break encryption. D-Wave’s quantum computer, for example, is unsuitable for this purpose. Even if IBM manages to keep its 50 qubit prototype stable enough in a lab setting, this machine still has two orders of magnitude fewer qubits than are required to break the most commonly used encryption schemes. Add to this that as the number of qubits grows, it becomes ever more challenging to keep the system stable, and it soon becomes clear that we have little to fear from commercial quantum computers in the near term.

How does a quantum computer differ from a PC?

In the long term, however, quantum computers may pose a significant threat to sensitive information that is stored in encrypted form. Quantum computers are capable of performing certain parallel computations — that ‘classic’ computers would struggle to solve — extremely efficiently. The reason for this is that quantum computers make clever use of quantum mechanics. Their processor is built using qubits, that can represent a 0 or a 1 at the same time. The computational power of a quantum computer scales exponentially. For example, and 8-qubit processor can perform 256 computations in parallel that a ‘classic’ computer would have to perform sequentially.

What can intelligence services do using a quantum computer?

The encryption of much of today’s Web traffic is based on the premise of multiplying two extremely large prime numbers (the so-called RSA algorithm). In theory, unlike ‘classic’ computers, a sufficiently powerful quantum computer would only require a short amount of time to factor the product of these two prime numbers, which would break the encryption. In practice, we are not at this stage yet. For example: MIT announced in the Spring of 2016 that their quantum computer was capable of factoring the number 15. This achievement is lightyears away from factoring the long numbers with hundreds of digits used in today’s Web cryptography.

When can we expect a breakthrough?

We are regularly asked the question: how long will it take before quantum computers can be used to gain access to our sensitive encrypted data? It turns out it is really difficult to answer this question. Even the experts do not know for sure, but most will say that this is still at least twenty to thirty years in our future. There are even experts that doubt if quantum computers will ever be powerful and stable enough to break our cryptographic schemes. This is because the stable quantum state needed to perform the relevant computations is easily disrupted. It is still an open question if it will be possible to maintain a stable state long enough to actually break cryptographic schemes.

What dangers do we see?

Let us assume that scientists manage to build that stable quantum computer within the next two decades. What dangers does this pose? Consider, for example, an intelligence service that has stored all communication between your computer and some sensitive website. Even though that communication is safe today, if it is stored somewhere, it could be broken once quantum computers are powerful enough. Therein lies the greatest danger: so-called ‘data at rest’ that is stored over longer periods of time is particularly vulnerable. Take, for example, the DNA profile of a person, something that most people would consider highly private. If such data needs to be stored in encrypted form for long periods of time, possibly 20+ years, then even though the encryption cannot be broken now, we need to think about what would happen if a quantum breakthrough occurs.

We should also note that in many cases, quantum computers breaking encryption will only become a problem once they are available. For example, the digital signatures used in the SURFconext identity federation only have very short validity times, making it irrelevant what people can do in twenty years time. Equally, the digital certificates used to authenticate HTTPS websites also have a limited validity of between one and three years.

What action can we take?

Cryptographers are hard at work to develop so-called ‘post quantum cryptography’ (PQC). These are algorithms that remain secure, even in the presence of sufficiently powerful quantum computers. While development of these algorithms has been ongoing for quite a number of years, and while there are promising candidate algorithms, there are open issues. For example, most of the proposed PQC algorithms have key lengths that are orders of magnitude larger than those of today’s algorithms. This makes these proposed algorithms hard to use in certain Internet protocols. Another issue is that most proposed PQC algorithms currently have much higher CPU performance requirements. This means that your computer would have to work harder (and thus spend more time), for example, setting up a secure connection to a web server. In many cases, another issue with PQC algorithms is their relative youth; typically, we want cryptographic algorithms to receive a lot of scrutiny from academic cryptographers, who attempt to break these algorithms using cryptanalysis. The absence of serious vulnerabilities under such public scrutiny forms the basis for trust in the algorithms.

Time to take action?

At SURFnet, we closely monitor developments around both quantum computing and post quantum cryptography, in close collaboration with academia, industry, standardisation bodies and other national public bodies, such as the Dutch NCSC. Based on this, we will inform our constituency if there is a need to take action, and will also inform them on choices to make when choosing PQC algorithms to replace more traditional forms of cryptography. And there are also actions you can take: especially if you store sensitive data over long periods of time, it is worth planning ahead and getting a clear overview over which data you store for what amount of time. As a rule of thumb: the longer you store sensitive data, the earlier you may need to consider to quantum-resistant PQC encryption algorithms.

Further reading?

Earlier this year, the Dutch NCSC published a factsheet on post quantum cryptography.