How Quantum Computers Break The Internet... Starting Now

Summary

The video discusses the threat of quantum computing to current encryption methods, explaining the concept of 'Store Now, Decrypt Later' and the potential for quantum computers to break encryption in the future. It covers the history of encryption, the RSA algorithm, and the quantum computing process. The video also introduces new post-quantum cryptographic standards being developed to counteract these threats.

Takeaways

• 🔒 The current practice of 'Store Now, Decrypt Later' (SNLD) involves collecting encrypted data with the expectation that future quantum computers will be able to decrypt it.
• 💡 Quantum computers have the potential to undermine public key algorithms due to their superior processing capabilities, which could break encryption within minutes.
• 📈 The US Congress has mandated the transition to new cryptographic methods that are quantum-resistant in response to the threat posed by quantum computing.
• 🔑 Traditional encryption methods, like RSA, rely on the difficulty of factoring large numbers, a task that quantum computers could potentially perform much faster.
• 🤔 Quantum computers utilize qubits, which can exist in multiple states simultaneously, allowing for the computation of many possibilities at once.
• 🌌 The power of quantum computers comes with a limitation: when measuring a superposition of states, only one outcome is obtained, and the rest of the information is lost.
• 🔍 Peter Shor's algorithm, using quantum Fourier transform, can efficiently find the period in a sequence, which is a key step in factoring large numbers on a quantum computer.
• 🔄 The process of factoring large numbers using a quantum computer involves creating a periodic superposition of states, finding the period, and then using classical algorithms to find the factors.
• 🛡️ Scientists are actively developing new encryption methods that are secure against both classical and quantum computing attacks, with NIST selecting four such algorithms in 2022.
• 📊 Post-quantum cryptography based on lattice mathematics offers a promising direction for secure encryption, as solving the closest vector problem in high dimensions is computationally hard.
• 🚀 The race is on between the development of quantum computers and the creation of quantum-resistant encryption, with the latter aiming to stay ahead to ensure data security.

Q & A

What is the concept of 'Store Now, Decrypt Later' (SNDL)?

SNDL refers to the strategy where encrypted data such as passwords, bank details, and social security numbers are intercepted and stored with the expectation that future quantum computers will be able to decrypt them within the next 10 to 20 years.

Why is the National Security Administration concerned about quantum computers?

The National Security Administration is concerned because a sufficiently large quantum computer, if built, would be capable of undermining all widely deployed public key algorithms, thus breaking the encryption that currently secures sensitive information.

What is the significance of the RSA encryption method?

RSA is an asymmetric key encryption system that uses two different keys for encryption and decryption. It is significant because it allows secure communication without the need to share a secret key in person, and it has been effective for over 40 years.

How do quantum computers differ from classical computers in terms of bits and qubits?

Classical computers use bits that can be in a state of either zero or one at any given time. Quantum computers, on the other hand, use qubits that can exist in a superposition of states, allowing them to be in both zero and one states simultaneously, which gives quantum computers their parallel processing capabilities.

What is the main challenge in harnessing the power of quantum computers?

The main challenge is that while quantum computers can perform many calculations simultaneously, extracting useful information from the superposition of states is difficult because measurement collapses the superposition to a single outcome, losing all other information.

What is the quantum Fourier transform and how is it used in quantum computing?

The quantum Fourier transform is a quantum equivalent of the classical Fourier transform that can extract frequency information from a periodic superposition of states. It is used in quantum algorithms to find patterns or cycles in the data, which is particularly useful in factoring large numbers, a task that can break certain encryption schemes.

How does the process of factoring large numbers using a quantum computer differ from classical methods?

Quantum computers can use the quantum Fourier transform to find the period of a repeating pattern in the remainders when a number is raised to successive powers and divided by the number to be factored. This period is then used to find factors of the number, a process that is much faster than classical factoring algorithms.

What is the current state of quantum computers in terms of the number of qubits?

As of the script's knowledge cutoff in 2023, quantum computers have not yet reached the number of qubits required to break RSA encryption. However, the progress in quantum computing is exponential, and estimates for the number of qubits needed for such a task have been decreasing.

What is the significance of the National Institute of Standards and Technology (NIST) selecting new encryption algorithms?

The selection of new encryption algorithms by NIST is significant because it represents a proactive step towards securing data against potential future threats from quantum computers. These algorithms are designed to be resistant to both classical and quantum computational attacks.

Can you explain the concept of lattices in the context of post-quantum cryptography?

In post-quantum cryptography, lattices are complex mathematical structures used as the basis for encryption algorithms. The security of these algorithms is based on the difficulty of finding the shortest vector in a high-dimensional lattice, a problem that is believed to be hard for both classical and quantum computers.

What is the role of Brilliant in the context of this script?

Brilliant is mentioned in the script as an educational platform offering courses on quantum algorithms and data analysis. These courses aim to help learners understand the fundamentals and applications of quantum computing and cryptography, as well as develop statistical reasoning skills.

