Quantum computing is a rapidly advancing field that has the potential to revolutionize computing as we know it. While traditional computers rely on bits, quantum computers use qubits, which can exist in multiple states simultaneously. This makes quantum computers much faster and more powerful than traditional computers, but it also means that they have the potential to break some of the security protocols that underpin the internet.
The internet is built on a foundation of encryption, which keeps our data safe as it travels across the web. Encryption works by encoding information so that it can only be read by someone who has the key to decrypt it. As the internet has grown and become more complex, encryption has become increasingly important. But some encryption algorithms are vulnerable to quantum computing.
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.
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.
For 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.
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.
Post-Quantum Cryptographic Standard
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.
One of the most widely used encryption algorithms is the RSA algorithm. This algorithm works by taking two large prime numbers and multiplying them together to create a public key. The private key, which is used to decrypt the data, is the product of two other prime numbers. Breaking RSA encryption requires factoring the public key, which is difficult for traditional computers. But quantum computers can solve this problem much more easily using a technique called Shor’s algorithm.
Shor’s algorithm works by using the quantum properties of qubits to find the factors of a number much faster than a classical computer can. This means that a quantum computer could potentially break RSA encryption in a matter of seconds, rendering much of the internet’s security protocols useless.
This is a serious problem because so much of our personal and financial information is transmitted over the internet. If someone were to break the encryption on a major financial institution’s website, for example, they could potentially access millions of people’s financial information.
So what can we do to protect ourselves from quantum computing attacks on the internet? There are a few different solutions that are being explored.
One approach is to simply upgrade our encryption algorithms. There are already quantum-resistant encryption algorithms that have been developed, such as the McEliece cryptosystem and the NTRU encryption scheme. These algorithms are resistant to quantum computing attacks because they rely on mathematical problems that are believed to be difficult for quantum computers to solve.
Another approach is to develop quantum-resistant versions of existing encryption algorithms. This involves modifying the algorithms so that they are resistant to attacks by quantum computers. This is a more difficult task than simply developing new encryption algorithms from scratch, but it has the advantage of being able to leverage the existing infrastructure that is already in place.
A third approach is to use quantum encryption. Quantum encryption works by using the properties of quantum mechanics to transmit information in a way that is intrinsically secure. Because of the way that quantum mechanics works, it is impossible to intercept a quantum communication without disrupting the information being transmitted. This means that quantum encryption could potentially provide a way to transmit information over the internet that is completely secure, even against quantum computing attacks.
The problem with quantum encryption is that it is difficult and expensive to implement. It requires specialized hardware and is currently only practical for use in very specific situations, such as secure communication between government agencies. However, as the technology advances and becomes more affordable, it could become a more widespread solution to the problem of quantum computing attacks on the internet.
In conclusion, quantum computing has the potential to break the internet’s security protocols, which could have serious implications for our personal and financial information. But there are solutions that are being explored, including upgrading our encryption algorithms, developing quantum-resistant versions of existing encryption algorithms, and using quantum encryption. While these solutions are not perfect, they do offer a way to protect ourselves from the potential threat of quantum computing attacks on the internet. As quantum computing continues to advance, it will be important for us to stay vigilant and continue to explore new ways to keep our data safe.
