How Quantum Computers Break The Internet... Starting Now
- 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 or SNDL. And it works because there is information around today that will still be valuable in a decade.
Things like industrial and pharmaceutical research and top secret government intelligence, and everyone is aware of this threat. The National Security Administration says that a sufficiently large quantum computer, if built would be capable of undermining all widely deployed public key algorithms. - You know in a five to 10 year timeframe, 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 Store Now Decrypt Later, 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. You know, 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. So it's known as a symmetric key algorithm. As long as no one else gets their hands on the key, your messages are safe. But now what if you wanna 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. And this is what in 1977, led three scientists, Riverst, 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 wanna 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. Now, when we repeat the same calculation, it will actually perform the calculation for all of those numbers at the same time. And what we're left with is a super position 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. So let's say we have a number N, which is the product of two primes, p and q. For the sake of this example, let's set N equal to 77.
Now I bet you can guess the prime factors, but let's pretend for the moment that we don't know them, because with a product of really big primes, we wouldn't. Now I want to use a fact about numbers that feels like magic. Pick a number g that doesn't share any factors with N.
If you multiply g by itself over and over and over, you will always eventually, reach a multiple of N plus one. In other words, you can always find some exponent r, such that g to the power of r, is a multiple of N plus one. Let's see how this works. Pick any number that is smaller than 77.
I'll pick the number eight. This number doesn't share factors with 77. And if you were doing this with big primes, it would also be extremely unlikely that you just happen to pick a number that shares factors with N. Now multiply eight by itself once, twice, three times four times, and so on, raising eight to ever higher powers and then divide each of these numbers by 77. We're not really interested in how many times 77 goes into the number, just the remainder, what's left over, because at some point, 77 should divide one of these numbers with a remainder of exactly one.
So eight divided by 77 is zero with a remainder of 8, 64 divided by 77 is zero remainder 64. 512 divided by 77 is six remainder 50. And as we keep going, we get remainders of 15, 43, 36, 57, 71, 29, and finally one. 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 8 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, 8 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 is actually the first remainder. So it must also appear when the cycle starts again.
Now we are ready to use a quantum computer to factor any large product of two primes. First we split up the qubits into two sets. The first set we prepare in a superposition of zero and one and two and three and four and five and six and seven and eight and nine, all the way up to 10 to the power of 1,234. Yeah, this is a huge superposition, but if we had perfect qubits, it would require only around 4,100.
The other set contains a similar number of qubits all left in the zero state for now. Now we make our guess G, which most likely doesn't share factors with N. We raise G to the power of the first set of qubits and then we divide by N and store the remainder in the second set of qubits leaving the first set of qubits as it was. Now we have a superposition of all the numbers we started with and the remainder of raising G to the power of those numbers divided by N. And through this operation, we have entangled our two sets of qubits, but we can't just measure this superposition. If we did, we would get a random value and learn nothing.
But there is a trick we can use. If we don't measure the entire superposition, but only the remainder part, we will obtain some random remainder. But this remainder won't occur just once. It will occur multiple times every time it comes up in the cycle. Imagine we were doing this with the example from before with N equals 77 and G equals eight. If the remainder we measured was say 15, then there would be multiple terms in our superposition.
Because there are multiple exponents you can raise G2 that give this same remainder, exponents 4, 14, 24, 34, and so on. They are each separated by 10, and that value is the exponent that satisfies our equation. So more generally 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.
This is the number we are looking for. Since the remainder is now the same for all states, we can put it to the side and we now have a superposition that is periodic. Each term is separated from its neighbors by an amount R.
If we now apply the quantum Fourier transform to this superposition of states and I'm simplifying a little here, we will be left with states containing one over R. So all that's left to do now is perform a measurement and find R by inverting it, and that's it for the quantum part. Now, 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.
And as long as these terms themselves are not a multiple of N, we can use Euclid's algorithm to find the factors of N and break the encryption. This would only take several thousand perfect qubits, but the qubits we have today are imperfect, so we need additional qubits to act as redundant information. In 2012, it was estimated that it would take a billion physical qubits to break RSA encryption, but by five years later that number had dropped to 230 million. And in 2019, after more technological breakthroughs, that estimate plummeted to just 20 million physical qubits. So how many qubits do we have today? Well, if we look at the state of IBM's quantum computers, we are nowhere near that number of qubits, but progress looks to be exponential.
So now it's just a question of when these two curves will collide before all our existing public key encryption can be broken. Because we've long known this threat is coming, scientists have been looking for new ways to encrypt data, which can withstand attacks from both normal and quantum computers. In 2016, the National Institute of Standards and Technology or NIST, launched a competition to find new encryption algorithms that aren't vulnerable to quantum computers. Cryptographers from all over the world submitted 82 different proposals, which were rigorously tested, some were broken. And then on July 5th, 2022, NIST selected four of the algorithms to be part of their post-quantum cryptographic standard. So how do they work? Well, three of the algorithms are based on the mathematics of latices.
So let's do a simple example in the 2D plane. Take two vectors, r1 and r2, by adding together different integer combinations of these vectors, say three times r1 and one times r2, you can get two different points and all the points you can get to by combining these two vectors in different ways is what is called a lattice. Now I will also give you the point C, and your task is to tell me which combination of r1 and r2 will bring me to the lattice point closest to c.
It's pretty easy to see that we can get there by going in the direction of r2 twice and in the negative direction of r1 twice. Simple enough. But those vectors, 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. And now if I ask you the same question again, can you tell me the combination of b1 and b2 that gets you to the lattice point closest to c? This has become a lot harder, but why is that? Each time we're taking a step, we're trying to get closer in either the X or Y direction, but with the b vectors, each time we take a step in the right direction with one vector, it puts us off in the other direction.
And that's why these vectors are a lot harder to work with. In the end, it takes us 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 squared. Add a third dimension and the number of points in the sphere is proportional to r cubed.
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 I want to send someone a message, I pick a point on their lattice, for example, say this point corresponds to the number seven. So if I wanna send the number seven, I can take that point but then add some random noise to it. So the message I send is not precisely at that point but close to it.
Now, to decode the message, my 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 my 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.
Behind the scenes, there's an army of researchers, mathematicians, and cryptographers, we're gonna make sure your secret data stays secret. These are some of the unsung heroes that will keep us safe moving forward, avoiding mass surveillance by governments keeping critical infrastructure protected and allowing you to live as if quantum computers were never invented in the first place. (digital buzzing) Something that fascinates me is being able to see where the world is headed. And right now it's clear that quantum computers and AI chatbots are going to play bigger and bigger roles in our lives in the coming decades. Even if we don't know exactly how they'll be implemented, I think it's important to learn how they work right now and you can do that with this video's sponsor, Brilliant. Brilliant has an incredible course on quantum algorithms.
This one was co-developed with Microsoft and Alphabet X. I love that you can simulate quantum gates and write and execute real quantum algorithms right in the lesson. No need to set up your own development environment. And if you want to dive deeper into cryptography, making and breaking codes is really a matter of statistics. Strong statistical reasoning skills help us find patterns in data and make sense of them, which is crucial to mastering just about any topic in math and computer Science. Brilliant's course on data analysis will help you ramp up fast.
It uses everyday situations, like business models to illustrate key concepts in statistics and it's interactive, so you can get hands on with data visualizations and develop a real intuition for interpreting them. You know the thing that sets Brilliant apart is they know how to break fundamentals down into their core building blocks, whether you're learning math, computer science or data analysis, Brilliant's thousands of bite-sized interactive lessons help you master key concepts and build to more advanced topics. You can try everything Brilliant has to offer for free for a full 30 days. Just go to brilliant.org/veritasium. I will put that link down in the description.
And for viewers of this video, Brilliant is offering 20% off their annual premium subscription to the first 200 people to sign up. So I wanna thank Brilliant for sponsoring this video, and I want to thank you for watching.
2023-03-21 23:43
