Kind: captions
Language: en
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 in a five to ten year time
frame 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
U.S 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 want to 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 unsecure Channel like a phone
line or the mail because it could be
intercepted and this is what in 1977 LED
three scientists Reves 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 want to 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
zero zero zero one one zero or one one
let's say each of these states
represents a number zero one two or
three if we want to do a calculation for
example raising 7 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 zero one two and three
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
superposition 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 Shore and Don koppersmith
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 where we can apply the
quantum Fourier transform and we'll 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 going to 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 8 by itself once twice
three times four times and so on raising
8 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 8 divided by 77 is 0 with a remainder
of 8. 64 divided by 77 is 0 remainder
64. 512 divided by 77 is 6 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 8 to the power of
ten 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 8 to the power of 5 plus 1
32 769 and 8 to the power of five minus
one thirty two thousand seven hundred
sixty seven these two numbers probably
share factors with n
so how do we find them we use Euclid's
algorithm
if you want to find the greatest common
divisor of two numbers say 32 769 and 77
divide the bigger number by the smaller
one and record the remainder in this
case thirty two thousand seven hundred
sixty nine 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 0.
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 want to find the
prime factors p and Q of a number n
first make a bad guess g
second find out how many times R you
have to multiply G by itself to reach
one more than a multiple of n
third use that exponent to calculate two
new numbers that probably do share
factors Within
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 a to the power of 10 is one more
than a multiple of 77.
watch what happens to the remainders if
we keep going past 8 to the power of 10
to 8 to the 11 8 to the 12 and so on
well we get remainders of 8 64 50 15 43
36 57 71 29 and again one
the remainder's cycle and they will just
keep cycling notice how the exponent
that yields a remainder of 1 is 20 which
is 10 more than the first exponent that
yielded a remainder of 1. so we know
that 8 to the 30 and 8 to the 48 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 8 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 then all the way
up to ten to the power of one thousand
two hundred and thirty four yeah this is
a huge superposition but if we had
perfect qubits it would require only
around four thousand one hundred
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 8. 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 I'm simplifying
a little here we will be left with
States containing 1 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 Park
now as long as R turns out to be even we
can use R to turn our bad guest 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 lattices 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
1 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 8 times B1 and negative 6
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 a 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
want to send the number seven I can take
that point but then add some random
noise to it so the message I send is not
precisely at that point but close to it
now to decode the message my recipient
must 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 is an army of
researchers mathematicians and
cryptographers we're going to 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
foreign
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 chat Bots 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 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 Brilliance course
on data analysis will help you ramp up
fast it uses everyday situations like
business models to illustrate key
concept 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 Brilliance 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 want to thank
brilliant for sponsoring this video and
I want to thank you for watching