How Quantum Computers Break The Internet... Starting Now

- Right now, some nation states and individual actors are intercepting and storing a lot of encrypted data such as passwords, banking details, and social security numbers. But they can't open these files. So why do they do it? Well, because they believe that within the next 10 to 20 years they will have access to a

quantum

computer that will be able to

break

encryption in minutes. This procedure is known as Store Now, Decrypt Later or SNDL. And it works because there is information today that will still be valuable a decade from now. Things like industrial and pharmaceutical research and top-secret government intelligence, and everyone is aware of this threat.

The National Security Administration says that if a large enough

quantum

computer were built, it would be capable of undermining all widely deployed public-key algorithms. - You know, within five to ten years, quantum computing will

break

encryption as we know it today. - Although quantum

computers

are still years away from being powerful enough, they are already a threat due to Store Now Decrypt Later, which is why the US Congress just passed legislation requiring all agencies to start to transition right now to new methods of cryptography that cannot be broken by quantum

computers

. You know, our current encryption schemes have been remarkably successful and have worked effectively for over 40 years.

Until the 1970s, if you wanted to exchange private information with someone, you first had to meet in person and share a secret key. This same key would be used to encrypt and decrypt messages. That is why it is known as symmetric key algorithm. As long as no one else gets their hands on the key, your messages are safe. But what if you want to send information to someone you've never met and it's too difficult to arrange a meeting in person? You can't share a key over an unsecured channel like a phone line or email, because it could be intercepted.

And this is what in 1977 led three scientists, Riverst, Shamir and Adelman, to devise a breakthrough in encryption. Today it is known by its acronym RSA and it works more or less like this. Each person has two really large prime numbers, all of them their own and which they keep secret. They multiply these numbers to get an even larger number, which they make public for all to see. Now, if I want to send someone a private message, I use their large public number to distort my message. And I confuse it in such a way that it is impossible to decipher it without knowing the two prime factors that formed that number.

This is an asymmetric key system, as different keys are used to encrypt and decrypt the message. So it's easy for my 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, into the most well-known factorization algorithm, General Number Field Sieve, but modern cryptography uses prime numbers that are around 313 digits long. Factoring a product of two primes of this size, even with a supercomputer, would take about 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 zero or 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 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 thus we obtain the answer 49. Quantum computers are made up of qubits that also have two states, zero or one. But unlike a classical bit, a qubit doesn't have to be in only one state at a time.

It can be 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 are left with is a superposition of the different responses. 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 therefore perform eight calculations at once. Increase that number to just 20 qubits and you can already represent more than a million different states, meaning you can simultaneously calculate more than a million different answers.

With 300 qubits, more states can be represented than particles in the observable universe. This sounds incredibly powerful and it is, but there is a big problem. All answers to the calculation are included in a superposition of states, but you cannot simply read this superposition. When you make a measurement, you only get one value from the overlay basically at random, and all other information is lost. So to harness the power of a quantum computer, you need a clever 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 luckily, these are precisely the problems that form the basis of almost all of the public key cryptography we use today. In 1994, Peter Shor and Don Coppersmith discovered how to perform a quantum Fourier transform. It works like a normal Fourier transform, it is applied to some periodic signal and returns the frequencies that are in that signal. This may not seem particularly interesting, but consider it. If we have a superposition of states that is periodic, that is, the terms of the superposition are separated by a regular amount, well, we can apply the quantum Fourier transform and we will be left with states that contain the frequency of the signal.

So we can measure this. The quantum Fourier transform allows us to extract frequency information from a periodic superposition, and that will be useful. So how does a quantum computer factor the product of two prime numbers much faster than a conventional computer? I want to explain this by first going over a simple example without the need for a quantum computer, and then I will show how a quantum computer could execute this method for even 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 this example, let's set N equal to 77. Now I bet you can guess the prime factors, but let's assume for the moment that we don't know them, because with a product of really big primes, we wouldn't know. t. Now I want to use a fact about numbers that seems magical. Choose a number g that doesn't share any factors with N. If you multiply g by itself over and over again, you will eventually always 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. Choose any number less than 77. I will choose the number eight. This number shares no factors with 77. And if you were doing this with large primes, you would also be extremely unlikely to choose a number that shares factors with N. Now multiply eight by itself once, twice, three times. multiplied by four, and so on, raising eight to higher and higher powers and then we divide each of these numbers by 77. We are not really interested in how many times 77 fits in the number, just the rest, what is 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 continue, we get remainders of 15, 43, 36, 57, 71. , 29, and finally one. There we have it, eight to the power of 10 is one more than a multiple of 77. So we have found the exponent R that satisfies this equation. But how does this help in finding the factors of N? Well, we rearrange the equation to bring one to the left side and then we can split it into two terms like this. And now, whenever r is even, we have an integer multiplied by another integer equals a multiple of N.

