Encryption is at the heart of everything we do on the internet. It ensures that confidential information stays confidential and let’s us know that people are who they say they are.
However, in theory quantum computers should be able to defeat encryption as quantum computers present all possible solutions to any equation in one step. That at least is the vision of proponents of the technology. But physicists doubt that it is possible to build a real quantum computer for various reasons. Tests run against the D-Wave quantum computer, the first quantum device on the market, have concluded that, at best, that device is not really quantum, but rather what some have called ‘quasi-quantum’.
What does all of this mean? Why is it important? If someone could actually build a working quantum computer, then they would render current encryption technology useless. To appreciate this point, it is necessary to understand how a quantum computer works and why current computing technology cannot crack the encryption problem, and to look at the mathematical principles behind this. We try to offer the simplest possible explanation.
The Quantum Concept
Quantum mechanics is the physics of items that are very small, i.e. subatomic particles. They have strange and counterintuitive properties, effectively allowing one particle to be in two places at the same time. Robert J. Oppenheimer, a world-famous physicist, was among the first to suggest that this physical property could be used by computers to solve problems in a new way. He said that if you could control the movement of particles, then you could keep them in a state of superposition, which refers to the property of a single particle being in two places at once.
But there is another law of physics that casts doubt on this. It is called the Uncertainty Principle. This principle says that you cannot tell where a particle is at any one moment, because any effort at measuring this will cause it to move from its current position. As a result, physicists are highly sceptical that quantum computers can actually be made to work. Yet D-Wave computing claims to have already built such a machine.
At first glance, what they built would seem to fit the definition of quantum. They have built a CPU circuit that holds both a positive (true) and negative (false) electrical charge at the same time. Contrast this with the circuits in semiconductors, like Intel chips, which are either open (true) or closed (false), but not both.
The Mathematical Difficulty of Cracking Decryption
To appreciate its possible usefulness, it is necessary to understand the difficulties involved in trying to defeat encryption. Hence, it is important to look at some mathematics. Encryption is based on the principle that the mathematical algorithm used to encrypt data is too difficult to solve by a computer within any reasonable period of time. Mathematicians working at Princeton, for example, wired together hundreds of computers in order to work on trying to find the value of a 1024 bit encryption key, such as that used by SSL. It took 2 years.
D-Wave have not demonstrated that they can defeat encryption any faster than that, nor have they claimed to have done so. But they have been successful in solving a similarly complex problem, which is called the optimization problem. As a result, they were able to sell some of their machines to Boeing and others who have put them to use to do precisely that.
The Optimization Problem
Solving the optimisation problem would be a game changer for businesses. It affects DHL, FedEx, and UPS every day, i.e. how best to make all their deliveries yet use the least amount of fuel. This is also called the transportation problem. Google Maps, for example, also tackles the transportation problem when you ask it for directions.
To solve this issue, Google uses a technique called linear programming. Let us briefly explain how this works: From high school algebra you might remember the basic linear equation f(x)=y=mx + b, which describes a line. In this equation m is a coefficient and b is the y intercept. If we put a constraint on this formula such as x > 4, then we can optimize this formula, i.e. find its maximum or minimum value.
When FedEx computes what route to drive to fill their deliveries, they are looking for the minimum value in the formula that represents how many packages they have to deliver and how far each customer is located from each warehouse, airport, truck depot, etc. So they are looking to solve an equation like the one above. But their equation has many more variables than just one x. They have to handle hundreds or thousands of constraints. And they have to solve many equations all at the same time. In other words, they are looking to identify the coefficients that give the minimum value for something like:
ax + by + cz < 200
ex + fy + gz < 300
hx + iy + jz < 400
x > 5
y < 30
z > 10
Except their actual equation is much larger.
You can solve a set of equations like this in Microsoft Excel using Google Sheets’ linear optimisation add-on, as long as there are not too many inputs. By using a computer, there are various algorithms to speed that up. But when the set of equations and the number of input variables is large, it could take hours or days for even a very large computer to do that. In theory, a quantum computer could do this in just one step. If it can hold all possible values for the coefficients a, b, c, d, etc in its memory at the same time, then it just needs to pick the combination that yields the optimal (minimum or maximum) value.
Prime Numbers and Encryption
What about encryption? How is this problem different or related to the transportation problem? What makes encryption so difficult is that there is no algorithm that can provide shortcuts to solving that. Cryptographers designed encryption to be complicated on purpose. So the computer can do nothing but try all possible values until it finds one that works. But if a quantum computer could hold all possible guesses in its computer chips, called qubits, then one of those answers is the correct answer to the encryption problem. The problem here is finding the encryption key. Apply that answer to encrypted text and you can decrypt it. So, what exactly is the encryption problem?
Mathematicians have been trying for 2,000 years to find an algorithm that will determine whether a number is prime or, if not possible, to at least determine its prime factors.
The best minds in mathematics, Euclid, Gauss, and Euler have looked at, but did not solve this problem. They have found many interesting properties of prime numbers that would speed decryption. But a computer still has to try all possible values when it is looking for the encryption key. So, there are no short cut algorithms that you can plug into the computer. The best they can do is use the algorithms that make this guessing run faster.
To recall, a prime number is a positive whole number that is divisible only by itself and 1. For example:
|2||Prime, because there are no whole numbers less than 2 that divide 2.|
|4||Not prime, because 4=2×2|
|6||Not prime, because 6=2*3.|
What about 132? That one is even, so it is not prime, because all numbers ending in 2 are divisible by 2. What about 123? That one is divisible by 3 because the sum of the digits 1+2+3=6 are divisible by 3. Those are examples of tricks that can be used to determine whether a number is prime. And there are other tricks that can determine whether a number is probably prime.
But what about a number like: 12121000100219291929192900044488288221? The only way to see if you can factor that number is to churn through all the prime numbers less than the square root of that. (As they teach in grammar school, you only need to go up to the square root because of the commutative property of mathematics. In other words 6=2*3=3*2.)
Encryption exploits the intractable nature of this problem. The RSA and elliptic curve (ECC) encryption algorithms both use prime numbers as their key. In the case of RSA, the encryption key is the product of two prime numbers. So as you search through numbers, looking for one that divides that, when you find one divisor you know the other, as there are only two. So you have found the key.
To give an example, suppose an encryption key is the product of these two prime numbers: 103 x 107 = 11,021.
Encryption works like this:
- First you take some text and convert it to numbers. So ‘Here I am’ becomes ‘123’.
- Then you use an encryption algorithm and plug in that number and the encryption key. Suppose the encryption algorithm says to just multiply one number times the other. So 11,021 * 123 = 1,355,583.
- Then send that encrypted message to recipient and they divide that value by the original key to get “123”.
- Then they turn that number “123” back into the original text “Here I am.”
Shor’s algorithm is an algorithm developed by Peter Shor that in theory could use the quantum nature of qubits to find the prime factors in RSA or ECC encryption keys. However, so far it has not been made to actually work on any quantum computer. As of 2001, the largest integer they had factored was the number 15, which is of course 15=3*5. While this was a long time ago, even since then there has not been enormous progress.
This algorithm does not solve the prime factorization problem. Instead, it takes advantage of the quantum phenomena to guess all possible solutions faster. So instead of taking perhaps years to decrypt encrypted data, it might do it in seconds, hours, or days. The NSA is using one to try to do just that.
The problem is that while the logic behind the algorithm is sound, no one has built a quantum computer that provides the true quantum status of superposition needed to make it work. There are many problems to overcome. For example, one atom introduced into the vacuum around the D-Wave CPU will upset the quantum state. So D-Wave cools its device to almost absolute value, which is colder than the temperature of deep space. At that temperature particles stop moving. The other problems are related to writing the software code for the operating system.
What Does the Future Hold?
It would be devastating if someone could apply Shor’s algorithm and crack the RSA encryption algorithm. We would have no way of protecting our secrets. History suggests that if D-Wave, Google, NASA, and IBM keep plugging away at this engineering, they will eventually solve the challenge. When that happens, someone will have to find a new way to encrypt data – one that does not rely on an intractable problem in mathematics.