[ar:Andreas Baumhof]
[al:DEF CON 27 Hacking Conference]
[ti:Are Quantum Computers Really A Threat To Cryptography?]
[au:Andreas Baumhof]
[by:DEF CON Communications (https://www.defcon.org/]
[00:00:00.10]
>>How many people know about uh
quantum physics? Eh, yeah? So I
was looking at this uh I was
[00:00:05.17]
looking at this this this talk
synopsis and IÕm like maybe this
is gonna be a good talk. >>Maybe
[00:00:11.53]
Not >>Maybe it wonÕt. [laughter]
I guess I wonÕt really know
until I take a look at the talk,
[00:00:16.53]
[00:00:19.43]
yeah? Learned that from a baby
book. Yeah. Awesome Alright so
letÕs all give Andreas a big
[00:00:24.43]
[00:00:26.50]
round of applause for coming all
the way to Vegas from Sydney
Australia to talk to us about
[00:00:31.10]
quantum cryptography. [applause]
Have a good time man. >>Thank
you very much. Alright. Welcome
[00:00:37.97]
everybody. Yeah after that
introduction hopefully you walk
away and learn something in this
[00:00:44.47]
talk. So, um quantum computing
if you read whatevers in the
press you either think we are
[00:00:50.60]
completely doomed and you know,
the internets gonna end. Or uh
nothings gonna end because they
[00:00:55.03]
will never exist so I thought I
would explore this topic a
little more from an algorithmic
[00:00:59.07]
point of view and really see
where we are. Not so much on the
hype but more really what are
[00:01:03.20]
the algorithms uh that we talk
about right now. So um I started
various companies in the
[00:01:09.43]
securities space you know
starting in 2002 which um makes
me feel slightly old um right
[00:01:15.17]
now, but first I am speaking at
Defcon I am very happy about
this yÕknow long term attendee
[00:01:19.57]
but never spoke here so letÕs
get right into this. So when you
talk about cryptography we
[00:01:25.17]
mainly yÕknow look into two
different um types of
cryptography. One is a symmetric
[00:01:30.37]
cryptosystem which is a
symmetric shared key yÕknow kind
of AES for example. Both sides
[00:01:37.30]
encrypt and talk to each other
with the same key and with
asymmetric uh cryptosystems
[00:01:42.70]
which use public key
infrastructure you would
basically use a public key to
[00:01:46.93]
encrypt the message and a
private key to um decrypt it. Um
thereÕs various forms of this uh
[00:01:52.00]
obviously for the digital
signatures as well. And um in in
this realm um virtually every
[00:01:57.00]
[00:01:59.13]
cryptosystem right now that is
deployed anywhere is what we
call computationally secure.
[00:02:04.30]
They are secure in the sense
that there are known algorithms
that can break them but all the
[00:02:10.43]
algorithms that can break them
are not easy to in the sense
that yÕknow that if I wanna
[00:02:16.73]
break in a yÕknow 2048-bit RSA
key with a normal computer takes
me a couple trillion years which
[00:02:21.73]
[00:02:24.10]
means I am secure even though
thereÕs known algorithms that
can break them. There are
[00:02:30.40]
information-theoretic algorithms
out there most notably an
algorithm called um a
[00:02:35.70]
one-time-pad or vernam ciphers
but they're really tricky and
not really practically usable
[00:02:40.67]
for example a one-time-pad you
do need to use the same amount
of keys as you want to transmit
[00:02:46.20]
so for example if you want to
transmit a one megabyte file you
need to have a one megabyte key
[00:02:49.90]
basically for every byte you
need a different um uh for every
byte data you need uh one byte
[00:02:55.10]
key so you would have to manage
massive amount of uh key
material which is not really uh
[00:03:00.03]
practically but I mean they do
exist but outside of this
virtually every uh cryptosystem
[00:03:05.07]
is just computationally secure.
And um uh when you look at this
uh quantum algorithm and IÕll go
[00:03:11.57]
into quite some detail about
this for those two different
types of algorithms. It is much
[00:03:17.27]
more interesting to look at the
asymmetric part of the uh of the
cryptosystems because in the
[00:03:22.23]
symmetric part there is a
quantum algorithms as well
called uh Grover which basically
[00:03:28.00]
looks into um a provided
quadratic speed up to the
classical um uh version.
[00:03:33.00]
[00:03:35.13]
Basically in the classical
version if I want to look for
the shared key I need to
[00:03:38.27]
basically brute force every
combination which obviously
takes forever. I get a squared
[00:03:43.10]
root up um a squared speed up in
the quantum version which is a
fantastic speed up yÕknow if I
[00:03:48.63]
can speed up a hundred fifty
trillion years but it is
obviously a hundred fifty
[00:03:52.83]
trillion years uh to break so
thatÕs not really that
interesting. So we want to focus
[00:03:57.57]
here on the asymmetric part
where um uh the speed ups that
quantum computers can provide
[00:04:02.87]
are massive and um weÕre going
to go into quite some detail uh
why uh their speed up is so big
[00:04:08.97]
as it is and uh how they work.
So letÕs revisit just a little
bit of how RSA encryption works
[00:04:15.77]
and it's really just a basic
introduction so we can use them
uh to understand how the quantum
[00:04:21.20]
versions of these algorithms
works. Basically, I choose two
prime numbers p and q and um uh
[00:04:26.20]
[00:04:28.20]
with those I just multiply them
get the number n. Now with the
number n I can calculate this
[00:04:33.90]
lambda function which is a
carmichael function which just a
function I can easily calculate
[00:04:39.00]
this and once I have this I just
chose another parameter e which
is smaller than the lambda and
[00:04:44.80]
the value. And then this n
together with the number e is my
public key. I can give this to
[00:04:51.53]
everybody out there who I wanna
choose to do um uh the
asymmetric encryption. And I
[00:04:57.23]
basically retain my private key
which is this uh um number d
here which is just the modular
[00:05:03.97]
inverse of the number e which is
the uh public key. Obviously mod
lambda n. There is always mod
[00:05:08.97]
[00:05:13.40]
lambda n in this uh scenario
which is a private key that I
retain. And with this private
[00:05:19.30]
key now with this scenario. I
can now look into hey I can now
encrypt something and send
[00:05:23.90]
something um from Alice to Bob
and as everybody knows with
asymmetric encryption I can only
[00:05:30.87]
encrypt something that is
smaller than my key so if I have
a two four, um 2048 width key I
[00:05:35.87]
[00:05:37.97]
can only encrypt something that
is smaller than uh 2048 um so I
need to pad my plain text into
[00:05:44.77]
um a number n so I turn this big
M into small number m um uh
there is various way for this
[00:05:51.73]
ways for this. Um I donÕt go
into too much detail but this is
where the padding scheme uh
[00:05:55.43]
comes in and then I basically
end up with this number uh small
m. In my ciphertext my encrypted
[00:06:01.70]
versionÕs really I just take uh
this number m to the power of e.
Mod n and thats basically my
[00:06:08.47]
ciphertext. And this is what I
encrypt with a public key. I can
now send this number c to uh to
[00:06:13.47]
[00:06:15.90]
Bob. Uh um receive this and um
if you have the private key you
can easily decrypt this as well
[00:06:20.90]
[00:06:23.03]
on the other side. And uh you
can easily see how this works.
It is really very
[00:06:28.60]
straightforward if someone has
the c and the ciphertext and the
d the private key by definition
[00:06:33.90]
c is m to the power of e. So you
see um uh the definition of d
was it is actually the inverse
[00:06:40.30]
of e so this e to the power of d
just uh equals out. So I end up
with m mod n so uh if I have the
[00:06:45.30]
[00:06:47.60]
private key, I can easily
recover um uh the uh the small m
and obviously by just reversing
[00:06:53.57]
the padding scheme I now have my
message again. So this basically
how RSA encryption works into
[00:06:58.57]
[00:07:00.60]
some detail. So my task is now I
do have a public key because its
public everybody knows what it
[00:07:05.60]
[00:07:08.53]
is. How do I turn this into
private key. Now from the
definitions it is really pretty
[00:07:13.97]
straightforward and simple. Um I
need to find those prime numbers
that make up this number n. This
[00:07:18.97]
[00:07:22.37]
number n is known it is part of
the public key. And if I can do
this I can easily calculate
[00:07:29.07]
lambda n which is really uh the
least common multiplier of
lambda p and lambda q and from
[00:07:35.67]
there I can easily derive the
private key d and uh IÕm done.
So all I need to do to basically
[00:07:40.67]
[00:07:43.03]
go from a public key to private
key is to find those two prime
factors p and q and um that I
[00:07:50.00]
chose in the very beginning when
I set up my key um uh then I
have everything that I need to
[00:07:55.13]
do to basically derive a private
key from a public key. Um while
that sounds pretty easy and
[00:08:00.13]
[00:08:03.33]
straightforward actually to do
this and to factor this number n
into the uh prime parts p and q
[00:08:09.40]
is um is uh really really hard
and all of the classically known
algorithms are all from
[00:08:15.63]
exponential complexity. Which
means they are really really
hard uh to solve even yÕknow the
[00:08:21.37]
GNFS uh algorithms is uh
slightly sub-exponential but
still massive in style so that
[00:08:26.80]
gives you those assurance that
if you use any of the asymmetric
algorithms uh people will need
[00:08:32.73]
trillions of years to decrypt
them so theyÕre fairly secure
for generations to come. But in
[00:08:39.20]
1984 a guy called Peter Shor he
was um uh a theoretical
physicist came up with this
[00:08:44.67]
algorithm. If we were to use
quantum computers. Obviously in
1984 it was all just a theory
[00:08:51.30]
quantum computers didnÕt exist
and they hardly exist today um
but the theory says he came up
[00:08:57.73]
with an algorithm of how to
factor those numbers in just
polynomial time. And in just
[00:09:02.90]
polynomial time really is a
difference that is really almost
incomprehensible. Because it
[00:09:09.47]
really means instead of taking a
trillion years on a classic
computer with a trillion
[00:09:14.83]
operations per second. Suppose
we have a quantum computer which
just does a million operations
[00:09:19.50]
per second. I can actually do
the same thing in just ten
seconds. So the difference
[00:09:25.20]
between exponential complexity
and polynomial complexity is
just out of this world and then
[00:09:30.60]
obviously if we could run this
algorithm it would pose a big
threat to um basically the whole
[00:09:35.87]
cryptosystems as it is deployed
because the base of this whether
it is um for RSA or elliptic
[00:09:40.87]
[00:09:44.43]
curves or for digital signatures
ECDSA which is using bitcoin or
for uh a key exchange like
[00:09:50.20]
Diffie-Hellman which is mainly
used in everywhere you go uh on
SSL or TLS exchanges so the base
[00:09:55.20]
[00:09:57.20]
foundation of this is used
virtually everywhere in todayÕs
internet. So they would be a big
[00:10:01.83]
threat. So letÕs explore a
little bit um how Peter Shor
came up with his algorithms.
[00:10:08.80]
What is actually needed and how
they work in uh in reality. So
now we need to a did a little
[00:10:15.23]
bit of an introduction into
quantum computing and it only
gets as deep as I thought we
[00:10:21.17]
need to go to understand how
ShorÕs algorithm works and uh
what we need to understand and
[00:10:26.73]
um uh so hopefully it-its not
its not too bad. So basically
there are two main types of
[00:10:31.77]
quantum computers right now. One
is called gate based quantum
computers. ThatÕs a big chunk
[00:10:37.57]
what everybodyÕs working on. All
the big guys IBM, Intel,
Microsoft, Alibaba they all
[00:10:42.87]
working on gate based quantum
computing which is called
universal quantum computing
[00:10:47.67]
because I can solve virtually
any problem similar to a
classical computing on this
[00:10:52.40]
computer. There is a different
computer um uh called quantum
annealers or Adiabatic quantum
[00:10:58.90]
computing which is was the first
quantum computer that was
available was from D-wave. And
[00:11:04.00]
D-wave computer this adiabatic
quantum computer is not a
general quantum computer. You
[00:11:09.00]
cannot solve every problem on
this quantum computer. It is
only specialized to solve a
[00:11:15.00]
particular optimization problem
so itÕs very much um you can
look at this basically as a
[00:11:21.43]
physical system and physical
systems tend to always end up in
the lowest energy state which we
[00:11:27.17]
call the ground state in this
system. So if I can now define a
function that I want to solve
[00:11:34.03]
and I basically define those
function in a way that the
lowest energy state is basically
[00:11:39.03]
[00:11:41.97]
the same as the solution to the
optimization problem I can use
this physical system to solve
[00:11:48.17]
the problem that I have because
I know this physical system will
end up in the lowest energy
[00:11:52.77]
state in the ground state. And I
know then this also tends this
also represents the state when
[00:11:59.20]
my optimization problem reaches
the lowest state. And there is
this really cool um theorem
[00:12:05.53]
which actually guarantees to me
that I end up in the lowest
state that there is. You can
[00:12:11.00]
really this of this kind of like
mountains and valleys. And you
can end up in a valley that is
[00:12:15.57]
just halfway through and you are
not really in the lowest state.
But there is a theorem um uh we
[00:12:20.63]
are gonna explore thatÕs a
little bit which guarantees
which gives me a way how we can
[00:12:23.97]
really be at the lowest state so
we can solve or I can find the
optimum solution to this
[00:12:29.20]
optimization problem. But it is
really just solving optimization
problems. The gate based quantum
[00:12:34.03]
computing is really a general
quantum uh general computing um
uh architecture where you start
[00:12:40.40]
with an input. You apply all
sorts of different calculations
to it. Technically these are all
[00:12:45.87]
gate based calculations. You do
an end gate. You take two qubits
and do something to it you get a
[00:12:50.93]
result. But essentially you have
an input you calculate something
and you have an output. And it's
[00:12:55.60]
basically uh you can calculate
uh every uh everything you want
to calculate with these
[00:13:00.40]
universal quantum computers
while quantum computers like
D-waveÕs can only solve
[00:13:07.20]
optimization problems. But
actually, as it turns out both
approaches can be used to solve
[00:13:12.80]
the factorization problem. And
uh we have ShorÕs algorithm from
1994 which uh uses gates to uh
[00:13:17.80]
[00:13:22.00]
solve this problem. And in
Quantum Annealing we have
various approaches since 2002
[00:13:26.60]
and IÕm going to explore those a
little bit in uh in the next
couple slides as well how they
[00:13:31.10]
work to actually um uh solve the
factorization problem as an
optimization problem. So uh
[00:13:37.33]
let's dive a little bit into
quantum computing and what I
need to understand to to explore
[00:13:43.07]
a little bit ShorÕs algorithms
and really with the idea of
giving you an understanding of
[00:13:48.67]
how can someone derive an
algorithm that gives me now such
a dramatic improvement over an
[00:13:55.30]
classical algorithm which takes
um exponential time uh to solve
So the basic building blocks for
[00:14:00.30]
[00:14:03.43]
uh quantum computers are what we
call qubits. qubits is the
equivalent of uh classical bit.
[00:14:08.83]
Classical bit is either zero or
one. A qubit is now a you can
almost think of it as a quantum
[00:14:15.33]
mechanical system which can be
in any state you want it to be.
And you actually donÕt really
[00:14:20.67]
know what state it is. But once
you measure this quantum
mechanical system it is either
[00:14:25.77]
gonna be zero or one. And this
is an uh this is something that
we are going to explore it later
[00:14:30.97]
on that why before we measure
this system we donÕt know which
state it is but it can actually
[00:14:36.67]
be in a superposition. It can be
in a state where all of these
qubits can um interact with each
[00:14:43.57]
other and only at the very end
of my processing step I will
measure the system and all of
[00:14:49.43]
those superpositions state will
basically terminate and I know
it is either zero or one. But
[00:14:54.50]
it's really a quantum mechanical
system you donÕt really know
what it is. ItÕs neither zero.
[00:14:58.90]
ItÕs neither one. It is
something in between. Uh Quite
often we assign variables to it
[00:15:03.90]
[00:15:06.70]
and here you can see a
representation of one of those
qubits. We have two bases zero
[00:15:11.03]
and one which basically
represent. Uh this zero means if
I represent the qubits in one
[00:15:16.03]
[00:15:19.67]
hundred percent of the cases I
will get the measurement outcome
of zero. The one means in one
[00:15:25.07]
hundred percent of the cases of
measurement it will give me the
measurement outcome of one. And
[00:15:29.20]
now qubit is in the
superposition of those two with
alpha and beta. The two complex
[00:15:34.83]
numbers I can represent those
and uh that uh can now define
the state of this particular
[00:15:41.23]
qubit. Now we call alpha and
beta probability amplitudes
because if I measure this
[00:15:47.57]
particular um uh qubit I will
now get the probability of the
measurement outcome for uh to
[00:15:52.57]
[00:15:56.47]
get the measurement outcome zero
the probability is going to be
alpha squared. And the
[00:16:01.50]
probability of getting the
measurement outcome of one is
going to be beta squared.
[00:16:06.30]
Remember when I measure this
particular thing even though it
is two complex numbers
[00:16:09.57]
associated with it it is going
to be either zero or one with a
certain probability associated
[00:16:16.00]
with it and the probabilities
really are defined by those two
numbers and basically to the
[00:16:21.07]
square for uh um alpha and beta.
Uh we know right now is going to
end up in zero and with those
[00:16:26.07]
[00:16:28.13]
two numbers I can represent
those qubits it's basically a
mathematical representation of
[00:16:33.40]
the quantum mechanical system uh
that the quantum computers are
operating. But remember all of
[00:16:39.40]
these measurements and
everything we do in the quantum
world is probabilistic.
[00:16:43.30]
EverythingÕs just a probability.
I can put a quantum in a state
where I can tell you in exactly
[00:16:50.00]
half of my measurement is gonna
be zero and half of my
measurement is gonna be one.
[00:16:53.93]
Which is perfect for random
numbers for example because I
can tell you, hey, you donÕt
[00:16:57.57]
really know whether itÕs zero or
one. ItÕs exactly equal
probability of getting zero and
[00:17:01.50]
one so I just take one qubit.
Measure it five trillion times
and I get five trillion random
[00:17:06.43]
bits. But obviously I donÕt
really know whether I get zero
or one. ItÕs all defined by
[00:17:11.47]
probabilities. Which has a big
implication on the algorithms
because the algorithms will also
[00:17:16.53]
only give me probabilities.
ThereÕs no algorithm that can
give me I run through this
[00:17:21.80]
algorithms once and it will give
me yes it is this answer. It
will always only give me yeah I
[00:17:27.80]
think with 83 percent
probability it is going to be
this answer for example. So
[00:17:31.90]
quite often you run these
algorithms multiple times to
really see um uh uh uh where you
[00:17:36.90]
end up with. The second um uh
principal that we need for
ShorÕs algorithm is the concept
[00:17:43.00]
of entanglement and uh that gets
slightly philosophical. Um I
wanna focus a little bit more on
[00:17:48.80]
the mathematical part of this.
Entanglement is basically a
property where I can have two
[00:17:53.63]
qubits and I know that there is
some correlation between those
two qubits. In the classical
[00:17:58.67]
world I have two bits and the
two bits are completely
independent of each other.
[00:18:02.23]
Neither of those bits will
interact with the other and if
this bit is one it doesnÕt
[00:18:05.80]
matter what this is. In the
quantum world I can have a a
relationship a correlation
[00:18:07.80]
between those two qubits. And a
simple example is a bell state
of two qubits. So this state is
[00:18:09.80]
here a state where you have two
qubits. In this funny notations
the first zero is the value of
[00:18:14.80]
[00:18:26.30]
the first qubit. The second zero
is the value of the second
qubit. But if I would measure
[00:18:31.00]
this qubit here and suppose I
measure the first qubit as being
zero it cannot be the second one
[00:18:37.27]
because yÕknow the first one the
first qubit was zero. So the
second qubit has to be zero as
[00:18:43.43]
well. I know that the second
qubit is gonna be zero simply
because I measure the first
[00:18:48.63]
qubit. And thereÕs no way
because I donÕt have zero ones
or one zero in there that the
[00:18:54.00]
second qubit could something
different than zero. So I take
basically two qubits. Give them
[00:18:59.90]
into this quantum mechanical
system. Prepare this bell state
and now I have two qubits that
[00:19:04.73]
are separate from each other but
in this quantum mechanical
system those qubits are now
[00:19:10.30]
correlated or what we call
entangled. And now I could give
one qubit to Alice and send her
[00:19:16.30]
to the moon and one qubit to Bob
and send him to Mars. And I know
that if Alice looks at her qubit
[00:19:21.30]
[00:19:23.53]
and says Òoh I got a zeroÓ I
know Bob has a zero as well.
Even though there is no
[00:19:30.43]
communication between those
simply because there is this
correlation these properties now
[00:19:35.70]
I need obviously those two
qubits I need to prepare them
together and then I can send
[00:19:40.50]
them anywhere I want and they
are now correlated without any
communication in between those
[00:19:46.83]
two. There is lots of
philosophical implications
because I can give I could put
[00:19:52.87]
those two qubits light years
away from each other and did I
really find a way of
[00:19:58.73]
communicating faster than light?
No I didnÕt because if Alice
measures its gonna be zero. If
[00:20:04.00]
she wants to tell Bob ÒHey I
measured zeroÓ she needs to
communicate this information to
[00:20:08.23]
uh Bob which obviously uh she
needs uh a few light years uh to
do so. But it's an important
[00:20:14.20]
principle we gonna use in ShorÕs
algorithm as well. And the main
thing for you to understand is
[00:20:19.70]
the um exponential large size. I
can look into when dealing with
these quantum systems. LetÕs
[00:20:26.33]
suppose I take two classical
bits. I can uh represent four
possible states with two
[00:20:31.73]
classical bits. But only one of
them at a time so yÕknow if uh
you see the four states there.
[00:20:37.53]
My system with those two bits is
in one of those states at any
one point at point in time. In a
[00:20:43.13]
quantum world I can take two
qubits and basically at the end
when I measure this system itÕs
[00:20:48.87]
also gonna be in one of those
four states. But before I
measure this system because of
[00:20:53.33]
superposition those qubits can
be in all four states at the
same time and only when I
[00:20:58.33]
[00:21:00.97]
measure the system the system
will collapse one of those four
states. And this is exactly now
[00:21:07.00]
a situation we are gonna explore
it. If you have n qubits I can
represent two to the power of n
[00:21:12.90]
state while I do calculations I
still at the end of the day need
to know what the result is uh of
[00:21:18.80]
my calculations so I need to
measure at some stage and the it
will collapse obviously to um uh
[00:21:24.53]
those end states but during
calculations I have two to the
power of n states which is a
[00:21:29.97]
massive amount of uh um uh
states that I can represent with
just a few amount of uh of
[00:21:35.30]
qubits. So now I now I have
everything kind of to look into
ShorÕs algorithm and how it and
[00:21:40.30]
[00:21:42.40]
how it works. Um uh and we are
gonna look into this. So the
main idea for that Shor had is
[00:21:47.40]
actually that if I want to look
into how to factor uh N into p
and q into hose two prime number
[00:21:52.43]
I donÕt actually have to solve
that problem. That problem is
equivalent to a different
[00:21:57.50]
problem. And basically he looked
into number sequences and he
realized from number theory that
[00:22:04.13]
you have a number sequence for
example uh you look at the
number sequence here you
[00:22:10.03]
multiply the previous number by
two. So you have 1, 2, 4, 8, 16,
32. If you now do if you now use
[00:22:17.03]
this number sequence and do this
mod 15 for example in this
example. You end up with this
[00:22:23.50]
number sequence 1, 2, 4, 8, 1,
2, 4, 8, 1, 2, 4, 8. This is
what we call a periodic um uh
[00:22:29.17]
sequence. So it is always gonna
be the same uh um kind of
sequence of 1, 2, 4, 8, and we
[00:22:35.47]
can now define a um uh uh a
number which is called a period.
Which is four which is basically
[00:22:42.33]
the number of the amount of
numbers before it repeats itself
and um uh the underlying
[00:22:49.13]
algorithm from Shor is that if I
want to find out the factors for
this number N. If I want to find
[00:22:56.10]
this p and q I can actually
transform this into problem of
finding the period R and that
[00:23:02.77]
turns out for that problem I can
run very easily on a quantum
computer. So basically um uh if
[00:23:09.37]
I look into this and the cool
thing is and IÕm gonna show you
on the next slide the
[00:23:13.80]
mathematics behind it is
actually basically very trivial
basic level of linear algebra
[00:23:18.53]
gives you everything to
understand how this works. So
the only thing you need to
[00:23:22.43]
accept is that out of number
theory thereÕs a theory which
basically says this theory this
[00:23:26.27]
function f(a) x to the power of
a mod N is a periodic function
um if x has um particular
[00:23:31.27]
[00:23:34.57]
properties and now I only need
to find uh the number uh the
period R and with this I have my
[00:23:39.57]
[00:23:42.10]
algorithm Shor which we run
through in quantum detail
actually but essentially it's
[00:23:46.23]
comprised of three phases. First
I turn this factoring problem
into a uh period finding problem
[00:23:52.07]
and that's actually trivial.
Then I use a quantum computer to
actually give me this period R
[00:23:57.07]
[00:23:59.37]
to solve this period R the
classical computer is again,
really really hard actually on
[00:24:04.43]
the classical computer still is
of exponential complexity which
mean that this algorithm on a
[00:24:10.30]
classical computer does not give
me any advantage whatsoever. But
I can use a quantum fourier
[00:24:16.70]
transform and that gives me the
speedup and then by once have
the period. R you can really
[00:24:21.17]
very trivially um uh use this to
find the factor so stage one or
step one and step three are
[00:24:27.10]
really trivial. Step two is
where all the magic happens and
thatÕs really where the main
[00:24:30.83]
speedup um comes. DonÕt wanna go
into two much detail but it is
really very simple so I think
[00:24:37.60]
you can uh download the slides
and you can look through this. I
know that f(a) is periodic. I
[00:24:44.03]
know that x to the power of zero
is one. I mean, everything to
the power of zero is one. And if
[00:24:49.17]
R is now my period I know
because the functionÕs periodic
that x to the power of r mod n
[00:24:55.63]
equals one two. Equals the same
what it was before because is
one period. And really with
[00:24:59.93]
basic linear algebra I can use x
to the power of r equals x to
the power of uh a half to the
[00:25:04.23]
power of two. And i can uh um uh
just write this in a different
form which gives me this um uh
[00:25:09.23]
[00:25:13.87]
this multiplication of two
numbers that gives me xero uh
mod n. So if I can use this if I
[00:25:18.87]
[00:25:23.33]
had this R I ha- I have these
two numbers so but if those two
numbers um uh mod N is uh uh
[00:25:28.33]
[00:25:31.40]
those arenÕt integers of
multiple of N because their
product is zero mod n so that
[00:25:37.90]
means that theyÕre integers
multiple of n so either those
are directly factors or if they
[00:25:44.10]
are not directly factors each
one of those has a factor in
common with a number I want to
[00:25:50.60]
look at. So the greatest common
divisor which is actually um not
too hard to computer um
[00:25:56.57]
classically it is just an n
squared complexity so by
computing the greatest common
[00:26:01.73]
divisor for each of those
numbers with n I have my factors
uh for uh for n and uh that is
[00:26:06.73]
[00:26:09.03]
really simple. But to get to
this R is really really hard.
But I can put this together uh
[00:26:14.90]
in a really quick example. LetÕs
suppose I have N equals 15. Now
everybody can calculate in their
[00:26:19.90]
head that prime numbers are 3
and 5. Basically I choose any
integer between 1 and 15 and
[00:26:24.90]
[00:26:27.37]
really lets for the sake of
simplicity let's use x equals
two. So you can see my period
[00:26:33.73]
here on mod 15 is 1, 2, 4, 8 uh
so I have the period 4. So I can
see this. ThatÕs the really hard
[00:26:39.70]
part to uh calculate But with a
period 4 the greatest common
divisor of x to the power of uh
[00:26:44.70]
[00:26:47.30]
uh R half is R is four so R half
is 2. Uh X is 2 so that is two
to the power of 2 which is four.
[00:26:52.30]
[00:26:54.90]
So the greatest common divisor
of 3 and 15 and 5 and 15 so uh
so uh four minus one and four
[00:27:01.13]
plus one is obviously 3 and 5.
And when you calculate the
through action in every case you
[00:27:05.90]
come up with uh 3 and 5. So
thatÕs exactly what ShorÕs
algorithm is all about. But the
[00:27:11.17]
really hard part is uh figuring
out what is this period R and
this is kind of where the
[00:27:16.33]
quantum uh compu- quantum
algorithm comes in. And those
computers, those quantum
[00:27:21.40]
algorithms always work in the
same principal. You basically
you initialize basically the
[00:27:26.40]
[00:27:28.53]
result that you want to see and
say letÕs think of we want to
get a 256 bit number or 2048 bit
[00:27:33.53]
[00:27:36.00]
number and you basically every
bit every bit of this bit
recommendation is either gonna
[00:27:40.67]
be zero or one. So you basically
put this in an equal uh
superposition so every bit you
[00:27:45.47]
basically put at fifty percent
zero and fifty percent one
because you really donÕt know
[00:27:48.70]
what it is. So itÕs really kind
of like uh at fifty percent.
Then you run through this
[00:27:54.47]
Quantum Fourier transform which
will use amplitude amplification
so with every duration of this
[00:28:00.97]
algorithm those amplitudes will
go toeither one or to zero which
is gonna be the final result.
[00:28:05.97]
[00:28:08.30]
And you run this through uh a
number of times and then you
measure it at the end and you
[00:28:14.50]
will see when you end up with.
IÕm gonna have an example of
this uh when we run this through
[00:28:20.10]
on a on real quantum computer.
So just to um uh summarize.
ShorÕs algorithm altogether is
[00:28:25.60]
fairly simple. You choose any
random number a which is uh
smaller than N. You compute the
[00:28:31.20]
greatest common divisor. If this
is not one. Actually you found a
you found a factor and then you
[00:28:35.83]
are done. But that is uh
obviously uh most likely not the
case. I use my quantum computer
[00:28:41.17]
to find this period R and once I
have R I just need to find the
greatest common divisor of those
[00:28:46.70]
uh two uh two terms and IÕm
done. So um uh another example I
choose randomly uh number seven.
[00:28:51.70]
[00:28:54.90]
Calculate period r, R equals 4.
I have the greatest common
divisor 48 and 15 and 50 and 15
[00:28:59.90]
[00:29:02.43]
gives me uh 3 and 5 so it uh all
works fine. I can now use this
and use uh um a livbrayr a
[00:29:07.43]
[00:29:10.60]
toolkit called Qiskit which is
an open source toolkit thereÕs
now at least 5 or 6 open source
[00:29:16.40]
platforms how you can use
quantum computers and how you
can program quantum computers um
[00:29:21.63]
either on quantum simulators or
on real quantum hardware. And i
gave you some references here
[00:29:27.63]
you can look at those it's
actually kind of fairly easy um
uh to go through. But they also
[00:29:32.63]
have the same and hereÕs an
example of this amplitude
amplification. Basically in the
[00:29:37.13]
end you see all of the
possibilities what the my prime
numbers could be. They all in
[00:29:42.60]
the same probability of what
they could be. ThatÕs my
starting point. And once I run
[00:29:47.83]
through this algorithm and I ran
through this uh ShorÕs algorithm
on from these references. The
[00:29:53.93]
amplitude of the correct results
have now been amplified and the
amplitudes of the wrong results
[00:29:59.90]
have now been kind of like gone
down to zero. And I actually see
that these two results R equals
[00:30:05.33]
0 and R equals 4. R equals zero
is obviously trivial um uh
probability so I discard this
[00:30:08.00]
and I end up with R equals 4. So
this was now executed on a
quantum simulator. Quantum
[00:30:13.00]
[00:30:17.47]
simulator I can simulate a
quantum state on my normal
computer. But remember in
[00:30:21.77]
quantum computing we exploiting
this fact that I have this
massive large space of 2 to the
[00:30:26.37]
power of N so IÕm gonna really
travel simulate more than
hundred qubits or so on a normal
[00:30:32.17]
computer and um uh uh but for
smaller ones uh for
demonstrations it is actually
[00:30:37.23]
quite cool. So the cool thing is
IBM has a quantum computer that
you can publicly access you can
[00:30:43.40]
write a uh a quantum computer
program executed towards their
cloud. It's very simple you just
[00:30:49.47]
change hey my backend is the
simulator you change the backend
to uh IBMs quantum computer. Um
[00:30:55.27]
and if you execute this against
a real quantum computer. It is
just a 5 qubit quantum computer
[00:31:00.03]
um uh right now. I still get R
equals 4 with the highest
probability. But you see there's
[00:31:05.97]
lots of other probabilities and
those probabilities are
representative of all the errors
[00:31:11.37]
you have in the system simply
because those quantum computers
that we have right now are
[00:31:15.87]
really pretty bad. What they are
what we call noisy. They donÕt
produce the correct result.
[00:31:20.87]
[00:31:22.93]
Because theyÕre noisy they
produce lots of wrong results.
Now repeat- by repeating my
[00:31:28.33]
algorithms lots of times I can
still get around this fact and
obviously in this case I still
[00:31:33.87]
have R equals 4 the highest
probability. But obviously that
has big implication of
[00:31:38.10]
performance because I need to
now repeat these um these
algorithms much more and
[00:31:43.07]
obviously I will end up in debt
cases because obviously the
noise will basically um uh
[00:31:49.27]
reduce the speedup in the
quantum effects to zero and it
basically collapses to um uh a
[00:31:55.43]
um a classical computation that
I have. But the cool is actually
with Qiskit as well there there
[00:32:00.43]
[00:32:02.97]
is libraries for every quantum
algorithm that yÕknow that
people know and they kind of uh
[00:32:07.90]
provide these libraries. If you
wanna run ShorÕs algorithm to
factor a prime uh to factor any
[00:32:13.00]
numbers. You just import ShorÕs
algorithm from Qiskit aqua which
is a which is a library. You
[00:32:19.07]
just say alright I want to
factor this number N equals 15.
I use a simulator. I do this uh
[00:32:24.43]
1,000 times and uh off I run.
ItÕs instant and I get a result.
How cool is this that you can
[00:32:31.00]
run this uh run this against a-
against a Quantum computer and
the only thing you need to do in
[00:32:34.60]
this example is if you run this
against real quantum computer is
you change the backend from the
[00:32:39.00]
simulator to a different backend
and now thereÕs a callout to
IBMs uh quantum computer to run
[00:32:44.80]
this uh on their backend. It's
actually really really cool and
this feeling when you run a
[00:32:49.90]
quantum computing software for
the first time is actually quite
cool. So I encourage everybody
[00:32:55.40]
to look at Qiskit or various
quantum computer libraries and
to play around with this. So the
[00:33:01.47]
problem obviously is and you
guessed it is in order to do
anything meaningful I need lots
[00:33:07.33]
of qubits. So in order to use uh
ShorÕs algorithm to um uh to
break RSA 2048 I need 4,000
[00:33:12.57]
qubits and I need 4,000 proper
qubits meaning without any
noise. I need for the time of
[00:33:14.63]
the computation there canÕt be
any noise on the computation as
well. And it's not really a
[00:33:19.63]
[00:33:26.53]
surprise because when Shor came
up with this in 1984 there
werenÕt any quantum computers.
[00:33:31.40]
He didnÕt have to worry about
hey can I really implement my
algorithm or not. He really just
[00:33:35.73]
came up with this system and
method. So um it was never
really meant to run on a quantum
[00:33:40.77]
computer and um right now lots
of people look at ShorÕs
algorithm and they say alright
[00:33:42.77]
uh kind of right now we have 70
qubit so its every the qubit
count doubles every year
[00:33:45.97]
whatever so it's gonna be
another ten years before um we
have ShorÕs algorithm. NobodyÕs
[00:33:47.97]
gonna run ShorÕs algorithm
because it was just a theory. So
letÕs look at some of the-the uh
[00:33:50.90]
research where people took
people took ShorÕs algorithm and
modified them and optimized them
[00:33:53.73]
to run on real quantum uh
quantum hardware. So the first
one was Fowler in uh in 2012.
[00:33:56.57]
Basically the first approach was
really kind of I need to tweak
this algorithm so it can be so
[00:33:59.80]
it can sustain errors. Because
ShorÕs Algorithm was really
under the assumption thereÕs no
[00:34:04.80]
[00:34:12.03]
errors or the qubits are
fantastic uh no errors so
basically they used what is
[00:34:17.03]
[00:34:27.80]
called the surface codes to
allow for errors to occur and
the error rate is 0.1 percent of
[00:34:34.23]
the uh of the gate error rate
and um uh Fowler came up I can
run ShorÕs algorithm and I can
[00:34:40.80]
factor 2048 bit number but I
need one billion qubits to do so
which is obviously a massive
[00:34:47.20]
amount uh in terms of over it um
to run this. So that was in
2012. Not to long a- not too
[00:34:53.47]
long ago. And then in 2017 with
further optimization from OÕ
Gorman we suddenly kind of like
[00:34:59.97]
had uh had an algorithm where it
reduces one billion qubits to
230 million qubits uh in 2017.
[00:35:04.97]
[00:35:09.30]
And thatÕs really an
optimization the physical
connectivity of those qubits.
[00:35:13.43]
And uh then Gheorghiu kind of
reduces further to 170 million
qubits so you can see thereÕs
[00:35:18.50]
algorithmic improvement without
any hardware improvements
obviously thatÕs happening at
[00:35:23.97]
the same time as well but
obviously I get down from 1
billion qubits to right now 170
[00:35:28.43]
million qubits. And the biggest
um uh contribution was from
Gidney and Ekera from uh um uh
[00:35:34.90]
Google and uh University in
Stockholm where they uh provided
paper just not long ago earlier
[00:35:40.87]
this year where they uh looked
into how they could do the same
thing that everyone else is
[00:35:46.20]
doing with just 20 million
qubits. Now we went in 2012 with
1 billion qubits to 2019 to 20
[00:35:51.20]
[00:35:53.67]
million qubits and we are far
from the end of the research
there in terms of optimization
[00:35:59.63]
uh to this problem. Now I wonÕt
go into too much detail of this
uh of uh what they do but
[00:36:06.17]
basically they also look into
lots of optimization of how
things work. And that basically
[00:36:11.13]
also similar to Shor not really
look into factoring the numbers
directly so that basically
[00:36:16.13]
[00:36:18.73]
convert this factoring problem
into Shor Discreet Algorithm uh
problem and um uh they have a
[00:36:24.00]
part that is computed
classically and a part that is
computed um quantumly on a
[00:36:30.87]
quantum computer. And they can
show that in order to find p and
q they can come up with
[00:36:37.63]
obviously they know what n is
which is uh the multiplication
of those two. They can come up
[00:36:43.23]
with a number where they know
that the addition of these
numbers is these or these known.
[00:36:47.47]
Sol if they have two uh
equations for two variables
which they can fairly easily
[00:36:53.33]
solve fairly easily is obviously
an overstatement because they
still need uh 20 million uh
[00:36:56.77]
qubits uh to do so. Um uh but
obviously the uh the um
reduction from 1 billion qubits
[00:37:03.70]
to 20 million qubits is uh
massive and uh I expect in the
next couple of years thereÕs
[00:37:08.23]
gonna be lots of optimization
through ShorÕs algorithm and
especially to Gidney and EkeraÕs
[00:37:12.97]
um uh algorithm where this is
gonna be uh reduced uh further
on. Obvuiously 20 million qubits
[00:37:19.33]
is still a long way away from uh
quantum computers that are
accessible today um uh where we
[00:37:25.63]
are in the realm of slowly below
100 qubits um uh at this point
in time. So I want to spend the
[00:37:30.63]
[00:37:32.97]
next you know or the last ten
minutes of my presentation on
the process of quantum
[00:37:36.87]
annealing. This is the second
type of quantum computer and uh
that is actually what is quite
[00:37:42.03]
surprising to me even though
everyone is talking about Shor
and the implication of
[00:37:45.80]
cryp-cryptography. Actually
quantum annealing right now is
much much further ahead in terms
[00:37:50.93]
of solving this factorization
problem. And we are going to
look into a little bit how uh
[00:37:55.40]
these algorithms work. So as
mentioned before quantum
annealing those computers are
[00:38:00.43]
really computes where it can
solve optimization problem. I
need to I need to define my
[00:38:05.10]
problem as an optimization
problem and then basically
quantum annealing computer can
[00:38:09.83]
take this problem and then find
uh minimum of this uh problem
because it represents a physical
[00:38:16.10]
state and I know the physical
state will always end up in the
ground state and I can read in
[00:38:20.77]
this ground state and I will
have the solution to my problem.
And there is really a cool a
[00:38:25.03]
cool theorem um uh where youÕre
gonna find you wanna go into the
lowest point. You wanna find
[00:38:32.00]
this lowest point on the right
hand side. So how do we find
this lowest point and not get
[00:38:36.07]
caught up in those uh minimums
uh in between. And thereÕs lots
of ways how you can do this from
[00:38:41.93]
the uh from the physical system.
And thereÕs really cool case on
this quantum annealing case
[00:38:48.00]
where there is a theorem that
says if I start in a really in a
very easy quantum mechanical
[00:38:53.00]
[00:38:55.50]
system. In this really easy
quantum mechanical system I know
the ground state. So this is my
[00:39:01.57]
problem I want to solve is here.
I am starting here and I really
know where I am. I can now
[00:39:06.77]
slowly evolve and adiabatic
means slowly evolving this state
from this here to the state
[00:39:13.43]
where I really wanna be and now
this theory gives me a guarantee
or physical proof that I will
[00:39:20.00]
end up in the in the maximum in
the optimal minimum of the
problem that I wanna solve. And
[00:39:26.27]
itÕs really cool so I have
Hamiltonians or functions that
define a physical system but
[00:39:31.53]
basically if you look at the
first function if you put in s
equal zero you end up in this
[00:39:36.20]
high H zero which is my easy to
understand system where I know
the local minimum and in my
[00:39:41.20]
[00:39:43.23]
calculation I slowly moves from
zero to one and if I am at one I
am in the stage high H one which
[00:39:49.47]
is the problem that I really
want to solve. But this uh
adiabatic theorem guarantees to
[00:39:54.87]
me that I will end up in the
maximum minimum for the problem
that I really want to solve.
[00:40:00.60]
Which is really really cool
because it gives uh I know IÕm
not going to be caught in some
[00:40:05.40]
local minimum. But still
essentially I wanna solve for
optimization problem. How do I
[00:40:09.47]
do this. And the first research
came from Burges in 2002 from
Microsoft. Where you know he
[00:40:15.80]
provide a foundation of hey I
wanna solve basically I wanna
look into the problem n equals p
[00:40:21.53]
times q. I am looking for p and
q um uh so that this equation is
true. So I just need to solve
[00:40:27.97]
this I need to write this as
optimization problem. And
basically he rewrote this as N
[00:40:32.87]
minus pq squared and this is
always a positive function. Is
always greater than zero. And
[00:40:38.33]
this is obviously only zero if N
equals pq. And if you write this
way you have what's called a
[00:40:43.33]
[00:40:45.83]
QUBO a Quadratic unconstrained
binary optimization problem
which you can happily run on any
[00:40:51.67]
quantum annealer that is out
there. And you basically use
binary representation that is
[00:40:56.30]
really just a fancy way up here
of writing P i and Q i but just
the i-th bit itÕs either zero or
[00:41:01.00]
one. And you basically now write
this down and it's a very simple
example. My example 15 is 5
[00:41:03.00]
times 3. Now um uh in binary
notation p equals x1,1. The last
bit always has to one because
[00:41:05.00]
the prime number canÕt be an
even number. And I just you
know, n minus pq squared I just
[00:41:07.43]
write it through and kind of by
hand say oh this function I need
to minimize now. And I can run
[00:41:13.90]
this against D WaveÕs quantum
computer and if I find the
minimum I know n equals pq
[00:41:20.53]
because thatÕs by definition a
positive function. So I can use
quantumÕs uh DÕwaveÕs quantum
[00:41:23.17]
computer they provide a library
as well and you see the link
here you can download it. ItÕs
[00:41:26.33]
basically same thing you just
call factor P. P is my uh my
product and I can run this on uh
[00:41:29.97]
DÕwaveÕs quantum computer. The
problem is if I run this without
any optimization I need n
[00:41:34.97]
[00:42:00.90]
squared qubits for this so I
mean the number of qubits that I
need really kind of like grow
[00:42:06.53]
quite heavily and for larger
numbers is not sustainable uh to
do. But I wanted to show you
[00:42:11.53]
[00:42:13.53]
itÕs all probability so if I run
this one time I end up with um
uh my for 15 for the p and q for
[00:42:18.53]
[00:42:20.60]
my two prime numbers is one and
seven which is obviously wrong
so I run this once and I didnÕt
[00:42:26.50]
really end up in the uh in the
right spot. But I run this five
times and now I already have 5
[00:42:31.37]
and 3 is already 60 percent um
uh you know probabilities. And
if I run this fifty times you
[00:42:36.60]
know I know my prime numbers are
already 3 and 5 so I know I need
to run those quantum algorithms
[00:42:42.53]
more and more often to make sure
I end up in the same results. Um
IÕm gonna skip over some of
[00:42:47.87]
those things because virtually
all optimizations of now this
base you know of of BurgessÕs
[00:42:54.30]
work where he basically looked
into hey my multiplication
matrix that you write out as a
[00:42:59.43]
function to be minimized there
can be lots of optimizations
virtually all of the work that I
[00:43:05.53]
present here now is based on
optimizations of how you do the
multiplications down below here.
[00:43:12.30]
If youÕve ever done
multiplications by hand you know
you start on the right and you
[00:43:16.93]
kind of multiply the lowest
numbers and it carry overs to
the left and virtually all of
[00:43:21.80]
those optimizations um uh go
through this how I can do this
multiplications much easier.
[00:43:28.37]
Dridi and Alghassi did some work
in 2016 where they used some of
these uh optimizations to remove
[00:43:33.37]
[00:43:35.37]
some of the all of the degrees
so they were already able to
factor a number greater than
[00:43:41.40]
200,000 with almost 900 qubits
now D waves qubits on quantum
annealing are not as donÕt have
[00:43:46.40]
[00:43:48.50]
to be as good as universal
quantum computer qubit so D wave
announced a system with uh I
[00:43:53.97]
think around 5,000 qubits for
next year. So 900 qubits is what
was available back then on
[00:43:58.97]
[00:44:01.97]
universal quantum computers. The
biggest prime number is less
than 100 and they these guys in
[00:44:07.93]
2016 could already now factor a
number that was over 200,000.
The big breakthrough was from
[00:44:13.87]
Jiang et al in Indiana in uh
April 2018 and it is really kind
of mindblowing uh you see the
[00:44:18.87]
[00:44:21.30]
next one which was really just
uh two months after really
around optimization of this
[00:44:26.43]
multiplication map and they have
now raised. They could factor a
number which is greater than
[00:44:32.60]
350,000 with just 94 qubits.
Remember D-wave comes up with
5,000 units quantum computer
[00:44:39.07]
next week um next year. Um uh
and it's all based on this
optimization uh problem that we
[00:44:44.07]
[00:44:46.50]
solve called factoring and with
optimization to the
multiplication table. And then
[00:44:51.87]
Peng in two thousand uh in uh
earlier this year really um uh
and you can see this uh
[00:44:57.13]
submission was received in July
while the previous submission
was I think uh submitted in
[00:45:02.03]
April or something it was just
months after. Optimizes even
further and theyÕve been able to
[00:45:07.37]
factor a number that was greater
than one million with just 90
qubits. So thatÕs already 20 bit
[00:45:12.00]
number. So right now when you
look into the problem of hey can
I use a quantum computer to uh
[00:45:17.40]
factor prime numbers. Universal
computers and ShorÕs algorithms
are nowhere compared to uh
[00:45:24.27]
quantum annealers. And with
quantum annealers I can already
um uh um do this with uh 20 bit
[00:45:30.03]
numbers. So um thereÕs three
things really interesting. So
they they can run this on
[00:45:32.03]
already existing hardware today.
And all of those algorithm
thatÕs a really big takeaway um
[00:45:34.03]
uh that you have. To do this I
donÕt just have one quantum
problem that I wanna solve. ItÕs
[00:45:39.03]
[00:45:48.17]
always a hybrid model of some
classical compu-computation and
some quantum computation. I
[00:45:53.30]
really use classic computer what
heÕs good at and quantum
computer what a quantum computer
[00:45:57.30]
is um is um good at. So um my
point is quantum annealers are a
thousand fold better right now
[00:46:02.30]
[00:46:06.57]
than ShorÕs algorithm and
universal quantum computers. But
because they are too noisy right
[00:46:11.60]
now we are far away from
breaking anything that is uh in
used in practical terms. Right
[00:46:18.50]
now the biggest number is a 20
bit number. But obviously we
know uh those two uh kind of
[00:46:24.90]
like converging curves here. The
algorithms are getting better
and better. At the same time the
[00:46:29.53]
quantum hardware gives me more
and more qubits as well. So both
of them will actually have a big
[00:46:34.60]
impact. I canÕt just rely on my
predictions saying hey the
number of qubits grow by 15
[00:46:39.40]
percent every year so IÕll be
fine for the next 50 years.
YouÕre neglecting the
[00:46:43.60]
improvements that the algorithms
uh will make over the next uh
over the next uh couple of years
[00:46:48.50]
too. So a couple of uh myth and
reality. Shor, nobody is gonna
implement Shor on any quantum
[00:46:54.57]
computer whatsoever. Um uh Shor
was a theoretical work. There
are practical work um uh you
[00:47:00.97]
know derivations of this work
that will be implemented. Um at
some point obviously on the on
[00:47:07.30]
the base of ShorÕs algorithms
people will break um uh the uh
the RSA encryption. It is a
[00:47:13.07]
matter of time. Now we can argue
whether its ten years, twenty
years, fifty years. But we are
[00:47:17.43]
only arguing about the time. We
are not arguing about arguing
about that it will happen. And
[00:47:22.70]
obviously thereÕs lots of cases
where this is already has an
impact right now. If I have
[00:47:27.40]
bitcoins right now and my public
key is known. I donÕt care
whether it takes me 20 years to
[00:47:33.07]
uh get the private key to those
uh to those bitcoins. I figure
in 20 years thereÕs you know one
[00:47:37.90]
and a half million bitcoins from
Satoshi flying around which is
around 12 billion dollars right
[00:47:42.73]
now. Hey if someone come to me
and say Hi Chris you know can
you bring me quantum computer.
[00:47:47.00]
Hey itÕs really hard it takes me
12 billion dollars you know. Hey
hereÕs 12 billion dollars right
[00:47:50.73]
there. [laughter] So um um so
anyway uh it takes it will be
quite a while but I want to
[00:47:55.73]
[00:47:58.30]
[inaudible] off the algorithms
started this talk talking about
how I trust the asymmetric word
[00:48:02.97]
of the RSA word. But thereÕs
plenty of work and this is uh
kind of you know from this
[00:48:07.33]
Chinese paper in the very end.
ThatÕs the thatÕs the uh uh the
end statement. ThereÕs plenty of
[00:48:13.50]
work on the way right now to use
quantum annealers or to look
into symmetric uh encryption. So
[00:48:19.43]
if you say hey I just use
symmetric encryption I find that
might not be holding up for too
[00:48:24.50]
long and I thank you very much I
am out of time. Thank you very
much for your time. [applause]
[00:48:29.90]
Do we have time for questions?
We donÕt have time for
questions. You can find me
[00:48:34.90]
[00:48:37.00]
anywhere if you have some
questions. Happy to engage with
you. Thanks so much!
[00:48:40.70]