This looks remarkably like p multiplied by q equals N. I mean, since we know that p and q are on the side right of this equation, they should also be on the left side simply multiplied by some additional factors. So one way to think about what we've done is that we've made a bad guess for one of the factors G and, by finding the exponent r, we've converted it into two much better guesses that probably share factors with N. Since r was 10, the two terms on the left 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 want to find the greatest common factor of two numbers, say 32,769 and 77, divide the larger number by the smaller number and record the remainder. In this case, 32,769 divided by 77 gives a remainder of 44. Then shift the numbers one position to the left and repeat. Now we divide 77 by 44 and obtain a remainder of 33. We 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 is 11, which is actually a factor of 77 and 32,769. You could do the same procedure with the other number or simply divide 77 by 11 to get seven, its other prime factor. So to summarize, if you want to 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 get to one more than a multiple. of N. Third, use that exponent to calculate two new numbers that likely 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 perform any of these steps, but on a classical computer, this method would not be faster than other methods. The key process that speeds up a quantum computer is step two, finding the exponent that you raise G2 to be equal to 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. Notice what happens to the remainders if we continue going from eight to the power of 10, from 8 to the power of 11, from eight to the power of 12, and so on.

Well, we get remainders of 8, 64, 50, 15, 43, 36, 57, 71, 29 and again one. The remains circulate and will continue to cycle. Notice how the exponent that returns a remainder of one is 20, which is 10 more than the first exponent that returns a remainder of one. So we know that eight to the power of 30 and eight to the power of 40, 8 to any power divisible by 10 will also be one more than a multiple of 77. It's also worth noting that if you choose any remainder, say 15, the next time we If you find the same remainder, the exponent will have increased by 10. Then 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 am plotting the remainders on a logarithmic scale so you can see that they are periodic with a period of 10. If I had made a different assumption, say I had chosen G equal to 15 instead of eight, then the period would be different and the remainders They would be different but there would always be a remainder of one. Why is this? Well, now that you can see that 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's actually the first remainder.

So it should also appear when the cycle starts again. We are now ready to use a quantum computer to factorize any large product of two primes. We first divide the qubits into two sets. We prepared the first set in a superposition of zero and one and two and three and four and five and six and seven and eight and nine, up to 10 to the power of 1234. Yes, this is a huge superposition, but if we had perfect qubits, we would only we would require around 4,100. The other set contains a similar number of qubits, all left in the zero state for now.

Now we make our assumption G, which probably shares no factors with N. We raise G to the power of the first set of qubits and then 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 simply measure this. overlap. If we did, we would get a random value and learn nothing.

But there is a trick we can use. If we do not measure the entire overlap, but only the remaining part,we will get some random remainder. But this rest will not happen just once. It will occur multiple times each time it appears in the loop. Imagine we were doing this with the example above where N equals 77 and G equals eight. If the remainder we measured were, say, 15, then there would be multiple terms in our superposition. Because there are multiple exponents, you can raise G2 that gives the same remainder, exponents 4, 14, 24, 34, etc. Each of them is 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 share the same remainder and all exponents will be separated by the same amount r. This is the number we are looking for. Since the rest is now the same for all states, we can set it aside and now we have a periodic overlap. Each term is separated from its neighbors by a quantity R. If we now apply the quantum Fourier transform to this superposition of states and I'm simplifying a bit here, we will be left with states containing one over R.

