Newsportal - Ruhr-Universität Bochum
Cryptography in the era of quantum computers
Researchers worldwide are striving to develop the quantum computer. Its computation power would surpass that of today’s machines to a considerable degree for certain tasks.
This is why the Hardware Security Group is currently developing the cryptographic methods of tomorrow. Prof Dr Tim Güneysu tells us about them.
Prof Güneysu, together with your group, you are developing novel encryption techniques that even shall resist attacks by quantum computers. However, a quantum computer does not exist yet.
That’s true. Still, security must always think in terms of the future. These days we know two flavours of cryptography, namely the symmetric and asymmetric cryptography.
The latter are required for the implementation of advanced security services such as are deployed in a majority of systems. Take the log-in to Amazon as an example, where you will likely submit critical information such as your credit card information. In the first step, a secret key has to be negotiated between the user and Amazon’s server before the encrypted data transmission can commence. And such transactions take place millions of times each day.
It is an open question when sufficiently powerful quantum computers will become available.
Currently, two different kinds of asymmetric methods are in use in virtually all practical systems, and we already know that both would be broken in the era of quantum computers. It is an open question when sufficiently powerful quantum computers will become available. But we have to be ready.
So alternative systems must be established in the market by that time. Moreover, we must prevent the encrypted data of today to be retrospectively revealed with the support of quantum computers that might be around in some years.
How do cryptographic techniques that protect from quantum computers differ from established techniques?
Quantum computers enable a novel paradigm of computation. Depending on the application, they will boast a computing power that is much higher than that of current computers. Hence we need techniques of post-quantum cryptography, i.e. asymmetric cryptographic techniques that are safe from quantum computer attacks. Those rely on particularly difficult mathematical problems that are not expected to be solved more efficiently even if the computational model of a quantum computer is deployed.
Quantum computers boast a computing power that is significantly higher than that of established machines, because they are based on the principles of quantum mechanics rather than those of traditional digital technology. The smallest information unit processed by traditional PCs is the bit, which can assume the two values 0 and 1. At any given time, it can have either the value 0 or the value 1. Quantum bits, short qubits, on the other hand, can assume both values at the same time due to an underlying physical effect of superposition.
A traditional computer that operates with two bits is capable of storing four bit configurations: 00, 01, 10, and 11; here, the first figure in each of the four-figure pairings represents the value of the first bit and the second figure the value of the second bit. At any given time, the traditional computer can assume only one of those four values.
A quantum computer with two bits, on the other hand, could store the same bit configurations, but all four configurations at the same time. If additional bits are fed into such a system, the computing power increases at an exponential rate.
However, quantum computers would not constitute a suitable replacement for traditional machines in every respect. Rather, they would only be suited for specific tasks. One of the most prominent ones would be breaking the asymmetric cryptography that is used today.
Unfortunately, the instances of those problems are often not that difficult to solve unless they operate with large parameters, what leads to extremely long cryptographic keys. In our EU project Post-Quantum Cryptography, we focus on four existing categories of cryptographic techniques in this context that would constitute a suitable replacement of current asymmetric cryptographic techniques.
How much do the cryptographic keys differ in terms of length?
At present, a length between 128 bit and 4096 bit is commonly used in key parameters of conventional techniques. Here, 128 bit are the equivalent of 16 characters; this is not even impossible to memorise. Accordingly, such key lengths can be quite easily integrated even in microdevices.
In highly secure post-quantum cryptography techniques, on the other hand, the key sizes range between several hundred kilobytes and megabytes, i.e. one million characters and more. Operating with codes of such length is even for common computing systems not a trivial task at all.
For quantum computers, processing or saving long keys would surely pose no problem at all.
Yes, but it is not the quantum computers of tomorrow that are the problem, but the microdevices of today. Cryptography is already ubiquitous, in bank cards, electronic health cards, and electronic locks. In future, such devices will probably become as powerful as our Smartphones today. But they aren’t yet. Still we must protect ourselves and our current data from the attacks of tomorrow.
In addition to that, health data, for example, is generally long-term critical. If somebody is able to intercept and store such data today, it must be ensured that it will not be possible to decode this data successfully using a quantum computer in 15 years’ time.
This is the problem that affects all technical devices with a long operating life. For example satellites, which are launched into orbit and are expected to conduct secure communication for several decades.
You are working on a solution for that problem: protecting microdevices from quantum computer attacks.
We explore alternative asymmetric encryption techniques that will ensure security even in the era of quantum computers. A main objective is the development of alternative techniques for handling complex protection algorithms and large cryptographic keys so that they can be implemented even into microdevices.
When will the techniques become ready to use?
Off the top of my head I’d say in five to ten years’ time. It is necessary to build up acceptance and trust into the respective technique before it can find its way into official or industrial standards. Experience has shown that this process takes several years. As a general rule, this is the requirement that has to be fulfilled before a new technique will be implemented in products in large scale.
17 December 2015