Outlines

00:00

🔒 Quantum Threat to Encryption

The script discusses the current threat posed by quantum computing to encryption methods. Nations and individuals are storing encrypted data, anticipating future quantum computers will decrypt it easily. This strategy is known as Store Now, Decrypt Later (SNDL). The National Security Administration warns that a sufficiently large quantum computer could undermine public key algorithms. The US Congress has mandated a transition to quantum-resistant cryptography. The script also explains the historical shift from symmetric key algorithms, where a single key is used for encryption and decryption, to the RSA asymmetric key system, which uses different keys for each process. The RSA system relies on the difficulty of factoring large prime numbers, a task made feasible by quantum computing.

05:01

🧠 Quantum Computing's Potential and Limitations

This paragraph delves into the power and limitations of quantum computing. Quantum computers use qubits, which unlike classical bits, can exist in multiple states simultaneously (superposition). This allows quantum computers to perform many calculations at once. However, extracting useful information from these computations is challenging because measuring a superposition only yields a single value at random, losing all other information. Quantum computers can potentially solve certain problems, like factoring large numbers, much faster than classical computers. Peter Shor and Don Coppersmith's quantum Fourier transform is highlighted as a key technique for extracting frequency information from periodic superpositions, which is crucial for breaking cryptographic codes.

10:04

🔍 Factoring Primes with Quantum Computers

The script explains how quantum computers can factor large numbers more efficiently than classical computers. It uses the example of factoring 77 to illustrate the process. The method involves picking a number 'g' that doesn't share factors with the number 'N', and repeatedly squaring 'g' until a multiple of 'N' plus one is reached. This reveals an exponent 'r' that can be used to generate two new numbers likely to share factors with 'N'. Euclid's algorithm is then used to find these shared factors. Quantum computers speed up the process of finding 'r' by exploiting the periodic nature of remainders in a superposition of states, making it feasible to factor large numbers in a short time.

15:05

🌐 The Race for Quantum-Resistant Encryption

The script discusses the ongoing efforts to develop encryption methods that can withstand quantum attacks. It mentions that scientists have been searching for new encryption techniques since the threat of quantum decryption is imminent. The National Institute of Standards and Technology (NIST) launched a competition in 2016 to find such algorithms. By July 5th, 2022, NIST selected four algorithms for their post-quantum cryptographic standard. Three of these are based on lattice-based mathematics, which involves complex problems in high dimensions that are believed to be difficult for both classical and quantum computers to solve, making them promising candidates for secure encryption.

20:06

🌐 Lattice-Based Cryptography and the Future of Data Security

This paragraph explores lattice-based cryptography, a potential solution for quantum-resistant encryption. It explains the concept of lattices in high-dimensional space and the difficulty of solving the closest vector problem in such spaces. The method involves each person having a secret set of vectors that describe a lattice, which they only share publicly in a form that is hard to work with. To send a message, a sender picks a point on the recipient's lattice and adds random noise. The recipient, who has the good vectors, can then decode the message by finding the closest lattice point to the noisy message. This method is considered secure against both classical and quantum computers, ensuring data remains confidential.

🚀 The Role of Quantum Computing and AI in the Future

The final paragraph shifts focus to the broader implications of quantum computing and AI in the future. It emphasizes the importance of understanding these technologies now, even if their full applications are not yet clear. The script promotes a course on quantum algorithms offered by Brilliant, which is co-developed with Microsoft and Alphabet X. The course allows learners to simulate quantum gates and execute real quantum algorithms. Additionally, the script highlights the importance of strong statistical reasoning skills in mastering various topics in math and computer science, and Brilliant's course on data analysis is recommended for developing these skills. The script concludes by thanking Brilliant for sponsoring the video and offering a discount to viewers.

Keywords

💡Quantum Computing

Quantum computing is a type of computation that uses quantum-mechanical phenomena such as superposition and entanglement to perform operations on data. Unlike classical computers, which use bits as the smallest unit of information, quantum computers use qubits, which can exist in multiple states simultaneously, allowing them to perform complex calculations much faster. In the script, quantum computing is discussed as a potential future threat to current encryption methods due to its ability to solve problems much faster than classical computers.

💡Store Now, Decrypt Later (SNDL)

Store Now, Decrypt Later (SNDL) is a strategy used by entities who intercept and store encrypted data with the expectation that it will be possible to decrypt it in the future using advanced technology, such as quantum computers. This approach is based on the belief that quantum computing will be capable of breaking current encryption algorithms, which makes intercepted data valuable even if it cannot be accessed immediately. The script highlights the urgency of developing new encryption methods that are resistant to future quantum attacks.

💡Public Key Cryptography

