Is quantum computing a threat to cybersecurity? (1)
by Josh Lake – Specialist in security, privacy and encryption
Quantum computing looks like it could revolutionize our technological world in the not too distant future. Find out what it is and how it may affect our security.
Quantum computing is looming on the horizon. Although it’s still a fair distance away and must traverse numerous stumbling blocks, its possible arrival presents a big step for technology and our society.
One area where it will have a significant impact is in the realms of cryptography and cybersecurity. The new techniques associated with quantum computing have the potential to turn the cryptographic world upside down, with severe implications for information security as well as the world at large.
Want to find out what quantum computing is and why it might have significant effects on our online security? Then keep reading, because we will discuss these complex concepts as simply as possible, to help you understand the nature of quantum computing and its possible ramifications.
What is quantum computing?
In essence, quantum computing leverages the properties of quantum mechanics to perform computations. This contrasts with our everyday, or classical computers, which adhere to the properties of classical physics.
Quantum computers rely on units of information known as qubits. These can exist in states of zero and one, as well as superpositions of both zero and one. In comparison, classical computers just use ones and zeros to store information.
The details of how it works are as complicated as the word quantum tends to imply. Assuming that most readers don’t have a high-level physics background, we won’t take a deep dive into the underlying properties of quantum computing and the theory behind it.
Instead, we will focus more on its implications.
What can quantum computers do?
Because quantum computers work under completely different principles than the computers that we use in our daily lives, they also have different capabilities. Many experts expect that they will be able to compute things and solve mathematical problems that classical computers simply aren’t able to do. Those in the field refer to this achievement as quantum supremacy, although it has yet to be reached.
Some of the potential applications of quantum computing include:
– Modeling complex chemical reactions, which may lead to innovation and advances in chemistry;
– High-level financial modeling;
– Predicting weather and climate fluctuations with greater accuracy;
– Running more complex AI programs;
– Advanced computations in physics;
– Breaking currently secure cryptographic algorithms, as well as introducing new cryptosystems.
Why are quantum computers a threat to cybersecurity?
As we mentioned above, the unique properties of quantum computers would allow them to perform computations that are currently impossible with classical computers.
This could have a significant impact on the cybersecurity landscape. Significant portions of our digital security rely on cryptographic calculations that are easy to perform in one direction, but almost impossible to perform in reverse. Even common encryption algorithms that we use to secure data today can’t be brute forced without a huge amount of time and computing resources.
This comes with a caveat: These calculations are only infeasible to reverse using current technology and techniques.
Quantum computing represents a new wave of technology that will come with a host of different techniques, some of which are already known to be able to break various cryptosystems that we rely on to keep our everyday communications safe.
If quantum computers fall into the hands of attackers, they would theoretically be able to use them to break systems that are considered secure against classical-computing attacks, allowing the attackers to access data that was previously secure.
At this stage, quantum computing presents the biggest threat to our most commonly used public-key encryption schemes. Some symmetric-key algorithms will also be affected, but not to the same degree.
Of course, the field of quantum computing is still full of surprises, so it’s not out of the realm of possibility that at some stage, other major vulnerabilities will be found in various cryptographic systems.
When will we have quantum computers?
The expected arrival date of practical quantum computers depends on who you talk to. Quantum computers already exist, but are incredibly unstable and weak at this stage, making them essentially unusable for any serious computations. The companies leading the charge include Google, Intel, IBM and D-Wave.
In 2016, D-Wave announced a 2,000-qubit quantum computer chip. However, the quantum annealing method it uses is controversial among experts, with some scientists asserting that it is no faster than classical computing.
In 2017, IBM announced a 50-qubit quantum computer, while Google upped the ante in 2018 with Bristlecone, a 72-qubit quantum computer. Despite these efforts, quantum computing won’t have many practical applications until scientists can cut down on quantum decoherence and the number of qubits is significantly increased.
IBM Q is an initiative that allows the public to access quantum computers through the cloud. The company has commercial offerings, as well as a number of different quantum computers that anyone can use for free. At this stage, the largest quantum computer that the public can freely use is 14 qubits.
According to Wired, the CTO of Intel, Mike Mayberry, expects the technology to be commercialized within 10 years. The same article quotes IBM as aiming to make the technology mainstream within five years. Other experts believe a 15-year timeline is more realistic.
Despite these predictions from some of the world’s biggest tech companies, there are also some experts, such as Gil Kalai, who believe practical quantum computing will never be achieved. However, it seems like most people involved in the field disagree with this opinion.
What challenges lie in the way of quantum computing?
Quantum computers are extremely temperamental machines, which makes them immensely difficult to build and operate. They need to be isolated from the outside environment and kept almost at absolute zero (-273ºC) in order to be usable. If not, they produce quantum decoherence, which is essentially the loss of information to the environment.
Quantum decoherence can even be generated within the system itself, through the effects of things like background thermonuclear spin or lattice vibration. Once quantum decoherence is introduced to a system, it cannot be removed, which is why quantum computers need to be so tightly controlled in order to be usable.
At this stage, numerous technological challenges need to be surpassed in order to produce a sizable quantum computer with minimal quantum decoherence. Until solutions can be found to address these challenges, quantum computing will remain impractical.
Quantum computing & public-key cryptography
Public-key cryptography uses separate keys for the encryption and decryption, one of which is public and another that is kept private. Refer to our article on public-key cryptography if you want to learn about the process in more detail.
These cryptographic systems are an essential part of many of the under-the-hood mechanisms that keep our online world safe. Public key cryptography is used for:
– Authorization of the other party in a connection – public key encryption is generally combined with digital certificates to verify that the other party in a connection is who they say they are, and not an impostor.
– Developing shared keys – These can be used to secure the data in a connection.
– Digital signatures – These are involved in authorizing other parties, verifying the integrity of data, and providing the quality of non-repudiation (if something is non-repudiable, it means that the person who is responsible has no acceptable way of denying their involvement).
– Encryption – In practice, public-key encryption isn’t used to encrypt the bulk of data. Instead, it is used to encrypt a symmetric key, which then encrypts the data in a more efficient manner.
The above aspects are critical for everything from normal web-browsing to transferring huge sums of money. If quantum computing becomes practical, it threatens to completely undermine commonly used public-key encryption systems such as RSA, the Diffie-Hellman key exchange, and the elliptic-curve variants.
How?
Each of these algorithms rely on mathematical problems which are easy to compute in one direction, but essentially impossible to do in reverse, at least under current technology and techniques. These calculations are integer factorization for RSA, the discrete logarithm problem for the Diffie-Hellman key exchange, and the elliptic-curve discrete logarithm problem for elliptic-curve cryptography.
Let’s discuss integer factorization to give you an idea of how mathematical problems can be easy to do in one way, but difficult in the other. We won’t cover the other two, because they are a little more complex, and we’re just trying to get the general idea across.
Integer factorization
The security of RSA is based on the difficulty of factoring prime numbers. Let’s say you were asked, “Which two prime numbers multiply together to give you a product of 748,607?”
You probably wouldn’t even know where to start, other than trial and error. If you could figure out the answer, it might take you hours.
Okay, let’s try another problem. What’s the result of:
739 x 1013
If you have a calculator handy, it’s easy. If you’re really good at multiplication, you might even be able to figure it out in your head. What’s the answer?
748,607
Looking carefully, you may have noticed that these two problems are the same, just in reverse. As you can see, it’s pretty easy to calculate the product of two prime numbers, but much more difficult to find those numbers if you have only been given their product.
This is the underlying idea of the RSA algorithm, albeit with numbers that are many times larger. It’s comparatively fast and easy to compute in one direction, but solving the problem the other way requires significantly more time and computing power. This feature allows us to encrypt our data relatively quickly and easily, but makes it almost impossible for attackers to break the encryption.
Enter Shor’s algorithm
In 1994, a mathematician named Peter Shor devised a quantum algorithm which could be used to find the factors of a number (such as those in the example above) in a relatively simple way. This means that it could be used to break some of our common public-key algorithms.
Since it’s a quantum algorithm, it needs a quantum computer to solve the problem. Because these computers are still weak and inherently unstable, Shor’s algorithm isn’t much of a threat at the moment. But as the technology behind quantum computers improves, we are slowly edging towards a world where we can no longer rely on our commonly used public-key algorithms.
At this stage, Shor’s algorithm is probably the biggest cryptographic threat that our society faces from the potential arrival of quantum computing. But the end is not nigh, and there are a range of other systems which look like they will be able to provide similar functionality to our current ciphers, without vulnerabilities to Shor’s algorithm.
This field of study is known as post-quantum cryptography. Industry, academics and government bodies are heavily involved in it and are well on their way towards coming up with solutions.
NIST’s post-quantum cryptography initiative
The US’s National Institute of Standards and Technology (NIST), which is responsible for setting standards for government and industry, has launched a program that aims to evaluate a range of different post-quantum algorithms to find one or more that would make suitable standards.
The agency aims to find an algorithm resistant to both quantum computing and classical computing attacks. At this stage, the project is in its second round, with 17 encryption and key-establishment protocols, as well as nine digital signature protocols having made the cut.
It’s not known how long it will take for NIST to establish a new standard. This current stage is expected to take between 12 and 18 months, however, there may be a third round if necessary. These algorithms need to be analyzed and tested rigorously to ensure that they are both usable and secure.
As an example of just how long the process of standardizing a new algorithm can take, it took NIST over five years to go from its announcement that it was searching for an algorithm, until the Advanced Encryption Standard (AES) officially became a federal government standard.
Read the second part of the article
yogaesoteric
April 21, 2020