So all that's left to do is What we do now is make a measurement and find R by inverting it, and that's it for the quantum part. Now, whenever r turns out to be even, we can use r to convert our bad guess g into two numbers that probably share factors with N. And as long as these terms themselves are not multiples of N, we can use Euclid's algorithm. to find the factors of N and break the encryption. This would only require 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 one billion physical qubits would be needed to break RSA encryption, but five years later that figure had dropped to 230 million. And in 2019, after more technological advances, 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 many qubits, but the progress seems to be exponential. So now it's just a question of when these two curves will collide before all of our existing public key encryption can be broken. As we have long known that this threat is looming, 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 are not vulnerable to quantum computers. Cryptographers from around the world submitted 82 different proposals, which were rigorously tested and some did not work. And then, on July 5, 2022, NIST selected four of the algorithms to be part of its post-quantum cryptographic standard. So how do they work? Well, three of the algorithms are based on latex mathematics. So, let's do a simple example on the 2D plane. Take two vectors, r1 and r2, by adding 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 are what you called lattice.

Now I will also give you point C, and your task is to tell me what combination of r1 and r2 will take me to the lattice point closest to c. It's pretty easy to see that we can get there by going twice in the direction of r2 and twice in the negative direction of r1. Simple enough. But those vectors, r1 and r2, are not the only vectors that can give you this network. Take b1 and b2 as an example. These vectors also form the same network. And now, if I ask you the same question again, can you tell me the combination of b1 and b2 that takes you to the point on the lattice closest to c?

This has become much more difficult, but why? Every time we take a step, we try to get closer in the another address. And that's why it's much harder to work with these vectors. In the end, it takes us a combination of eight times b1 and minus six times b2 to reach the nearest network point. This is much more difficult than before, but it is still a relatively easy problem to solve. But if we expand it to three dimensions, this becomes much more difficult, especially since you don't have the collection of all the points in the network.

They only give you the vectors that make it up. So when you find a network point near the target, you still need to find all the other network points nearby to make sure yours is 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 on the sphere is proportional to r cubed. So just notice how the number of points in the network grows as we increase the number of dimensions. Solving the nearest vector problem is a piece of cake for your three-dimensional computer.

Even a hundred dimensions should be manageable. But in the proposed future encryption schemes, we will use about a thousand dimensions. Take a step in the right direction in 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 so many dimensions, it is extremely difficult to find the closest point even for the most powerful computers 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 describe a network, but he keeps them secret and only shares his network publicly using a set of vectors that are difficult to work with.

Now, if I want to send a message to someone, I choose a point on their network, for example, I say that this point corresponds to the number seven. So if I want to 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 determine which point on the network is closest to the message point. In thousand dimensions, this will be extremely difficult to do unless you have the good set of vectors, which is what my recipient has.

So it's easy for the recipient, who has the good vectors, but difficult 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 is an army of researchers, mathematicians and cryptographers, we will make sure your secret data stays secret. These are some of the unsung heroes who will keep us safe in the future, preventing mass surveillance by governments, keeping critical infrastructure protected, and allowing us to live as if quantum computers were never invented. (digital buzz) Something that fascinates me is being able to see where the world is going.

And right now it's clear that quantum computers and AI chatbots will play increasingly important roles in our lives in the coming decades. Even if we don't know exactly how they will be implemented, I think it's important to learn how they work now and you can do so with the sponsor of this video, Brilliant. Brilliant has an amazing course on quantum algorithms. This was co-developed with Microsoft and Alphabet X. I love that you can simulate quantum gates and write and run real quantum algorithms right in the lesson. You don't need to set up your own development environment.

And if you want to delve deeper into cryptography, creating and cracking 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 for mastering almost any math and computer science topic. Brilliant's course on data analytics will help you advance quickly. It uses everyday situations, such as business models, to illustrate key concepts in statistics and is interactive, so you can get hands-on with data visualizations and develop real intuition for interpreting them. You know what sets Brilliant apart is that they know how to break down fundamentals into their building blocks, whether you're learning math, computer science, or data analytics, 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 shiny.org/veritasium. I'll put that link in the description. And for viewers of this video, Brilliant is offering a 20% discount on its annual premium subscription to the first 200 people who sign up. So I want to thank Brilliant for sponsoring this video and I want to thank you for watching it.