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.
Related: 9 Companies to watch in AI Cybersecurity
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.
See also: Common encryption types explained
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.
The Open Quantum Safe project
On top of NIST’s search for suitable algorithms, the Open Quantum Safe project has also been launched. As a collaboration between academics and the open source community, backed by industry funding, it aims to support the “development and prototyping of quantum-resistant cryptography”.
The Open Quantum Safe project is currently focusing on two main objectives:
- Developing liboqs – an open-source library for quantum-resistant cryptographic algorithms.
- Prototyping integrations of cryptographic algorithms into various protocols and applications.
Post-quantum public-key algorithms
At this stage, five main approaches for public-key algorithms are thought to be resistant to quantum-computing attacks. These are hash-based cryptography, lattice-based cryptography, supersingular elliptic-curve isogeny cryptography, multivariate cryptography, and code-based cryptography.
Research into their security and usability is ongoing, but it is hoped that at least one option based on these techniques will be suitable for the post-quantum cryptographic world.
Hash-based cryptography
These systems for digital signatures have been around since the 1970s, but fell out of favor because under these schemes, a private key can only be used to sign data a limited number of times. Because these mechanisms are hash-based, rather than number-theoretic like the signature schemes we currently use (RSA, DSA, ECDSA, etc.), they aren’t vulnerable to known quantum-computing attacks.
This resistance ignited new interest in their properties and potential applications. Hash-based cryptography keys would need to be 36,000 bits long to grant 128 bits of security and be able to sign one million messages.
Lattice-based cryptography
Lattice-based cryptography involves a range of different approaches that rely on the properties of lattices. There are a number of different lattice problems which make their underlying structure resistant to both classical computing and quantum computing attacks.
Lattice-based cryptographic systems such as NTRU seem like promising candidates. After rigorous study, no major security concerns have been found. A team of academics recommended a 6,130-bit public key and a 6,743-bit private key for 128 bits of security with the NTRU algorithm.
Supersingular elliptic-curve isogeny cryptography
This method involves using both supersingular isogeny graphs and supersingular elliptic-curves to create a public-key exchange that has perfect forward secrecy. It works similarly to the Diffie-Hellman key exchange and has been scrutinized quite heavily.
The latest research shows that a 3,073-bit public key can give 128 bits of security under this system. This is the smallest key size for any of the systems that have been evaluated so far, with a similar size-to-security ratio as RSA.
Multivariate cryptography
These schemes are based on the concept that multivariate equations are difficult to solve. There are a range of different systems, and the most prominent has the quirky name of Unbalanced Oil and Vinegar.
At this stage, these systems seem to be most effective for digital signatures, because they produce the shortest signatures. Current research suggests that they are less useful when it comes to encryption.
As an example, an analysis of the Rainbow algorithm showed that it could provide 128 bits of security with 424-bit digital signatures, but public keys would have to be 991,000 bits and private keys would have to be 640,000 bits for the same level.
Code-based cryptography
One of the most prominent examples of this type of cryptography is the McEliece algorithm, which relies on the difficulty of decoding a general linear code. It has been studied for over 30 years and is resistant to known quantum-computing attacks.
There are a number of potential ways to implement this system. The technique with the smallest key sizes would need a public key of 32,771 bits and a private key of 4,384 bits to provide 128-bit security.
Quantum computing & symmetric-key cryptography
Symmetric-key encryption is the type of cryptography that you are probably most familiar with. It uses the same key in both the encryption and decryption processes, and it appears in a wide variety of applications, from encrypting your hard drive, to locking down the information that is transmitted between your web browser and an HTTPS website.
This type of encryption is a fundamental part of keeping our communications safe. Without it, our data would be far more vulnerable to attackers and eavesdroppers. The good news is that symmetric-key encryption is far more resistant to known post-quantum computing attacks than public-key cryptography.
Grover’s algorithm
At this stage, Grover’s algorithm is the biggest quantum-computing threat that can be used against our commonly used symmetric-key encryption methods. Others may arise in the future, but so far, Grover’s algorithm is the biggest concern.
It was developed by Lov Grover in the 1990s and it has the capability of calculating the key that was used to encrypt data with a high likelihood of success. Attackers could, therefore, use it to obtain keys that were used to encrypt data, giving them free reign to access the contents.
Again, since the quantum computers of today are nowhere near capable of running such a complex attack, Grover’s algorithm is not currently considered a threat. Despite this, if quantum computers do emerge and fall into the hands of adversaries, they will be able to use the algorithm to brute force the keys of their targets.
The threat of Grover’s algorithm is nowhere near as severe as those that loom ahead of public-key cryptography. Practically speaking, Grover’s algorithm is only able to reduce the security of a cipher like AES by half. That means that against Grover’s algorithm, a 128-bit AES key would only have the practical security of a 64-bit key.
There is a relatively simple solution to this threat: doubling the key length. If we wanted our data to have a security level of 128 bits against Grover’s algorithm, we would simply use a 256-bit AES key. Although the threat is certainly real, the countermeasures for protecting our symmetric-key algorithms are relatively simple, so cryptographers are not particularly worried about attacks based on Grover’s algorithm.
Quantum computing: More than just a security threat
At this stage of the article, you might be beginning to think that quantum computing is all bad news when it comes to internet security and cryptography. Despite the complications that quantum computing may bring to these fields, there could also be some benefits.
The unique properties of quantum mechanics open up a world of new opportunities when it comes to secure communication. Some of these, such as quantum key-distribution, are already being used. Potential quantum mechanisms for the future include Kak’s three stage protocol and quantum digital-signatures, among other possibilities.
Quantum key-distribution
Quantum key-distribution is much like any other key exchange protocol. It allows two parties to securely establish a symmetric key which they can use to encrypt their future communications. The main difference is that it leverages the unique properties of quantum mechanics, allowing the two parties to detect if an attacker is eavesdropping on the messages.
This is made possible because of one of the fundamental principles of quantum mechanics: Any attempt to measure a quantum system will alter it. Since intercepting data is, in essence, a form of measurement, a quantum key-distribution scheme will detect any anomalies that come from an attacker eavesdropping and abort the connection.
If the system does not detect any eavesdropping, the connection will proceed, and the parties can be certain that the key they have developed is secure, as long as adequate authentication has taken place.
Quantum key-distribution is currently used in certain situations where the need for security is high, such as banking and voting. It is still relatively expensive and cannot be used over large distances, which has prevented further adoption.
Kak’s three-stage protocol
Subhash Kak’s three-stage protocol is a proposed mechanism for using quantum cryptography to encrypt data. It requires the two parties in the connection to first be authenticated, but can theoretically provide a way to continuously encrypt data in a way that is unbreakable.
Although it could be used to establish keys, it differs from quantum key-distribution because it can also be used to encrypt the data. Quantum key-distribution only uses quantum properties to establish the key–the data itself is encrypted using classical cryptography.
Kak’s three-stage protocol relies on random polarization rotations of photons. This method allows the two parties to securely send data over an unsafe channel. The analogy that is usually used to describe the structure is to picture two people, Alice and Bob. Alice has a secret that she wants to send to Bob, but she does not have a safe communication channel over which to do so.
To securely send her secret over an insecure channel, Alice puts her secret in a box, then locks the box with a chain around the outside. She then sends the box to Bob, who locks the box with his own chain as well.
Bob then sends the box back to Alice, who takes off her lock. She then returns the box to Bob. Since the box now only has Bob’s lock protecting it, he can unlock it and access the secret data.
This method allows Alice to send Bob a secret without any third party being able to access it. This is because the box has at least one person’s lock on it each time it is sent across the insecure channel.
Quantum digital signatures
Quantum computing threatens our commonly used digital signature schemes, since they rely on public-key ciphers that are vulnerable to Shor’s algorithm. However, the new technology also opens the door to quantum digital signatures, which would be resistant to these attacks.
Quantum digital signatures would work just like normal digital signatures, and could authenticate data, check its integrity and provide non-repudiation. The difference is that they would rely on the properties of quantum mechanics, rather than on mathematical problems that are difficult to reverse, which is what the systems we currently use are based on.
There are two different approaches to quantum digital signatures:
- A classical bit string is used for the private key, and a public quantum key is derived from it.
- A quantum bit string is used for the private key, and a public quantum key is derived from it.
Both of these types of quantum digital signatures differ from classical digital signatures, because they use one-way quantum functions. These functions would be impossible to reverse, while classical one-way functions are just incredibly difficult to reverse.
Quantum computing: Should you be worried?
Practical quantum computing is still on the distant horizon and there is a lot that we don’t know about it. Its harshest critics think that quantum computing will never be useful, while some of the companies involved in its development estimate its commercial arrival at some point in the next five to 15 years.
At this stage, significant challenges lay ahead for scientists. Current machines aren’t powerful enough, and the issues surrounding quantum decoherence need to be resolved.
While these factors seem to be keeping our current cryptographic systems safe for now, there is still the risk that new algorithms, techniques, and attacks will be discovered. If quantum computing does finally arrive, these could pose far greater risks than anyone anticipated.
Despite these unknowns, a lot of money is being thrown into quantum computing and the study of its ramifications on security. Industries, government bodies, and academics are all working to prepare for a post-quantum future which may never arrive, just in case.
This is important, because the risks are great and the areas that need to be studied are extensive. On top of this, it takes years to develop, analyze and standardize new cryptosystems.
While quantum computing is still years away, if we weren’t already starting to work on precautionary measures now, a worst case scenario could lead to quantum computing falling into the hands of attackers before the appropriate defense mechanisms are in place. This would be catastrophic for all of our digital communications.
The risks are real and there is the slight possibility of things turning disastrous. However, a realistic analysis of the development of quantum computing and the precautionary measures that are being studied alongside it indicates that the world is on track to manage these risks effectively.
If practical quantum computing arrives, it is likely that it will disrupt some of our currently used cryptographic systems. Despite this, alternatives that are assumed to be secure are already in the pipeline.
As long as we continue along our current path and no sudden surprises emerge, the potential arrival of practical quantum computing should not cause any major disruptions or upheaval. For now, there’s nothing to worry about–the scientists seem to have everything under control.
Quantum physics particles by Geralt licensed under CC0