And if you have three qubits, they can be in a superposition of 0, 1, 2, 3, 4, 5, 6, and 7.
Right now, some nation states and individual actors are intercepting and storing lots of encrypted data like passwords, bank details, and social security numbers. But they can’t open these files. So why are they doing it? Well, because they believe that within the next 10 to 20 years, they will have access to a quantum computer that can break the encryption in minutes. This procedure is known as Store Now, Decrypt Later (SNDL). And it works because there is information around today that will still be valuable in a decade, such as industrial and pharmaceutical research and top secret government intelligence. Everyone is aware of this threat, and the National Security Administration (NSA) says that a sufficiently large quantum computer, if built, would be capable of undermining all widely deployed public key algorithms.
It’s estimated that in the next 5 to 10 years, quantum computing will break encryption as we know it today. Even though sufficiently powerful quantum computers are still years away, they’re already a threat because of SNDL, which is why the US Congress just passed legislation mandating all agencies start transitioning right now to new methods of cryptography that can’t be broken by quantum computers.
Our current encryption schemes have been remarkably successful, working effectively for over 40 years. Up until the 1970s, if you wanted to exchange private information with someone, you would first have to meet up in person and share a secret key. This same key would be used to encrypt and decrypt messages, and is known as a symmetric key algorithm. As long as no one else gets their hands on the key, your messages are safe.
But what if you wanted to send information to someone you’ve never met, and it’s too hard to arrange an in-person meeting? You can’t share a key over an unsecured channel like a phone line or the mail, because it could be intercepted. This is what in 1977 led three scientists, Rivest, Shamir, and Adelman to come up with an encryption breakthrough. Today it’s known by their initials RSA, and it works something like this. Every person has two really big prime numbers, all their own which they keep secret. They multiply these numbers together to get an even bigger number, which they make public for everyone to see. Now, if I want to send someone a private message, I use their big public number to garble my message. And I garble it in such a way that it is impossible to ungarble without knowing the two prime factors that made that number. This is an asymmetric key system, since different keys are used to encrypt and decrypt the message. So it’s easy for my intended recipient to decode, but impossible for everyone else, unless they can factor that large public number.
Now, someone could try to factor it, using a supercomputer, in the best known factoring algorithm the General Number Field Sieve, but modern cryptography uses prime numbers that are around 313 digits long. Factoring a product of two primes this big, even with a supercomputer, would take around 16 million years, but not on a quantum computer.
See, in normal computers, a bit can only be in one state at a time, either a zero or a one. So if you had two bits, they could be in one of four possible states, 00, 01, 10 or 11. Let’s say each of these states represents a number, 0, 1, 2, or 3. If we want to do a calculation, for example, raising seven to the power of one of these numbers, we can only do it for one state at a time, in this case seven squared and so we get the answer 49.
Quantum computers consist of qubits which also have two states, zero or one. But unlike a classical bit, a qubit doesn’t have to be in just one state at a time. It can be in an arbitrary combination of those states, a superposition if you will, of zero and one. So if you have two qubits, they can exist simultaneously in a superposition of 0, 1, 2, and 3. And if you have three qubits, they can be in a superposition of 0, 1, 2, 3, 4, 5, 6, and 7. And this is the magic part.If you look at the exponent where the remainder is one, that is the exponent r, in our equation g to the power of r, is a multiple of N plus one.In this case, that exponent is seven.So eight to the power of seven, is a multiple of 77 plus one.If we actually do the calculation, eight to the power of seven is equal to 58, 048.And if we divide this by 77, we get 752 with a remainder of one.So this is the multiple of N plus one, that we were looking for.And if you look at the exponent, that’s the number r, that we were looking for.Now, the prime factors of 77 are seven and 11.So if we take the square root of 58, 048, we get the two prime factors of 77.So seven times 11 is equal to 77.
Now, when we repeat the same calculation, it will actually perform the calculation for all of those numbers at the same time, resulting in a superposition of the different answers: 1, 7, 49 and 343. If we add another qubit, we double the number of possible states. So with three qubits, we can represent eight states, and thus perform eight calculations all at once. Increase that number to just 20 qubits, and you can already represent over a million different states, meaning you can simultaneously compute over a million different answers. With 300 qubits, you can represent more states than there are particles in the observable universe.
This sounds incredibly powerful and it is, but there is one very big catch. All of the answers to the computation are embedded in a superposition of states, but you can’t simply read out this superposition. When you make a measurement, you only get a single value from the superposition basically at random, and all the other information is lost. So in order to harness the power of a quantum computer, you need a smart way to convert a superposition of states into one that contains only the information you want. This is an incredibly difficult task, which is why for most applications, quantum computers are useless.
So far, we’ve only identified a few problems, where we can actually do this, but as luck would have it, these are precisely the problems that form the foundation of nearly all the public key cryptography we use today. In 1994, Peter Shor and Don Coppersmith figured out how to take a quantum Fourier transform. It works just like a normal Fourier transform, apply it to some periodic signal, and it returns the frequencies that are in that signal. Now this may not seem particularly interesting but consider this. If we have a superposition of states that is periodic, that is the terms in the superposition are separated, by some regular amount, well we can apply the quantum Fourier transform and will be left with states that contain the frequency of the signal. So this we can measure. The quantum Fourier transform, allows us to extract frequency information from a periodic superposition, and that is gonna come in handy.
So how does a quantum computer factor the product of two primes much faster than a conventional computer? I want to explain this by first walking through a simple example with no quantum computer required, and then I’ll show how a quantum computer could execute this method even for a very large number in a short period of time. And that is why we can find the exponent R that gets us to one more than a multiple of N.
So there we have it: eight to the power of 10 is one more than a multiple of 77, so we’ve found the exponent R that satisfies this equation. But how does this help find the factors of N? Well, we rearrange the equation to bring one over to the left hand side, and then we can split it into two terms like so. And now, as long as R is even, we have one integer times another integer is equal to a multiple of N. This looks remarkably similar to p times q equals N.
I mean, since we know that p and q are on the right hand side of this equation, they must also be on the left hand side just multiplied by some additional factors. So one way to think about what we’ve done is we’ve taken a bad guess for one of the factors G, and by finding the exponent R, we’ve turned it into two much better guesses that probably do share factors with N.
Since R was 10, the two terms on the left hand side are eight to the power of five plus one, 32,769 and eight to the power of five minus one, 32,767. These two numbers probably share factors with N. So how do we find them? We use Euclid’s algorithm. If you wanna find the greatest common divisor of two numbers, say 32,769 and 77, divide the bigger number by the smaller one and record the remainder. In this case, 32,769 divided by 77 gives a remainder of 44. Then shift the numbers one position left and repeat. So now we divide 77 by 44 and we get a remainder of 33. Repeat the process again. 44 divided by 33 gives a remainder of 11 and again 33 divided by 11 equals three remainder zero. When the remainder is zero, the divisor is the greatest common factor between the two numbers you started with. In this case, it’s 11, which is indeed a factor of 77 and 32,769. You could do the same procedure with the other number or just divide 77 by 11 to get seven, its other prime factor.
So to recap, if you wanna find the prime factors p and q of a number N, first, make a bad guess G, second, find out how many times R you have to multiply G by itself to reach one more than a multiple of N. Third, use that exponent to calculate two new numbers that probably do share factors with N. And finally use Euclid’s algorithm to find the shared factors between those numbers and N, which should give you p and q.
Now, you don’t need a quantum computer to run any of these steps, but on a classical computer, this method wouldn’t be any faster than other methods. The key process that a quantum computer speeds up is step two, finding the exponent you raise G2 to equal one more than a multiple of N. To see why, let’s go back to our example, where eight to the power of 10 is one more than a multiple of 77. Watch what happens to the remainders if we keep going past eight to the power of 10, to eight to the 11, eight to the 12, and so on. Well, we get remainders of 8, 64, 50, 15, 43, 36, 57, 71, 29, and again one. The remainders cycle and they will just keep cycling. Notice how the exponent that yields a remainder of one is 20, which is 10 more than the first exponent that yielded a remainder of one. So we know that eight to the 30 and eight to the 40, eight raised to any power divisible by 10 will also be one more than a multiple of 77.
It’s also worth noting that if you pick any remainder say 15, the next time you find that same remainder, the exponent will have increased by 10. So you can find the exponent R that gets us to one more than a multiple of N, by looking at the spacing of any remainder, not just one. Remember that. Here I’m plotting out the remainders on a log scale so you can see they are periodic with a period of 10. If I had made a different guess, say I had picked G equals 15 instead of eight, well then the period would be different and the remainders would be different but there would always be a remainder of one. Why is this? Well, now that you can see this is a repeating pattern, we can go back to the beginning and any number raised to the power of zero is one. So that We are now ready to use a quantum computer to factor any large product of two primes. We split the qubits into two sets: the first set is prepared in a superposition of numbers from 0 to 10^1234, while the second set contains a similar number of qubits all left in the zero state. We then make a guess G, which most likely doesn’t share factors with N. We raise G to the power of the first set of qubits, then divide by N and store the remainder in the second set. By doing this, we have entangled our two sets of qubits. We cannot measure this superposition, as it would give us a random value and we would learn nothing. However, if we measure the remainder part, we will obtain a random remainder that will occur multiple times every time it comes up in the cycle. This number is the exponent that satisfies our equation. After measuring the remainder, we will be left with a superposition of states that all share the same remainder, and the exponents will all be separated by the same amount r. We can then apply the quantum Fourier transform to this superposition of states and be left with states containing one over R. By performing a measurement and inverting the result, we can find R. As long as r turns out to be even, we can use r to turn our bad guess g into two numbers that likely share factors with N. We can then use Euclid’s algorithm to find the factors of N and break the encryption. In 2012, it was estimated that it would take a billion physical qubits to break RSA encryption, but by 2017 that number had dropped to 230 million. By 2019, after more technological breakthroughs, that estimate plummeted to just 20 million physical qubits. In 2016, the National Institute of Standards and Technology (NIST) launched a competition to find new encryption algorithms that aren’t vulnerable to quantum computers. After rigorous testing, four algorithms were selected to be part of their post-quantum cryptographic standard on July 5th, 2022. So how do they work? Well, three of the algorithms are based on the mathematics of latices. For example, take two vectors, r1 and r2, and by adding together different integer combinations of these vectors, you can get two different points. All the points you can get to by combining these two vectors in different ways is what is called a lattice.
Now, if you are given a point C, your task is to tell which combination of r1 and r2 will bring you to the lattice point closest to C. It’s pretty easy to see that you can get there by going in the direction of r2 twice and in the negative direction of r1 twice.
However, r1 and r2 are not the only vectors that can give you this lattice. Take b1 and b2 for example. These vectors also build up the same lattice. If you are asked the same question again, can you tell which combination of b1 and b2 gets you to the lattice point closest to C? This has become a lot harder, but why is that? Each time you take a step, you’re trying to get closer in either the X or Y direction, but with the b vectors, each time you take a step in the right direction with one vector, it puts you off in the other direction.
In the end, it takes a combination of eight times b1 and negative six times b2 to get to the closest lattice point. That is a lot harder than before, but it’s still a relatively easy problem to solve. But if we extend it to three dimensions, this already becomes a lot harder, especially because you’re not given the collection of all lattice points. You’re only given the vectors that make it up.
So when you find a lattice point close to the target, you must still find all the other lattice points near it to make sure yours is indeed the closest. Let’s take a circle of radius r in two dimensions. The number of lattice points inside the circle is proportional to r^2. Add a third dimension and the number of points in the sphere is proportional to r^3. So just watch how the number of lattice points grows as we increase the number of dimensions.
Solving the closest vector problem is a piece of cake for your computer in three dimensions. Even a hundred dimensions should be manageable. But in proposed future encryption schemes, we’ll use around a thousand dimensions. Take one step in the right direction on one of those dimensions, and you could potentially be taking a wrong step in the other 999 dimensions. You win some, you lose everything else. With that many dimensions, it becomes extremely hard to find the closest point even for the most powerful computers, that is unless you know a good set of vectors.
So how do we use that to encrypt data? Well, let’s go back to our two-dimensional example. Each person has a good set of vectors that describes a lattice, but they keep these vectors secret, and they only share their lattice publicly using a set of vectors that is hard to work with. Now, if someone wants to send a message, they pick a point on the lattice and then add some random noise to it. So the message they send is not precisely at that point but close to it.
To decode the message, the recipient must figure out which lattice point is closest to the message point. In a thousand dimensions, this will be extremely hard to do unless you have the nice set of vectors, which the recipient does. So it’s easy for the recipient, who has the good vectors, but hard for everyone else. And as far as we know, this problem is extremely difficult to solve for both normal and quantum computers. The world is changing fast, and with it come new technologies such as quantum computers and AI chatbots. To understand and stay ahead of these developments, it is important to learn how they work. With Brilliant courses on quantum algorithms and data analysis, you can get up to speed quickly. Brilliant breaks down complex topics into bite-sized, interactive lessons, and offers a free trial and a 20% discount for the first 200 people to sign up. Thanks to Brilliant for sponsoring this video and for helping us stay safe and informed!