How Quantum Computers Break The Internet... Starting Now
Summary
TLDRThe 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
🔒 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.
🧠 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.
🔍 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.
🌐 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.
🌐 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.
Mindmap
Keywords
💡Quantum Computing
💡Store Now, Decrypt Later (SNDL)
💡Public Key Cryptography
💡RSA Encryption
💡Qubit
💡Quantum Fourier Transform
💡Lattice-based Cryptography
💡Euclid’s Algorithm
💡Superposition
💡Post-Quantum Cryptography
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.
Voir Plus de Vidéos Connexes
世上無人能破解!量子力學為何是最強之盾?量子糾纏不只安全,還能讓你上網超光速!?|量子熊 ✕ 泛科學 EP11
Redes - El ordenador del futuro - Ordenadores cuánticos
10 Mind-Blowing Facts About Quantum AI
Quantum Computing Will Be Bigger Than AI! What You Need To Know!
The Race to Harness Quantum Computing's Mind-Bending Power | The Future With Hannah Fry
Quantum Computing In 5 Minutes | Quantum Computing Explained | Quantum Computer | Simplilearn
5.0 / 5 (0 votes)