Quantum computers
Quantum computing and quantum communications; these concepts were invented just 30 years ago, after scientific journals refused to issue earlier publications regarding these subjects because it looked more like science-fiction. Nowadays, quantum systems really do exist, with some of them reaching the stage of commercial sales. Quantum computers raise and answer new questions in the security field, primarily in cryptography.
We live in a world of radio waves and electromagnetic signals: Wi-Fi, GSM, satellite TV and GPS, FM-tuner and speed camera are just some examples of electromagnetic wave usage in our daily lives. Of course, computers are an integral part of this ecosystem, be it a mainframe, laptop or a smartphone. A very important feature of electromagnetic signals is measurability. It’s quite easy to read all the parameters of a signal without introducing changes to it, and this is the exact reason why almost every aforementioned technology today is equipped with encryption, which protect transmitted information from being read or altered by a third party. Typically, communicating parties don’t have another channel to talk, and cryptosystem developers brilliantly solved a very complicated problem – how to negotiate a secret encryption key when all communication might be observed by others. The solution to this problem is the foundation for all modern protection systems, and quantum computers might break it. Will quantum cryptography become a next-generation security solution? Let’s find out.
The tagline
The names “Quantum computing” and “Quantum cryptography” are accurate. These systems are based on quantum effects like superposition and entanglement of micro-particles.
The primary difference between ordinary and quantum computers is a data unit. While an ordinary computer uses bits and bytes, which are strictly 0 or 1, a quantum computer uses qubits (quantum bits), which are able to be in several states simultaneously. It sounds confusing, and it’s even more confusing to implement, but years of research clearly show that it works. A quantum computer is wildly different from an ordinary one and it’s barely possible to use it for Tetris, but it performs much better in probability-related or optimisation-related task solving.
The list of tasks, which might be dramatically sped up using quantum computing, is quite long: logistic optimisations, DNA sequencing, stock market predictions and cryptographic keys brute-forcing. It is worth mentioning that everything in the quantum world is complicated and it takes much effort to read an “answer” given by a quantum computer. However, each task runs several times, and it doesn’t take too long. Therefore, it’s possible to obtain a final answer (read: encryption key) by comparing results of these runs.
All quanta are in the white box on the right
Deep dive: Modern systems in the core of SSL, HTTPS, VPN, etc., are typically encrypted data using a secret key and symmetric algorithm. It’s the same on the sender and receiver sides (hence symmetric), which negotiate a secret key in the beginning of the session using another, asymmetric cryptosystem. Asymmetric algorithm is used just for secret key negotiation because it’s computational-heavy. Security of asymmetrical cryptosystem is based on solving the complexity of some mathematical problem. e.g. integer factorisation of very large numbers (RSA algorithm). It takes noticeable time just to multiply or divide such large numbers, to say nothing about trying multiple numbers in order. So the cryptosystem setup assumes that a spy can eavesdrop on the connection, but it will take an unreasonable amount of time (from dozens to millions of years depending on key length) to calculate a secret key and decrypt the connection. It turns out that quantum computers might help here. Using Shor’s algorithm, a quantum computer comes to a final state corresponding to solved mathematical problems very quickly, almost as fast, as an ordinary computer multiplying a couple of numbers. Despite some extra issues, like the necessity to run this task several times and complicated results reading with the help of classical computers, a quantum computer might find the required large numbers very quickly, helping an attacker calculate the secret key and decrypting the message.
By the way, good symmetric algorithms, e.g. AES, don’t have flaws allowing that kind of dramatic bruteforcing speedup. By existing estimates, bruteforcing 256-bit AES key on a quantum computer is equal to bruteforcing 128-bit AES on a classic computer, so security levels remain very high.
Where the shoe pinches
Quantum computers don’t reside on the desktop of every other teenage hacker wishing to eavesdrop on his classmates’ Facebook sessions for good reason. Creation of a full-scale quantum computer involves many engineering challenges that some specialists consider to be impossible to accomplish. The main challenge is making sure qubits are entangled, because each quantum system tends to collapse into a classical state, lacking valuable undetermined properties. We can’t avoid mentioning the long-suffering Schrödinger’s cat here, which eventually can’t stay both dead and alive simultaneously – a quantum computer, however, must maintain this miraculous state for a long enough time to perform calculations and measure results. Modern prototypes can keep this state for milliseconds, and in some cases, a couple of seconds. The task becomes more and more complicated when the qubit count rises too. To break cryptosystems, computers must have 500-2000 qubits (depending on the algorithm and key length), but existing quantum computers operate with 14 qubits at maximum. That is why today’s quantum computers are not usable for breaking your SSL certificate, but the situation may change in 5 years.
Main expositors of science in general and specifically Schrödinger’s cat – Penny and Sheldon of “The Big Bang Theory”
Steps toward quantum goal
Against this background, Canadian company D-Wave brassily claims that it produces 512-qubit quantum computers. Moreover, these devices are available for sale. Many experts say that the D-Wave computer is not “real”, because it utilises a quantum annealing effect and can’t demonstrate full properties of a quantum computer. However, it’s complicated to argue with piles of cash, and D-Wave has customers willing to pay $10 million for the device, such as the military contractor Lockheed Martin and search giant Google to name a few. In spite of existing controversy, the computer solves a specific subset of optimisation tasks using methods, which are quantum in nature and bring real value to customers. Google plans to experiment with machine learning and Lockheed Martin believes that a quantum computer is able to find mistakes in the source code of software used in F-35 jet fighters. D-Wave scientists admit that their computer is unable to solve some other “quantum” tasks, e.g. aforementioned integer factorisation, so it poses no threat for modern cryptoalgorithms. However, there is another threat: real and functional quantum computers inspire big companies and governments to invest more in quantum development, speeding up the creation of other, cryptography-capable computers.
D-Wave Two — quantum computer-annealer
Quantum cryptography
Quite amusingly, quantum physics might offer the remedy to threats it poses. Theoretically speaking, it’s impossible to eavesdrop on a connection if it’s based on a single micro-particles transmission – quantum physics laws say that to try to measure one parameter of a micro-particle will alter another parameter. This phenomenon, known as the observer effect (and often confused with the uncertainty principle), should resolve the main issue of “classical” communications – the possibility of eavesdropping. Each attempt to spy on a communication will alter the transmitted message.
In quantum communications, significant interference means that an unwanted third party monitors the connection. Of course, you want to prevent information leaks, as well as know that it happens. That is one of the reasons why modern quantum cryptosystems only use “quantum” communication channels to negotiate session encryption keys, which are used to encrypt information transmitted via traditional channels. So a potentially intercepted key is rejected and parties negotiate a new key until transmission comes unaltered. We see that quantum key distribution (QKD) system is being used exactly in the same role, as asymmetric cryptoalgorithms, which may fall to quantum attacks soon.
Meet Cerberis, commercially available quantum key distribution system
Unlike quantum computers, quantum cryptosystems have been available commercially for quite a long time. First scientific research emerged circa 1980, but practical implementation appeared swiftly. The first lab tests were conducted in 1989, and at the end of the century there were commercially available systems able to transmit an encryption key over a 30-mile long fibre optic. Companies like id Quantique and MagiQ Technologies sell ready out of the box QKD systems, which are simple enough to be installed by a network technician. In addition to government and military institutions, QKD users are multinational corporations, banks and even FIFA.
Perfect protection?
In theory, quantum communication systems do not allow stealthy eavesdropping, but current implementations were demonstrated to have some flaws. First, to avoid interference and allow long-distance transmission, the system transmits multiple photons. Of course, developers try to keep that at a minimum, but there is a theoretical possibility to intercept one photon and analyse its state without touching others. Second, there is a distance limit (about 100 miles) for current systems, which makes their use much more limited. Geographically distant branches would not be able to communicate without some “repeater”, which becomes an obvious point for man-in-the-middle attacks.
Third, hackers of the physicist world discovered, that by “bliding” photodetectors with a powerful laser, they are able to manipulate its readings, which enables all kind of data manipulation in QKD systems. All these are implementation flaws. However, it clearly demonstrates, that quantum systems are by no means silver bullets and protection of transmitted data, even if implemented in the domain of physics instead of maths, still remains a problem for decades ahead. And there is one more thing. Unlike existing technology, quantum devices will remain niche for many years, you won’t encounter dozens of them in each office or apartment as it currently happens with Wi-Fi or smartphones. That’s why it’s too early to dismiss maths – classic cryptosystems, which are able to work over any physical communication channel, will remain in high demand for many decades. However, there is a need to pick new algorithms, more resistant to quantum computing.
Tips