It’s the year 2035: Quantum computers are capable of cracking all of the public-key algorithms that provided protection for sensitive data back in 2019. Hackers use quantum computers to access information in private emails, while state authorities use them to obtain data belonging to suspicious institutions. Debit card payments are no longer possible, and trading in cryptocurrencies such as Bitcoin is vulnerable to attack.
This scenario seems unrealistic from our current perspective. Researchers predict, however, that in ten to fifteen years there will be functioning quantum computers capable of calculating mathematical problems such as the prime factorization of very large numbers millions of times faster than today’s normal computers. And those quantum computers would be able to crack encryption methods which we now believe to be secure. How realistic is this prediction, and what does it mean for the IT security industry?
The difference between normal computers and quantum computers
A quantum computer with 1 qubit can take on 2 states simultaneously. A computer with 25 qubits can assume 2 to the power of 25 at the same time—or 33,554,432 states. This allows quantum computers to take on many times more states than a normal computer and perform more simultaneous calculations. This means a quantum computer with many qubits would require only a few minutes to perform calculations that would take a normal computer longer than a human lifetime to complete.
Development status of quantum computers and current challenges
Although research on quantum computers has been going on for over 20 years, it has not yet been possible to develop a commercially usable quantum computer. Major institutions such as the NSA, Google, IBM and Microsoft are working to develop high-performance quantum computers. At the beginning of this year, IBM introduced a non-commercial quantum computer measuring 2.5 by 2.5 meters that operates on 20 qubits. A quantum computer with as few as 50 qubits would be faster than a supercomputer that uses many processors.
The fact that there are no commercially available quantum computers yet is due to a number of challenges that have yet to be solved: First, quantum computers are difficult to build because qubits need to be kept in stable superposition.
So far, it has only been possible to achieve run times up to a few microseconds. Second, many entangled qubits are needed to achieve high computing power. However, this also greatly increases the number of errors resulting from calculations performed with many qubits. Even calculations performed with normal computers produce such computational errors, but unlike quantum computers, correction algorithms exist for these. This means that new algorithms have to be developed so that quantum computers can perform calculations efficiently and free of errors.
The successful development of a quantum computer would also give rise to the use of quantum cryptographic encryption methods, the development of which, however, is currently facing similar problems. Quantum cryptographic encryption promises secure communication. As soon as an eavesdropper tries to read the value of a particle, the value changes. The eavesdropper exposes him- or herself and is unable to read the message, at least according to current theory. However, connections made thus far have been very error-prone, since the particles need to be transmitted with absolutely no interference. Moreover, the currently developed network is not suitable for transmitting communications secured with quantum keys.
Protecting data from quantum computers: Post-quantum cryptography
Research is already being performed on new quantum-resistant encryption algorithms to prevent the decryption of methods that we have come to believe are secure. This area of research is called post-quantum cryptography. Established asymmetric public-key encryption methods such as RSA multiply large prime numbers together for their encryption. It would take normal computers decades to factorize the primes again, which is why the procedures were considered secure until now. However, an algorithm has already been developed for quantum computers that can factorize large numbers into prime factors and crack asymmetric encryption in a matter of minutes. Right now, this algorithm exists only in theory, since quantum computers are not yet powerful enough to run it. The number of qubits needed to quickly crack asymmetric encryption methods is fairly well known: Between 2,300 and 4,000.
At present, a lot of research money and energy are being invested in the development of quantum-resistant encryption methods. There are numerous possible methods that the American Institute NIST (National Institute of Standards and Technology) is trying to standardize. There are currently 48 procedures under review that are believed to be quantum-resistant. One of these methods is the Supersingular Isogeny Diffie-Hellmann key exchange method (SIDH), which in contrast to other methods, has the advantage of being less memory-intensive. The development of quantum-resistant encryption methods is also facing problems: On the one hand, the storage space requirements and computational effort are very high for many methods. On the other hand, their security cannot yet be reliably assessed.
The development of quantum-resistant encryption methods shows that the threat posed by quantum computers is being taken seriously. However, when and whether quantum computers will be operational at all is completely unclear. According to a May 2018 study entitled The State of Development of Quantum Computers published by the German Federal Office for Information Security (BSI), because of the high cost of error correction, it is “in the foreseeable future unlikely, and probably also economically unattractive, for academic and industrial laboratories to realize a cryptographically relevant quantum computer.” For intelligence agencies, however, this development may indeed prove more relevant. How realistic the quantum-computing threat is depends on how much progress is made in the development of quantum computers and on what effective, quantum-resistant encryption methods are being developed.