Public key cryptography is a cryptographic system that uses pairs of keys: public keys, which may be disseminated widely, and private keys, which are known only to the owner. This allows secure communication over an insecure channel without needing to exchange a secret key in advance. The script discusses how quantum computers could potentially break widely used public key algorithms like RSA, which currently form the backbone of secure internet communications.

💡RSA Encryption

RSA encryption is a public key encryption technology that uses the difficulty of factoring large prime numbers to secure data. It was developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. The script explains how RSA works and why it is vulnerable to quantum computing, as quantum algorithms can factorize large numbers exponentially faster than classical algorithms, potentially rendering RSA insecure in the future.

💡Qubit

A qubit, or quantum bit, is the basic unit of quantum information. Unlike a classical bit, which can be either 0 or 1, a qubit can exist in a superposition of states, meaning it can be both 0 and 1 simultaneously. This allows quantum computers to perform many calculations at once, significantly increasing their computational power. The script uses qubits to illustrate how quantum computers can process vast amounts of information in parallel, posing a threat to traditional encryption methods.

💡Quantum Fourier Transform

The quantum Fourier transform is a linear transformation on quantum bits and is the quantum analog of the discrete Fourier transform. It is a crucial component of many quantum algorithms, including Shor's algorithm for factoring large integers, which is significant for breaking encryption. The script explains how the quantum Fourier transform can be used to solve periodic problems that are difficult for classical computers, thereby enabling quantum computers to break encryption like RSA.

💡Lattice-based Cryptography

Lattice-based cryptography is a type of post-quantum cryptography that relies on the hardness of lattice problems, which remain difficult even for quantum computers. In the script, lattice-based cryptography is presented as a promising solution to creating encryption algorithms that are secure against quantum attacks. The script explains how lattices work in multiple dimensions and why they are challenging for computers to solve, offering an example of how this approach could protect data in a post-quantum world.

💡Euclid’s Algorithm

Euclid's algorithm is a method for computing the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers also divides their difference. In the context of the script, Euclid’s algorithm is used to find common factors between numbers, which is a step in the process of factoring large numbers, a problem that is at the core of RSA encryption and its vulnerability to quantum computing.

💡Superposition

Superposition is a fundamental principle of quantum mechanics, where a quantum system can exist in multiple states simultaneously until it is measured. This principle allows quantum computers to perform multiple calculations at once, dramatically increasing their processing power compared to classical computers. The script describes how superposition enables quantum computers to evaluate many possible solutions to a problem simultaneously, a key factor in their ability to break complex encryption algorithms.

💡Post-Quantum Cryptography

Post-quantum cryptography refers to cryptographic algorithms that are designed to be secure against the potential threats posed by quantum computers. These algorithms are intended to replace current systems that could be vulnerable to quantum attacks. The script highlights the importance of transitioning to post-quantum cryptographic methods to ensure the security of data as quantum computing technology advances.

Highlights

Nation states and individual actors are intercepting and storing encrypted data like passwords and bank details, anticipating future quantum computers that can break encryption.

The concept of 'Store Now, Decrypt Later' (SNDL) is based on the belief that quantum computers will be able to decrypt currently secure data in the future.

The National Security Administration warns that a sufficiently large quantum computer could undermine all widely deployed public key algorithms.

US Congress has passed legislation mandating the transition to new cryptography methods that quantum computers cannot break.

Current encryption schemes like RSA rely on the difficulty of factoring large prime numbers, a task that quantum computers could potentially perform quickly.

Quantum computers use qubits, which unlike classical bits, can exist in a superposition of states, allowing simultaneous computation of multiple possibilities.

Peter Shor and Don Coppersmith's quantum Fourier transform allows quantum computers to extract frequency information from a periodic superposition, crucial for factoring large numbers.

Quantum computers can factor the product of two primes much faster than conventional computers by exploiting the periodicity in the remainders of powers of a number modulo N.

The process of factoring large numbers on a quantum computer involves creating a superposition of states, measuring the remainder, and applying the quantum Fourier transform.

The quantum part of factoring involves finding the exponent that satisfies a specific equation related to the remainders of powers of a number modulo N.

The number of qubits required to break RSA encryption has been estimated to decrease from a billion to 20 million due to technological advancements.

Scientists are developing new encryption methods that can withstand attacks from both classical and quantum computers, with NIST selecting four post-quantum cryptographic standards in 2022.

Three of the selected post-quantum algorithms are based on lattice-based cryptography, which involves solving complex problems in high-dimensional spaces.

Lattice-based encryption schemes use a set of vectors to describe a lattice, with the secret vectors used to encode and decode messages.

The security of lattice-based cryptography relies on the difficulty of finding the closest lattice point to a given target, a problem that becomes exponentially harder as the number of dimensions increases.

Researchers, mathematicians, and cryptographers are working to ensure the security of data in the face of quantum computing advancements.

Brilliant offers courses on quantum algorithms and data analysis, helping learners understand and master the fundamentals of these fields.

Transcripts

- 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.