Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/527 Thanks!
Quantum cryptography, that is
what we will learn, how to exploit
quantum mechanics for cryptography
purposes and I think also
we will do a little bit of relativity
in it. I don't really understand
how you can combine quantum mechanics and
relativity without getting loop quantum
gravity or string theory, but I guess
we will find out. And our teacher today
will be Christian Shaffner, who is
currently at the University of Amsterdam.
Please give him a warm round of applause.
Thank you.
Thank you very much.
So I'm waiting for my slides.
Here we go.
I work at QST, which
is recently established Research
Center for Quantum Software in Amsterdam.
And as you just heard, I'm also at the
University of Amsterdam and I collaborate
with CWI.
I'm very happy to be here and tell you a
little bit more about my field of
research, quantum cryptography for
the next hour or so.
And so to get started, please put
on your 3-D glasses.
Oh, you didn't bring any
I'm sorry for that doesn't matter too
much.
Um, I'll put on mine, so we're
fine.
I'm ready.
Good.
So here we go.
In 1969,
man has first set foot on
the moon, as you can see here on this
picture sent around the world by
NASA.
But maybe they haven't, actually.
So if you believe this kind of conspiracy
theories here on the Internet,
then this scene has actually been filmed
in some Hollywood studio.
And this is all fake.
And this leads to one of the
research questions that I'm
investigating, namely, how can you
actually prove that you are at
the specific location?
So I will come back to this question a
little bit later in my talk.
First of all, here's a quick outline of
what I want to cover tonight.
So talking about quantum cryptography,
we can do without telling you a
little bit about quantum mechanics.
So there's going to be the first part of
my talk and then I'm going to focus on
two applications.
The first one will be quantum key
distribution and the second one will be
position based cryptography.
Basically coming back to that question
that I just asked.
So here we go, introduction
to quantum mechanics.
Now,
for the purpose of this talk, you can
think of a cubitt, a quantum bit,
um, as the polarization of
a photo.
Mathematically speaking, we're talking
about the UNIVAC unit vector in
a two dimensional complex Hilbert space.
But don't worry, we're going to make it
way more practical.
Photons are just particles of light.
So I imagine you can have a light source.
You put some polarizing filter here
and then this direction of this
polarizing filter, basically, it will be
the state of the cubit.
So it will be this vector.
You can actually turn this around,
this vector slang form.
And in quantum mechanics,
we kind of give some particular names to
certain directions. For instance, this
horizontal direction here, we're going to
call the zero state.
So just basically arbitrary naming.
We call this the zero state and
we use this fancy notation with this
brackets to denote
that state. In my talk, I'm just going to
use this symbol here.
So this round table with these horizontal
arrows, that's going to denote the zero
state, um,
and actually so that
the actual direction doesn't matter.
So it doesn't matter whether it points
here to the right.
It may also point to the left, which is
going to work with, say, the horizontal
way of polarizing photons.
Now, the polarization which
is orthogonal to that, we're going to
call the one state.
So here we have another state of our
covid.
And together they form a basis,
orthogonal basis of this
vector space. And we're just going to
use, say, the yellow color for it.
This is called the rectilinear or the
computational basis.
Let me get a little bit more practical,
um, and actually
build this thing, so we need a light
source, but wait a second, there's
light sources all over the place.
Actually, I'm holding a light source here
in my hand.
So this laser perfect light source,
then we need a polarizing filter.
And that's the time when you can take off
your 3-D glasses again.
And actually, next time you go to
the cinema, just grab some of them
instead of delivering them at the end of
the after show, get some extra ones
because they're actually really useful.
You can destroy them like this and
take out the polarizing filters.
And so.
Doing that, we can actually build
such a quantum system here.
I have a light source, I hold this
polarizing filter in front of it and I
can turn it the way I like.
And I basically built that system.
So let me
show you that a cubit quantum
bit is at least as good as
a classical bit.
So here we have our two heroes, Alice and
Bob. And Alice would like to communicate
a bit to Bob.
Now, what you could do is she could take
her light source, use a polarizing
filter like that, and, um, and
send that to Bob.
Bob on his side.
He could put another polarizing filter
in the orthogonality polarized.
And if no light comes through and then
he doesn't see any photons, then he would
say, well, Alice was actually sending a
zero state.
So I have prepared this little experiment
over here.
Now, maybe.
You can, uh, switch to the camera,
um, so I have a laser pointer
here, another one.
And I'm shining.
Oh, yeah, I'm using little polar bears
for polarization.
You can you can get them very cheap
if you go Christmas shopping now.
So here's the laser
eye shine through both of these
lights and you see over there right now,
Alice is sending in zero and this
other filter is ninety degrees, so
polarized.
So there's basically almost no reflection
here on the ground. And if I turn this
and actually see this point,
there is getting much more brighter.
So here is where about it's not the
perfect filter, but it's pretty, pretty
good. So now the light is almost gone.
OK, you can see.
So maybe switch back to my slides.
You can see using
this technique, we
can send classical information to
from Alice to Bob.
And in particular, if she's if Alice
is sending out the one state,
then if it's filtered, a light
will go through.
And therefore, if he sees photons, he
knows Alice was sending a one so we can
use Cubitt to send zeros
and ones. And in fact, what we are doing,
quantum mechanical is beating.
It's a so called measurement.
So Alice is sending a state and
we are doing a measurement in the
computational basis.
The outcome of a quantum measurement is a
classical bit inside a zero and one,
and this happens with a certain
probability.
In this case, if Alice is sending to one
state, then with probability one bulb
will actually get one as
an outcome and nothing changes in the
state.
So far, so good.
Now let's do something more interesting.
And what you can do with a cubit
is that you cannot only polarized,
say, in these two directions.
What you can do is you can do stuff in
between. You can just rotate
your filter arbitrarily and they're
going to call this state, which is kind
of 45 degrees between zero and one.
We're going to call that zero state as
well. But in another basis, namely the
diagonal basis.
So we have two more states, this one and
that one, and we're going to use
the red color for that in this talk.
And so these are these two states here at
the zero state in the diagonal basis and
the one state in a diagonal basis or
demand basis.
And together they form another
orthogonal basis.
So this state, the zero
state, in fact,
in terms of linear algebra, you can
interpret it as a linear combination
of the zero in one state.
So if you take this vector here zero and
you add one and you probably renormalize
to have a unit vector, then you actually
get that zero state.
So in fact, what we have
is actually a superposition of
zero and one.
So we have a we have a cubitt in a state
which is both zero and one at
the same time.
Basically just using this diagonal
polarization.
Now, what happens if you go and measure
that state in the computational
basis?
So again, the outcome will be a classical
bit, but now we're going to have a
probabilistic outcome.
So imagine I mean, what happens if
you send, like, diagonally polarized
light and you put this filter
like Bob did before?
Then roughly half of the light will go
through. Now, you saw me turning before
and the pulse was getting fainter.
So if you turn like 45 degrees,
then roughly half of the light will go
through. I would have to do this
experiment with single photons, but then
you can't see anything anymore.
So, in fact, what quantum mechanics
tells us is if you measure that state
in the computational basis, you're going
to get a random outcome with probably
one half, you're going to see a zero.
And in fact, you're changing the state
by observing it, by measuring it in
space. And because after you've seen a
zero, then the state is actually the
zero state.
On the other hand, if you, um,
with probability one half, you will get
outcome one and you change the state to
one. So whatever comes out of this filter
is actually polarized in this
horizontal in this vertical direction.
Now, let me show you the following.
And this one can actually demonstrate
I'm going to go back to the experiment.
So, um.
Sorry for all the work over there.
Thanks a lot.
So this same set ups before, um,
you see hardly any polls
on the other side because it's now
90 degrees over tonight.
It got brighter now, though.
It's almost gone. Now, what I'm going to
do is I'm going to take another filter
and I put this in between those two
filters.
And what's going to happen is that the
point actually reappears.
So this is something very strange.
No, you have like nothing goes
through and you put something more
in between and actually it's going
to reappear.
Right. So why what's
going on here?
So if you go back to the slides,
here's the explanation.
So we started off with something that is
polarized horizontally.
And clearly, if you put something 90
degrees, you don't see anything that was
the set up.
Now, what we did is the following.
We put another filter in between.
And it turns out that the zero state, you
can see it as a superposition
of this zero, a diagonal zero
state and a diagonal one state.
So it's a linear combination of these
two. It's a superposition of these two.
And once we put this diagonal filter in
between, we actually measure
in that basis, for instance, obtaining
the zero state, only letting light
through that is in this direction.
And in fact, as I said before, I have
changed the state to that.
So I've changed the polarization of the
light. Roughly half of the light is going
through from this horizontal
direction to the diagonal direction.
And now, of course, if I put another the
other filter in between now, then roughly
a quarter of the light is actually going
through.
So by putting something in between,
actually demonstrating that
measurement actually changes the state
because again, you can interpret that
diagonal zero state as a superposition of
the other two. If you're going measure,
you actually end up with something.
Yeah, so
that's the magic of quantum mechanics.
Thank you. So here's a quick summary
of what we've learned so far.
There are funny states you can actually
produce them. It's not that hard.
We use the yellow and the red color for
it. What you can do is you can measure
them. Let's take the one state, measure
it in a computational basis.
You will get with probability one
outcome, one.
You don't change the state at all.
If you happen to measure the state in a
wrong basis, say
this one state in the diagonal basis,
your outcome is a random bit.
It's probably one half.
You see zero and you change the state to
the zero state.
And with probably one of you get one,
then you change it to the other state.
So that's basically all we need to know
for now.
And with that enhanced, we actually enter
the wonderland of quantum mechanics.
We've already seen stuff that can
be zero and one at the same time.
It's kind of a superposition of zero and
one. And in fact,
here it's Schrodinger's cat you might
have heard about.
This is a thought experiment or
an experiment where you have some
say, Cubitt, that is in a superposition
of zero and one and it kind of in this
box there's a set
up. So that is a conditioned
on the outcome being one.
There's some poison released inside this
box that they'll actually kill the cat.
And if if the outcome is zero,
then nothing happens and actually the cat
is alive. So Schrodinger thought of
this experiment, don't do that
at home of this box
where inside and this kind
of superposition should extend
to this macroscopic object of a
cat which is both dead and alive
for the same time.
So this hasn't actually been observed
in reality yet.
But there are superposition
of the molecules, for
instance, though not not cats, but
maybe will get there at some point.
With these things, you can build quantum
computers, so maybe this is maybe a
picture of the currently largest quantum
computer we have, you can count them.
There's maybe nine cubits.
This is from the U.S.,
from the group of Joe Matinées at UC
Santa Barbara. They were, uh, bought by
Google. So there's a lot of development
in this area. But that's not where I want
to go in this talk.
I want to focus on this part here,
Willow, and I'm going to explain you
later in my talk about these things are
all about so.
Um.
I would like to give you a little another
little demonstration
here. I have a black box
in my hands here.
So this is a physical random
number generator.
It's connected through a cable here to
the USB port of my computer.
And what I can do with it is
I can create random numbers.
Let me switch to the application that
does that.
And now basically here you don't see
much. There's just a green, uh, flashing
here and it's connected.
Uh, here you can see the serial number.
Then I can choose what I want to do.
Let's say I create integer numbers
between zero and one. So bits, maybe,
um, a thousand of them
and press generate.
And here we go, random
bits that nobody has ever seen before.
Great.
Thank you.
So how does it work
if you look that up and go
to the Producers website electic
in Switzerland, they
they tell you that inside this box there
is a light source like this one that I'm
holding in my hand, a laser that emits
cubits like things, states that we have
seen before and
they are shot onto a semi transparent
mirror.
Again, this is like nothing fancy,
actually.
Um, yeah.
This and transparent mirror,
it lets the photons eye to go through
to this side or being reflected
to the other side. And this happened
roughly with poverty, 50 percent.
Here are some photon detectors that
detect which side they took.
And then there's some classical
preprocess post-processing.
And in the end, you end up with random
numbers.
So there's a lot of stories to tell about
this device.
Again, unfortunately, I don't really have
time for that.
Um, however, the point I want to make
here is that for this, you don't
need any quantum computer.
So there's no quantum computer inside
here. That's basically just technology
that we can actually build.
The only thing we need for this is
quantum communication.
And so this is something that we can
actually do, uh, nowadays.
Um, so I get
slowly but surely to the first
application they made one of their
quantum key distribution
and here is
a pointer away.
Um, uh,
in order to understand that, there's one
more thing I need to tell you.
And this is the so-called no cloning
theorem. So this is a mathematical
statement that says the following.
Um, let's take one of these four states
at random. Let's let's see this with this
question mark here.
So this is just selecting one of these
four states, uh, at random.
And the goal is to make a clone.
So this is Dolly the sheep.
That's that's we know how to clone sheep.
And the goal of this task here is to
clone an unknown quantum state,
will take an unknown quantum state, try
to come up with a machine that makes a
perfect copy, a perfect clone out
of this state.
Now, it turns out that quantum mechanics
does not allow us to do that.
So given whatever we can do by quantum
mechanics, measurements, unitary
operations, whatever, we will not be
able to do this. So there exists no
cloning machine.
And this is the no cloning theorem.
And the proof of it is actually pretty
easy.
You can do that after, say, two hours of
linear algebra, because it turns out that
copying this operation here is simply
a nonlinear operation and
you're only allowed linear operations by
quantum mechanics.
So it's it's really pretty easy to prove
that in two lines if, you know, like
how to formalize this properly,
um, and somehow intuitively,
like you're forbidden to make a copy,
but you're forbidden by law, by by nature
to make a perfect copy out of a state.
So this is already a bit like
cryptography. You know, you should be
able to use this in order to kind of
secure information.
And indeed, that's what we can do.
So two clever people,
Charlie Bennett and Jill Barça in
back in 84, they came up with this scheme
as quantum key distribution dukedom
scheme between Alice and Bob.
Um, it works like that.
There's a quantum phase where Alice send
some cubits to Bob.
So these are dashed arrows here.
And then they talk classically over an
authenticator channel.
So there's an eavesdropper.
The eavesdropper tries
to kind of listen in on this conversation
and she has full control over the quantum
part of this transmission.
The classical part is authenticated.
That means, um, she's
if she's able to to read to
to hear everything that you're say, but
she's not able to change the messages,
um, in this set up, the goal is to come
up with a key, a classical key.
So these are just the classical bits
string, which is identical for Alice and
Bob, something like that.
And Eve has no clue what it is.
And so whatever she does here, she
will not be able to learn that key.
So this is a key distribution and
protocol. And I'm going to explain in a
second, uh,
how this works and more details.
But this offers a quantum solution to the
key exchange problem.
And the funny thing is kind of that
it does not rely on any computational
assumptions, such as factoring
discrete logarithms, security of
a free etc.
One can mathematically prove that this
scheme is, uh, secure.
Um, and
it's a key exchange, uh, setting.
So it puts players into the starting
position to use symmetric cryptography.
So once you have established you have
established the key, then you can go and
do your favorite task, uh, say
encryption. You can use that one time pad
with that key that you, uh, generated
here.
So in order to put this a little bit in
perspective, I've, uh, created
this slide here.
Um, so the quantum
cryptographic landscape also
naming all the things that have been
covered here.
It is, uh, Congress.
Um, so here on the X axis,
there is the power of the attackers.
So we are considering here efficient
classical attackers and efficient, I
mean, polynomial time.
So attackers that run within
like reasonable time frames,
classical ones or in, uh,
like as opposed to quantum attackers
or, uh, they can use quantum computers,
but still they have to run efficiently.
And then they're, Stefany, last column,
which is called Everlasting Security.
So a term that means that
you're allowed to store whatever
is communicated on the line.
And then later, at some point
in the future, actually, after an
infinite amount of time, you can break it
and therefore all these things will
fail to to a brute force, uh, attack.
So if you look at a yes or Shaar
and then they're pretty confident that
this is secure against sufficient
classical attackers, I mean, there's no
proof for it. But that's what you
believe. People have looked at this, uh,
for long.
They probably also secure against
quantum attackers to make sure that you
use long enough keys and,
uh, in case of hash functions that you
use long enough outputs.
But of course, they will fail against
somebody who is just an infinite amount
of time, and
then if you saw
dance talk and then Antonios talk
yesterday, then their source monster
here. So this is this big red box here
where that will that will come and break
RSA and discreet locks.
So everything basically every public key
crypto system that is currently used on
the Internet will be broken by efficient
quantum attackers, whereas we
are confident that
they resist classical attackers.
And then the area of post quantum crypto
kind of kicks in and tries to fix that.
And coming up with different new
schemes. And this was the topic
of, uh, then Antonya told yesterday,
namely hash based signatures, the
McCauley's encryption scheme maybe
let US based crypto, but
more research needs to be done in order
to be more confident and that
these schemes actually do resist
classical as well as quantum attacks.
Um. Now, what I'm going to talk about
and what my research is about is about
this last, um, column here.
And this is basically
giving like using more technology
on the honest player side.
So it becomes more more difficult,
technically speaking and also money wise,
to implement these things.
For instance, you can use Kadeem, which
we can mathematically prove because we
don't really rely on any computational
assumption that it's secure.
And and what I see as the biggest
advantage of a KUKA system is that
that the attacker actually has to act
while the protocol is running.
So it really has to kind of attack it
at the moment when it's run.
And if it if this attack is not
successful, then from then point on,
whatever key is generated will be secure
forever.
And so, of course, it's interesting to
kind of take this technology, if you
can afford it, if you can somehow
implement it and combine it with,
uh, we say more conventional schemes
to actually get to the best of both
worlds. And that's also how current
implementations do with.
All right, so let me
explain you in a bit more detail how
how it works.
So in this protocol, in
this BP 84 protocol,
Alice starts off picking
random basis. So she she picks a string
of, say, red, yellow, red,
yellow, yellow at random.
She also picks a random string
of bits, say zero one one one zero.
And then she encodes these bits into that
basis. So we get back this kind of
one of the four states we've seen for
each position that's before.
And that's what Ali sends over the
quantum channel to Bob.
Now, Bob, he has no clue what these
callers are. He cannot see that from the
Cubists that he receives.
And so he has no idea what the basis is
that Alice was actually using.
And what he's going to do is just pick
another random basis.
So he picks another basis at random.
So yellow, red, red, yellow, yellow
and measures in that basis.
So he doesn't need to store anything.
You can just do this beforehand and as
soon as the arrives, he can then measure
immediately.
So it turns out if he was lucky and
he picked the right basis, well then he
will also recover the right bit
that we have seen how that works.
If you will happen to measure in the
wrong basis for you a yellow cubitt in
the red basis, well, then you just get
the random bit, which might agree
with what Alice had in mind, but it also
might not.
So we don't know.
So how to get kind of solve
this problem? Well, Alice is going to
classically tell Bob, say, look
here, this is the string of basis that
I was using, say, a red, yellow,
red, yellow, yellow.
And now Bob knows very actually measured
correctly. And also he says, oh, yeah,
these first two positions, they were no
good. I measured them in the wrong basis.
So let's throw the results away
and just keep the rest very measured in
the rest in a correct basis.
So you also has to tell Alice about that.
So classically, again, he can tell Alice,
hey, let's throw away the first two
positions. I didn't measure there
correctly, so let's just throw those out,
OK? And what remains, they basically
have ASCII.
So that becomes the key that they're
sharing.
But wait a second.
It's it's not that easy after all,
there's the eavesdropper.
So, as I said, the
eavesdropper has full control over
this quantum communication here.
And that means that, well,
luckily, we kind of try to use
this no cloning theorem because,
um, well, if doesn't know the basis
either all for her.
It just looks like one of these four
states picked at random.
And we've seen that the no cloning
theorem actually forbids her to make a
perfect copy out of the classically.
You could just copy everything that flies
by on the line and you would be exactly
in the same position as Bob is,
however, a quantum leap.
It's not that easy because you cannot
simply make a copy.
And therefore, that's the tricky
part. The honest players, Alison.
But they can actually test whether
somebody has interfered because you can
try to make a copy.
But we have seen kind of measuring
observing a state actually changes the
state and therefore
there's a kind of a trade off.
The more she tries to learn about the
state, the more she will actually
interfere with it.
And therefore, there will be errors in
that remaining part here.
And so in an additional step in the
protocol, the allies involved, they're
going to check classically how many
errors approximately are in the remaining
in the remaining string.
They will correct for that.
They just use classical error, correcting
codes, and then they do another step
called privacy amplification to basically
hash it down to something smaller.
And all this together will actually make
sure that so they might have to sacrifice
some more positions.
They might have to have to apply some
additional operations, but they
eventually end up with a smaller key
about which we can guarantee we can
actually mathematically prove that if
doesn't know anything about it.
So in order to do this,
this is really pretty tricky.
So mathematically speaking, you actually
have to follow your whole course about
quantum information theory in order to
give a mathematically sound proof
of this statement that I just outlined
here.
But intuitively, yeah, it's
not that hard to to grasp.
All right, so.
I guess I kind of showed with this
device, this is something that we can
actually do, the honest players, they
only need to generate some photons,
polarize them. I've done it over there
and Bob just needs to measure them upon
the reception. So it's technically
feasible. We don't need any quantum
computer. Well, it might, but we don't
care. I mean, we only care about the
honest players.
We only need quantum communication.
And in fact, this company that is
producing these random number generators,
it's not a coincidence.
They also produce quantum key
distribution devices like this one over
here. So that's something that you can
actually go into a store or a Web store
and buy it. It's pretty expensive.
Um, however,
these devices are out there and that
means that they could also be hacked.
So he could just go and, like, open this
thing up. It will look like that inside
the older, an older model.
But this this kind of rec standard
rec sized black boxes
that are connected by some optical fiber
and, um, well, commercially
available, that means there's also people
who actually hack them.
So this is a picture of Musharraf
is originally from Russia now at the
University of Waterloo.
He runs a quantum hacking lab
and he has opened. So this picture is
done by him. He's opened these devices
and also the random number generator,
of course. And here's a little picture of
him, um, actually
at, uh, at the camp
in the Netherlands at HA hacking at
random in 2009, where
he brought his little suitcase.
Well, little his
eavesdropping suitcase that allowed
him to actually hack commercially
available, uh, security systems.
I don't want to know how he got through
customs with that, but he actually
managed he
has lots of stories to tell about this.
OK, so
that's kind of the state of the
art of, uh, of of quantum key
distribution.
And, um,
yeah, I think I'm approaching
the, uh, the last part of my talk.
So I'd like to come back to this
question. Remember the question.
The moon, yeah, how can you actually
prove that you are at a certain location?
So let's see.
Um.
Well, normally, um,
cryptographic players
and that's perfect, theoretically, very
theoretical world.
They use credentials, cryptographic
credentials, such as,
say, secret information, a password or a
secret key that you store in some safe
place or say
authenticated information like a passport
or biometric features like a fingerprint
or iris scan, something that
distinguishes you from
the rest of the crowd in this in
his audience.
Um, the question I would like to ask
here is, can the geographical location
of a player be used as such a
cryptographic credential?
So is it possible to use just
the fact that I'm on the stage and
almost nobody else is?
Um.
Can that kind of distinguish me from
from all of you?
First of all, it sounds like a bit bit of
a strange question, but if you imagine
the idea and the setting of a bank
where you just walk in and you see some
person behind the counter that you've
never met before, just the fact that
this person is standing behind the
counter kind of makes you trust this
person with all your financial
details.
No, it's of course, the bank has made
sure that only trustworthy people
hopefully are actually behind the
counter.
But nevertheless, it's kind of the place
where this person is that
that makes a difference.
Maybe other applications,
if you are able to answer this question,
is like, um, uh,
why have you ever been to the moon?
Are you actually on the moon, for
instance, or seen a military context?
You want to make sure that I launch a
missile command actually comes from
within your military headquarters and not
from some nearby terrorist cell.
Um, maybe in the setting of this
Congress, you want to broadcast the
message and you want to make sure that
only at one particular assembly it can
actually be threat.
Wouldn't that be fun?
Um, maybe you can
try to kind of avoid this so-called
pizza delivery problem or avoid
making fake calls to emergency services
like this poor guy over here
who has been swatted by
by some fellow gamers.
And more many more so like try
to think of some nice applications and
let me know if you come up with them.
So let's try to do this.
And of course, so this now something
happens that we that we always do.
If you kind of cook up a new question,
the abstract away, all the the
noisy details, and you kind of try
to simplify our world as much as
possible. And we studied a very basic
task of position verification.
Additionally, I'm going to assume that
everybody involved lives in one dimension
just on this line here.
Of course, that's not realistic.
Actually, we live in two, maybe three,
maybe four days.
But for now, just assume that everybody
lives on this line. We have to verifiers
and we have some approver in the middle
and approver would like to convince the
verifiers that she is at this particular
blue line here
and this is a publicly known place.
So everybody knows why this blue line is.
And what we want to make sure is that
no coalition of fake approvers
and I'm going to call fake approvers all
everybody that is not at this blue line
to verify her. So, for instance, evil
is an evil volp even
even if they collaborate, they shouldn't
be able to convince the verifiers that
one of them is at this blue line.
That's going to be the task I want I want
to solve.
And even
more unrealistically, I'm going to assume
I make a lot of oversimplifying
assumptions, for instance, that
communication between the players is
going to happen at the speed of light.
It's actually not true in reality, no.
If you said even if you send information
through optical fibers, it travels
at less than the speed of
light.
I'm also assuming that
actually computation is instantaneous,
doesn't take any time to compute
anything.
Of course, that's also not true.
And I assume some back channels for the
verifiers that somehow they can
coordinate their actions.
This is less of a point.
OK, let's try this.
Let's try like that.
So the first strike goes as follows.
Let's say time goes downwards
and we have to. Following protocol,
Verifier one picks a random
NUNC some some random string X
and then started approver the proof very
simply asked in a protocol to return that
string X back to the verifier.
And the verifier measures the time it
takes for the string to come back.
Well, this technique is called
distance pounding because it allows
you to upper bound how far away
to prove arrays from this verifier.
Imagine if the approver is further away,
then it will take this message longer to
get to the proofer and also longer to
return. So if you know when the message
arrives and if it's the original message,
then you can somehow put an upper bound
on how far the proof is away.
And so if you do this also from the other
side, let's say we choose another random
string Y and let the proofer return
it over there again, we will measure
the time it takes.
Then hopefully you are able to verify
that somebody is at this blueline.
So let's try to break this setting up
our evil ellyson evil Bob.
And actually it's not very hard to break
this protocol because
what they can do is Alice can intercept
this classical message X and they know
where this blueline is, so they know when
the honest proofer would return it.
So it just waits for the right amount of
time and returns that message back
to the verifier after that, that amount
of time. And BOPE does the same thing.
Intercepts, while you wait a little sense
that backed away until the verifiers.
This looks exactly as if somebody
has been at this blueline.
So they cannot distinguish this situation
of the attackers from the situation where
there is an honest, proven Atapattu
point.
So they completely break this protocol.
It doesn't work.
Let's have a second try something more
clever. Let's send this X and Y
still classical inputs
so that they arrive at the same time
at the proofer and let the proofer
compute some function on these inputs.
Let's say they want to see the proof
is supposed to check whether X equals
Y, let's say is equal to be and
it's equal to the bit that says whether X
is equal to Y or not,
then the.
But it can be an arbitrary function that
is easy to compute. So then the results
would have to be sent back to the
verifiers, the verifiers.
They would check the time it takes for
the for the messages to come back.
So, uh, computing doesn't take any
time. That's what we have assumed.
We know how fast the messages travel.
So hopefully that will that'll work.
Let's try to break it.
So let's set up Alice and
Bob now.
What do they have to do?
Yeah, suspense, so
Alice can intercept
this X, you can make a copy
out of it. It's classical string so you
can keep you can keep a
copy for herself. You can send another
copy over to Bob and Bob.
You can do the same thing.
You can takes this. Why keeps a copy
for herself. Sends another one over here
and now just in time,
they both have X and Y and they just go
along and basically compute the function
themselves. So this is a publicly known
function, say a quality function.
Alice can check whether X equals Y
and send that outcome in time
back to the verifier and Bob will do the
same.
So again, complete break of the protocol.
It doesn't work.
However, if he and in fact, turns
out this is a generic problem, actually
no protocol for a classical
position. Verification in the setting
will work. So these people here have
shown, I should say all
these references are actually hyperlinks.
If you download the slides, you can click
on them and it will take you to the
research paper, which shows that actually
this is a generic problem.
So you can never have any classical
protocol that is secure in this sense.
And this holds not only in
one dimension, but in arbitrary
dimensions, because simply can set up
attackers between the claimed position
and the verifiers.
They intercept everything that comes
along and forward it to their fellow
cheaters and they will be able to run the
same function as the honest proofer is
supposed to run and thereby
making it look to the verifiers if
somebody was there.
So this doesn't work.
However, if you look at the attack, so
that's what they're doing now.
They're kind of taking a copy of this X
and share it with their fellow cheater
and then compute the function themselves.
This involves copying
classical information.
And of course, we have seen quantum
no cloning theorem, so.
Turns out that maybe you should
use quantum information and we should
make it hard, make it should make
it impossible for Alice and Bob to
to do this copying operation.
So here we go. Let's try that and
let's have the following protocol.
And the first verifier sends,
say, a random Cupitt to this
question. Where can we see one of these
four quantum states we've seen before
since that were a quantum channel to the
proofer and timet
in the way that it arrives?
At the same time at Approver, the other
verifier sends a classical bit, just one
bit zero one.
If the bid is zero, then Approver
is supposed to send it back to the first
verifier.
Just put the mirror now and then it will
be reflected back to the twenty first
verifier again.
Will we'll measure the time will make
sure it is the original Cubitt that was
sent. Well let's assume that that's not
a problem then.
If the bid is what I'm supposed to do,
nothing. Just let it pass through
and kind of let it fly to the other
verifier over here.
So that's the protocol I want to look at
and let's try to break it,
so here is the game that we have to
play as as attackers, at
least as a Cubitt Volp, as a classical
bit. And if the bid is zero, at
least needs to end up with the cubitt.
If the bid is one, Bob needs to end
it. So, Bob, just as classical
information, he can do the same thing as
before. He can make a copy out of his bid
to keep one for himself forward, one for
the other side.
But at least she's in trouble
now because of the no cloning theorem.
She has to kind of try
to make a copy here, but she cannot do
it. You no calling theorem.
She's kind of by the time constraints,
she's forced to make up her mind right
now, right here at this point.
But she doesn't know yet whether to be
desirable or to be this one because it
takes some time for this information to
travel over here.
So she could of course, you could guess
she could say, well, the rate is probably
zero. I keep to keep it for myself and
half of the time she'll be lucky and she
can send the Cuban back.
But the other half, she she doesn't have
it. She she she
needs the cubitt and it's too late to
send, you know, it would arrive too late
so the other verifier wouldn't notice.
So it looks like,
uh, this is this is secure
because there is some certain probability
that things will go wrong.
There's a there's a non-zero probability
that the verifiers can distinguish
this situation of the attackers
from the one that, um, the
with an honest proof in the middle who
will always succeed.
Oh, it was very easy to run this
protocol. And honestly, he could just
put them mirror or not, and he will
always succeed. So there's a gap between
these two probabilities. So if you repeat
it a thousand times, a million times,
then at some point very quickly, actually
the verifiers will see a difference
between this setting and the other set.
So that would actually prove security.
That's what we thought.
Turns out it's not true,
actually. You can break this protocol
and you can even break it perfectly.
So this was quite this was quite a blow.
I mean, we thought now that that cannot
be. And in order to understand
how to break this protocol, I need to
explain it to more things.
I need to explain to you what
EPR pairs are because they need
kind of a magic resource element, Bob,
in order to do that.
And so if you are pairs, they
are named after these three very famous
physicist Einstein Podolsky Rosann,
and they come in pairs.
That's why they're called pairs and
they somehow haven't made up what they
want to be. So there's all these arrows
here. Somehow it's it's kind
of a mixed state and there's this magic
glow between them.
So they are in a very interesting special
state. They're entangled.
So these are entangled cubits for
strength.
And it's possible to generate
them so at least, for instance, can
generate them.
Can keep them for himself, Popken she
can give the other one to Toubab and in
fact, they can be very far away from each
other. So they may be generated at the
same place, but then Bob can take it with
him or say send it over some optical
fiber. It can be hundreds of kilometers
away. However, they are still entangled.
And what that means is that, for
instance, if Alice goes and measures her
Cubitt saying a computational basis,
then because this guy hasn't really
decided yet what he wants to be, he will
actually get the random outcome.
It's probably one half. You're going to
get a zero and you collapse the state or
the zero state. And with probability one
half, Alice will get one and she will
collapse the state or one.
But the funny thing is that
simultaneously she obtains
her measurement outcome.
This state also collapses
on bombsite.
And so this is kind of the epic magic.
So this is kind of the funny thing
of this of these quantum states.
And this is what Einstein called spooky
after Fennville.
Spooky action at a distance.
And he didn't like that.
So what that means is, for instance, if
Alice observes a zero and
the zero state and bombsight is also
zero, state means if he goes and measures
it again in the computational basis,
he will now get probabilities with
probability. One, he will get the outcome
zero. He will get observe the same bit
as early stage before.
So to Einstein is looked like
that's no good because that seems to
contradict my theory of relativity.
However, it's actually not true.
So I didn't quite understand.
But this EPR pairs, they do not
allow to communicate information.
So it's a difference whether so here
they allow it allows them to get
a shared random bit because when Alice
measures, she will get random bit
and Bob, when he measures, he will also
get the same random bit.
It's just a shared classical random
bit. It's not information that Alice
had in mind.
Say I'm on a Zenda zero two bob, because
once he does a measurement, the outcome
will be random.
And that's the difference between sending
information from Alice to Bob
to just creating some some
shared, uh, correlation.
Now, probably this is hard
to grasp and don't worry, very
smart people had trouble with that.
So if you see this for the first time and
relax. So
it's OK.
Um.
If you have this, then
we can actually do quantum teleportation,
so we're not going to do the Star
Trek version. We're going to do the
version that was cooked up by these
people over here, um,
actually a long time ago in 93.
It works as follows.
So let's say Alice and Bob
and they have such an epic pair.
Actually, this has been demonstrated
many, many times experimentally.
So this is something that can actually
do.
Um, they share any power parity,
might be far away from each other.
And on top of that, Alice has an unknown
cubitt.
And that cubitt this committee over here
and this unknown state that she doesn't
know she would like to teleport Bob.
So she would like this Cubitt to end up
on bombsite.
Now, what she can do is she can do a
kind of complicated measurement that I
haven't talked about on her two cubits.
So she will do a so-called BELAL
measurement.
And this is a measurement on two cubits.
It's the half of the EPA that she
shares with Bob together with a cubit
that she wants to teleport.
The outcome of this measurement is again
going to be classical, classical to
random bits, actually random bits.
So they say zero one,
two or three.
And magically,
because of the entanglement this
Stateville, this, it will appear
on bombsite. However, it will not appear
in the clear. It will appear in some
encrypted form.
Actually, this is the analogous to the
classical one time pad exploring
with a random bit.
This is actually the quantum one time pad
because it's actually explored in a
quantum way with two classical bits,
because if ellis'
since this classical outcome sigma
over to, then he's able to
unlock this encryption and actually
recover the original cubitt.
So this is the procedure, how quantum
teleportation works, you have to do what
you have to have an prepare, you have to
do a belt measurement, you get a
classical outcome.
That outcome needs to be sent to the
other person. And once you know that you
can undo the encryption of the state in
order to recover this original Cupitt
here.
And again, this is something that does
not contradict relativity theory.
So this this kind of collapses, doesn't
happen instantaneously.
You can only recover this Cubitt after
you've learned the classical information.
And so it takes some time for this
classical information to travel from
Alice to Bob. No, if they're far apart.
And so there's there's no information
going faster than the speed of light
because you have to wait for the signal
before you actually get to the states.
That was in Alice's hand before.
All right, so now with that attempt, we
can break our protocol, remember
what it was, the attack I
always had a cubitt Bob had a bit to the
cubit should end up at Alice's side.
If it was zero, if this bit was one that
Bob should end up with a cubitt, and
if they share entanglement, if they
share, say, to EPR pairs like
this and and why wouldn't they know
they could just go and prepare that
beforehand, then they can
actually perfectly break this protocol
because what they can do is
teleportation.
So here here we go.
Alice would do a teleportation
measurement, a bell measurement on the
cubitt that she holds together with
the first half of of one of the EPR
pairs. This will teleports
this and Cubitt over
here to Bob.
Now, actually, it will not be here in the
clear. It will be encrypted.
But these keys, you'd be able to send
these classical keys along here.
And Bob, Bobby has
to beat. He knows whether he should keep
the cubitt or not.
So if the bit is one, he will just not do
anything and wait for his keys to arrive
and uncover this.
Cupitt so then he will hold the right
Cupitt.
However if the bit the zero
then he will actually teleport it back to
Aliceville. Just do another teleportation
measurement and kind of make
this cubitt now end up again on
Alice's side.
So it's at the right place now.
It's kind of double encrypted, it's
encrypted by this measurement and by that
measurement. But again, there's time
for this classical information to travel.
So he would send along the
and he would send along the outcome of
this this measurement.
And then Alice, at this point, she learns
o be zero.
So I have to look at my second Cubitt
here and I have to undo this
measurement here that what that did
to uncover and then I have to undo my own
measurement that I did.
And I will end up with the correct
cubitt.
So.
Here, are you actually perfectly break
the protocol because again,
to the verifiers, it's going to look as
if somebody is in the middle,
so.
Well, are there actually
protocols that cannot be broken and this
is kind of one of the main results we
obtained in this research
area. In fact, there is no secure
protocol. So what we've showed is the
so-called no go theorem that we've done
back in 2010, that any
position verification protocol, even if
it's a quantum protocol, it can be broken
using a huge number of entangled
qubits. So if you have enough resources,
an exponential and the amount of
resources, then you can break any
of these position verification protocols.
However, as always, in science,
if you kind of answer a question
and you prove a theorem, it immediately
leads to new questions.
And it's here. The obvious question is,
well, do you really need that many
resources or is there a protocol
such that it's easy to run if you're
honest, so honest approvers and verifiers
are efficient or they just need to do
simple things, but very can guarantee
that any attack on it requires
a lot of entanglement.
But that would be great.
Then then we actually have a secure
protocol.
And this is this is actually a research
question that I'm currently, uh,
studying.
And I invite you to have a look at
my home page and for some reason,
developments in this in this area.
I think that brings me to the end.
I hope you've learned something in this
talk.
First of all, about quantum mechanics.
What cubits are these four states?
You've seen the no cloning theorem.
You've encountered some funny
in your resource state
that cubits that are entangled
and you've seen how to use them and
to to do teleportation
in the first application.
I've talked about quantum key
distribution and try to give you a little
bit of context how where it fits
in the world.
And in second part, as I've talked about,
position based cryptography in one of
the currently active research areas
where it depends whether you can break
the protocol if you have enough
resources and maybe you cannot if
you don't have enough resources.
All right. Thank you very much for your
attention and.
We now have some
minutes left for Q&A, so please
line up at the microphones.
This is an exceedingly well miked room.
So you have eight microphones to choose
from. Just line up at any one
of them and I will call you when you can
speak.
Yeah, and please try not to walk in front
of the cameras when you leave.
This is very annoying for the people on
the street and also the people in
the stream. If you're on the icy channel
on Twitter, you can just ask questions
there. We do have an Internet person
here that will read your questions.
Microphone number two, please.
Hello.
Yeah, thanks for the talk.
And and but
I have one question concerning
the quantum key distribution
using Wiggill machines.
And and you said they could
be hacked. And from my understanding
and clarification, I assume that
this hacking does not take place
at the quantum part of this
process, but it takes place at the
specific implementation
and and the classic
channels. Is that, too?
Yes, of course.
So with any system you implement,
even if you can show security,
improve security, in our perfect
mathematical model, we have to make
sure that we actually model the reality.
And in reality, things are way more
complicated. You have to use photon
detectors. And in fact, in this
particular case, it was the the
photon detectors that were attacked.
So you were the most able
to actually blind them by shining
in a lot of light.
So they are very sensitive.
They normally operate on a single photon
level and and thereby kind
of getting out of the model that we
that we use to improve security.
So so it's it's really an attack on the
on the actual implementation.
But in fact, maybe I can say in general
that I see this as a sign of maturity
of this field. I mean, that's the only
way to go. No, somebody has to build the
machine. Then somebody comes and attacks
it. And kind of it's a cycle.
And so so things get better by
by investigating actual implementations.
Thanks.
Just a quick note to the people leaving
right now. This talk is going on for like
three more minutes. So please just wait
three more minutes and stop being very
annoying to everybody.
Thank you.
Internet, please.
Thank you. First question, is there
anything you can do at home with limited
budget?
Well, you can definitely run this
little experiments that I did actually
can have a lot of fun with polarizing,
glassless in general and, um,
but say of
real cryptographic relevance, that's
going to be way harder because you do in
order for these security proofs to kick
in, you do have to operate on a single
photon level.
And this is this is very delicate
to handle. So you do need some photonic
slap in order to do that.
Microphone number one, please.
So one comment because you were
commenting on our talk from yesterday,
the post one talk, I mean, if
you are using yes.
Or if you're using any authentication
code, you are back to
computational assumptions, hardens
assumptions. So when you had two of
your table, you are still claiming you
have infinite long term security
while at the same time you're combining.
And that's just not true.
The other comment I have is,
so how about my mobile communications?
How about the most common use of Internet
via Wi-Fi?
OK, um,
so you're
concerning your first question, I think
we should take this offline.
I mean, I'm happy to explain to you
your second comment, of course.
So in that sense,
this research is not and
I'm assuming a very strong model for this
position of verification where basically,
as I said, I call kind of fake proofers,
all those that are not at this claim
position and they can even it can be even
coalitions. So in that sense, it's not
realistically modeling
a real world scenario.
Into the McLeese, I'm speaking to
Mark, I'm not talking about the second
part, I'm talking about like, what would
you give me for the normal tripto
application? OK, mobile phone wi.
OK, well, as you know,
it's quite a high
demand, say, on the hardware side
that you have to have in order to run
this protocol.
Of course, there's also a lot of efforts
to actually miniaturize those devices
so that maybe at least one part is
actually portable
a sense.
And the yeah, the best
kind of add-on that you
can offer is this everlasting security
that you have to kind of be
active attacking, actively
attacking at the point of execution.
And if you are not successful in that,
then then actually the rest of
the time the security will be guaranteed.
So I will have lasers.
Sorry, we have lots of people queuing.
Please discuss later.
Thank you.
Microphone for please.
And correct me if I'm wrong, but
you need a direct line for
this kind of thing to work, right.
So if you have any routers
or something in between and it won't work
because you need to read it out
or make a copy.
I'm just clarifying.
Are you talking about the second part or
the first part of both?
I think, um, well, for
quantum key distribution, that doesn't
matter too much. So you're perfectly fine
routing your cables around corners
using optical fibers.
For the second part, it's actually kind
of crucial. You're right.
So it's all about timing there.
So, of course, you have to
consider more realistic settings.
Also the fact that you are not we are not
communicating at the speed of light.
This will add additional constraints.
And so it will way more work
is required to model, say, a more
realistic setting where you might not
have a straight line of sight, very, very
communication. Ashley has to take some
corners. And so you might end up not
with one particular position you can
verify, but with the whole interval
somewhere you can make sure that somebody
is so.
But these are things that we are
currently working on to make to
to to model things more realistically.
Mike, number two, please.
Um, hello.
Uh, I think Tanya had a similar question,
but, uh, you said you have no
computational assumptions for Cookie,
but you need this authenticated RNA
and the authenticated RNA.
You do it with classic crypto, with
either an H mag or RSA signature.
So you have the computational
assumption again.
So I think this whole thing is kind
of circular.
You're trying to replace, uh,
whatever and a cipher.
But you, again, need some,
uh, maybe a
hash function or some signature from
traditional crypto to make
it work in the first place.
So I think it's a very
expensive solution for a non-existent
problem.
OK, um, well, so
in fact, you don't need to use a
computational scheme to to do
authentication or information,
theoretically secure authentication
schemes. But, um,
uh, you're right that, uh,
you're using up this key.
So in a sense, also what you can never
prevent is that it just completely blocks
all the communication.
And in that sense, you will she will be
able to kind of make you run out of key.
But what it does add is
that that, uh, this this
feature that I already told Tarnya,
namely that that you have to be active at
the moment of execution.
So this this is kind of the upgrade
to, say, classical schemes.
Unfortunately, we are out of time, so
please thank Christian again.
Thank you.