WEBVTT
00:00:00.000 --> 00:00:25.280
36C3 preroll music
Applause
00:00:25.280 --> 00:00:30.369
naehrwert: Yeah. Thank you for the
audience and thanks that you came. Thanks
00:00:30.369 --> 00:00:34.530
for the Congress for giving me the
opportunity to be here tonight, to be able
00:00:34.530 --> 00:00:39.880
to tell you a bit about post quantum
cryptography, a bit about as isogenies. I
00:00:39.880 --> 00:00:44.390
mean, just educate the people a bit about
what that means, even, because I'm not too
00:00:44.390 --> 00:00:52.500
sure how many of you heard about that
before. Yeah, let's just jump right in. So
00:00:52.500 --> 00:00:57.410
my day job is being a mathematics PhD
student at an undisclosed university. You
00:00:57.410 --> 00:01:03.320
can ask me in private if you're
interested. So previously I did physics. I
00:01:03.320 --> 00:01:07.450
was also or maybe I'm still a bit active
in the console hacking scene. And if
00:01:07.450 --> 00:01:12.320
you're interested about that shameless
plug, you can find us at Nintenbros
00:01:12.320 --> 00:01:17.220
Assembly later. You can ask us all about
our somehow console hacking endeavors. But
00:01:17.220 --> 00:01:24.220
enough about that. So I brought you some
pictures, screenshots of websites. So I
00:01:24.220 --> 00:01:28.670
don't know if you have seen the chatter on
social media and the blogs here recently
00:01:28.670 --> 00:01:36.210
about that Google paper on quantum
supremacy. So there is a Nature article
00:01:36.210 --> 00:01:42.280
about that beyond quantum supremacy. And
there is a Verge article that Google
00:01:42.280 --> 00:01:47.701
confirms quantum supremacy and
breakthrough, whatever that means. There
00:01:47.701 --> 00:01:52.020
is Google's own blog post about it. Notice
there are always these shiny pictures of
00:01:52.020 --> 00:01:57.909
these huge tubs filled with helium where
they house these quantum computers. So
00:01:57.909 --> 00:02:04.079
supremacy means the state or condition of
being superior to all others in authority,
00:02:04.079 --> 00:02:11.129
power, or status. So calling something
quantum supremacy, I mean, that screams
00:02:11.129 --> 00:02:16.420
something being pretty amazing. But what
actually does this mean for us? What does
00:02:16.420 --> 00:02:22.980
it mean for cryptography? And I think I
can relieve you all about from from maybe
00:02:22.980 --> 00:02:29.290
some fears that you had for us in
practice. Maybe today it doesn't really
00:02:29.290 --> 00:02:36.230
mean anything yet. So for cryptography
none of our underlying assumptions,
00:02:36.230 --> 00:02:40.601
whatever it means for now, are being
actively broken yet as we know or that we
00:02:40.601 --> 00:02:46.910
know of. But in theory, they are broken.
Okay. And because they're only broken in
00:02:46.910 --> 00:02:50.349
theory, that's pretty good. So we can
still blame the designers and implementers
00:02:50.349 --> 00:02:57.080
of whatever we cook up for when things go
wrong. So that's nice, too. But as I
00:02:57.080 --> 00:03:01.970
already wrote in the abstract a bit for
this talk, we should be, somehow, better
00:03:01.970 --> 00:03:06.980
be safe than sorry. So instead of somehow
waiting until the point of where quantum
00:03:06.980 --> 00:03:11.060
computers somehow become feasible to break
our cryptography, we should probably
00:03:11.060 --> 00:03:16.069
research it today. It's a bit with the
climate change, right? Suppose it's right
00:03:16.069 --> 00:03:19.500
to save our climate today instead of
waiting until it's too late. So if we're
00:03:19.500 --> 00:03:24.900
going to be reborn to do the same for
cryptography. There are also three
00:03:24.900 --> 00:03:30.920
upcoming talks I want to advertise here a
bit. I think I don't remember the days,
00:03:30.920 --> 00:03:34.519
but descriptions look pretty interesting.
So I'm going to leave that up for a few
00:03:34.519 --> 00:03:38.870
seconds. There is one called Provable
Insecurity, one called Cryptography
00:03:38.870 --> 00:03:42.819
Demystified and one about high assurance
cryptography software. I'm sure this is
00:03:42.819 --> 00:03:48.590
gonna be interesting. Okay, let's return
back to what I want to talk about. So
00:03:48.590 --> 00:03:53.810
there's something I chucklingly call the
Post-Quantum Cryptography Zoo. There are a
00:03:53.810 --> 00:03:57.780
few buzzwords up there. You don't really
have to know what they mean. I'm just
00:03:57.780 --> 00:04:01.600
going to say them out loud. Lattices,
codes, multivariate polynomial systems.
00:04:01.600 --> 00:04:07.310
That's also a bit of a mouthful. And hash
based cryptography. And there is the one
00:04:07.310 --> 00:04:11.760
that I want to briefly talk about tonight
called supersingular elliptic curve
00:04:11.760 --> 00:04:16.199
isogenies. OK, so this is the stuff that I
really like. Isogenies, they are great.
00:04:16.199 --> 00:04:21.970
And now I'm going to tell you why they're
so great. All right. So I don't know how
00:04:21.970 --> 00:04:26.369
many of you have a mathematics background.
Maybe I can do a test. Can people raise
00:04:26.369 --> 00:04:32.879
their hands where if they have some formal
training in, say, algebra? Yeah. Okay. So
00:04:32.879 --> 00:04:37.759
that's pretty good. So I'm just gonna tell
you some something about it. There are
00:04:37.759 --> 00:04:42.580
decimal numbers. This is Pi. Then there
are rational numbers somehow the are, one
00:04:42.580 --> 00:04:46.339
half, one third and so on and so forth.
Then there are integers from minus
00:04:46.339 --> 00:04:52.889
infinity to plus infinity and they follow
nice whole steps. But for working with
00:04:52.889 --> 00:04:56.619
those numbers and for cryptography, we
want something that's nicer behaved. We
00:04:56.619 --> 00:05:01.499
want somehow a finite set. OK. So this is
just important for implementation. And the
00:05:01.499 --> 00:05:05.350
ones that we want to work with, I'm just
going to remind you, are the integers
00:05:05.350 --> 00:05:11.620
modulo N, so we take some positive integer
N, big N, and then we consider the set
00:05:11.620 --> 00:05:16.599
from zero to N minus one. Okay. And these
numbers do follow certain addition and
00:05:16.599 --> 00:05:20.249
multiplication rules and it pretty much
works like a clock face. OK. I chose N is
00:05:20.249 --> 00:05:24.569
12 here and, just bear with me, imagine my
clock face goes from zero to eleven
00:05:24.569 --> 00:05:28.930
instead of from one to twelve. But it's
really the same. For example, if I tried
00:05:28.930 --> 00:05:35.240
to add ten to five. OK, I start from ten.
I go two steps and then I arrive at zero.
00:05:35.240 --> 00:05:38.789
This is where my clock ticks over. Right.
Like on a real clock. And then you go
00:05:38.789 --> 00:05:44.129
three more steps. And so ten plus five mod
twelve is three. So it's numbers that kind
00:05:44.129 --> 00:05:49.550
of behave this way. Think of addition on
on a clock face. And for the computer
00:05:49.550 --> 00:05:54.530
scientists out there or, I mean, everyone
probably knows about that, for a computer
00:05:54.530 --> 00:05:58.930
they're like the 8 bit integers where N is
2 to the 8. And then these are the numbers
00:05:58.930 --> 00:06:03.669
from 0 to 255, and so on and so forth. So
these are the numbers that we want to work
00:06:03.669 --> 00:06:12.719
with. Just to set the stage a bit. And
these isogenies. We will live in a world
00:06:12.719 --> 00:06:18.020
where we we work with somehow related
numbers to these integers mod N. And now
00:06:18.020 --> 00:06:25.249
for big N, we choose a prime P and then
these integers mod P, they represent what
00:06:25.249 --> 00:06:30.689
we call the finite field with P elements.
Okay. And you can think of this as a set
00:06:30.689 --> 00:06:35.929
that has exactly P elements and really
kind of behaves like the real numbers.
00:06:35.929 --> 00:06:39.020
Okay. You can add numbers, you can
subtract numbers. You can divide by
00:06:39.020 --> 00:06:42.919
everything but zero. Okay. And this finite
field with P elements works really the
00:06:42.919 --> 00:06:46.839
same. It's just a finite set, but
everything is invertable except zero.
00:06:46.839 --> 00:06:50.199
Okay. And these are the numbers that we
want to work with and computers can do
00:06:50.199 --> 00:06:56.509
that. So that's fine. And just for the
sake of telling you, there are also fields
00:06:56.509 --> 00:07:02.999
that have somehow P to the R elements, but
they are not the same as what people are.
00:07:02.999 --> 00:07:06.479
Okay. But there is a way to construct it.
But that's all you need to know about. So
00:07:06.479 --> 00:07:09.930
this is really the set of numbers that
we're going to work over and that that's
00:07:09.930 --> 00:07:15.580
all you need to know. Okay. So the
cryptographic problem that I want to focus
00:07:15.580 --> 00:07:20.149
on this talk is simple key exchange. I'm
not gonna talk about signatures, I'm not
00:07:20.149 --> 00:07:23.639
going to talk about encryption, nothing.
Let's just focus on this one simple
00:07:23.639 --> 00:07:29.529
problem of how do Alice and Bob exchange a
key without anyone else somehow getting
00:07:29.529 --> 00:07:33.319
access to that key? And I mean, there are
somehow classical solutions to that. I
00:07:33.319 --> 00:07:37.050
could put my key in a suitcase and I could
bring it to Alice or I could somehow pay
00:07:37.050 --> 00:07:41.380
someone to bring the suitcase to Alice. Or
maybe people heard about the thing where I
00:07:41.380 --> 00:07:44.830
put my lock on the box and I ship it to
Alice and she puts her lock on the box and
00:07:44.830 --> 00:07:49.009
she ships ships it back now I remove my
lock and I ship it to Alice again. OK, so
00:07:49.009 --> 00:07:53.610
there are countless ways, but we want to
somehow do this in a nice, instantaneous
00:07:53.610 --> 00:07:59.979
kind of way using mathematics. Okay. So
this simple problem is what we're going to
00:07:59.979 --> 00:08:05.949
focus on. And classically (whatever that
means for now) this has been set off by
00:08:05.949 --> 00:08:09.780
Diffie-Hellman. And this is this nice
paper from 1979 the title is New
00:08:09.780 --> 00:08:13.849
Directions in Cryptography. So this
already tells you that something important
00:08:13.849 --> 00:08:20.259
must be going on and what you somehow
invented there was a way to exchange keys
00:08:20.259 --> 00:08:27.179
between two parties using a nice, well-
defined problem. Okay. And how does it
00:08:27.179 --> 00:08:31.539
work? Okay. I'm just gonna tell you how it
works. So there are two parties, Alice and
00:08:31.539 --> 00:08:39.250
Bob. A and B. They agree on a safe prime
modulus, N. Okay. So this is the integers
00:08:39.250 --> 00:08:45.029
mod N, which I saw, and a generator G. So
what does that mean? Basically in my set,
00:08:45.029 --> 00:08:50.160
from zero to N, I want to single out one
element such that every element can be
00:08:50.160 --> 00:08:54.569
written as a power of that element. And
somehow this means it generates it. Right.
00:08:54.569 --> 00:09:00.110
So every Y can be written as G to the X
mod N. Okay, this is my setup. And then
00:09:00.110 --> 00:09:06.250
there is Alice and Bob and they agree on
these two parameters. Okay. And now how do
00:09:06.250 --> 00:09:12.199
we do the key exchange? So it's very
symmetrical. So Alice chooses a random A
00:09:12.199 --> 00:09:17.199
in the set from one to N minus one. And
she sends big A is G to the small a mod N
00:09:17.199 --> 00:09:21.589
to Bob. And as you might have guessed it,
because I said it's symmetrical, Bob does
00:09:21.589 --> 00:09:26.819
the same. Okay. So how does the picture
go? So Alice on the left, she chooses a
00:09:26.819 --> 00:09:33.290
random small A. And she sends that big A
to Bob. Bob chooses a random small B. He
00:09:33.290 --> 00:09:38.120
sends the big B to Alice. And then
somehow, you know, you have to combine
00:09:38.120 --> 00:09:45.080
them somehow. Right. How do you do this?
So this is nice to compute the shared k,
00:09:45.080 --> 00:09:50.550
the shared key. So Alice takes the B, she
got from Bob and raises it to the power of
00:09:50.550 --> 00:09:56.379
her own random secret value. And Bob does
the same. And magically from mathematics,
00:09:56.379 --> 00:10:04.269
they both get the same small k. And now
I'm going to tell you why, somehow, this
00:10:04.269 --> 00:10:11.750
is hard for anyone else to get the same
small k. So now bear with me. I'm gonna
00:10:11.750 --> 00:10:16.120
write it down mathematically, first of
all, why not teach you a bit about that as
00:10:16.120 --> 00:10:21.290
well? So this is this diagram, this
commutative diagram that somehow
00:10:21.290 --> 00:10:24.931
represents this key exchange that just
happened. Okay. So Bob and Alice, they
00:10:24.931 --> 00:10:30.779
both started in the left upper corner with
the G and they both end up in the lower
00:10:30.779 --> 00:10:35.269
right corner, the G the AB. So they both
are able to somehow compute G to the AB
00:10:35.269 --> 00:10:39.089
and no one else is. And how does that
work? Well, Alice will only compute the
00:10:39.089 --> 00:10:43.990
horizontal arrows, so she only raises to
the power of small A because that's her
00:10:43.990 --> 00:10:48.540
random secret that only she knows. And Bob
only computes the vertical arrows, so he
00:10:48.540 --> 00:10:51.800
only raises to the power of small B,
because that's the secret to he knows and
00:10:51.800 --> 00:10:57.490
no one else does. And I mean by the
commutativity and the associativity of
00:10:57.490 --> 00:11:02.819
exponentiation, they just agree on the
same G to the AB which is which is cool.
00:11:02.819 --> 00:11:08.519
And somewhere in there there hides a
problem that we like to call the discrete
00:11:08.519 --> 00:11:13.549
logarithm problem and it just happens for
integers mod N if I choose my N
00:11:13.549 --> 00:11:17.410
appropriately, I'm not gonna tell you how,
but just believe me if I choose it
00:11:17.410 --> 00:11:25.670
appropriately. If I give you Y and G, for
you it's hard to find the small X. Somehow
00:11:25.670 --> 00:11:30.040
like taking a logarithm, and we call it
the discrete logarithm because it's a
00:11:30.040 --> 00:11:33.720
discrete set of numbers instead of the
continuous decimal numbers, what we
00:11:33.720 --> 00:11:37.720
started with was this discrete finite set
of numbers and this DLP is hard. Okay.
00:11:37.720 --> 00:11:44.780
This is a hard problem for classical
computers. And the best classical generic
00:11:44.780 --> 00:11:49.720
algorithm - I'm not gonna talk about
somehow algorithms that specifically
00:11:49.720 --> 00:11:54.889
target integers mod N, I'm just going to
talk about generic algorithms for for this
00:11:54.889 --> 00:11:59.600
DLP problem. The best algorithm somehow
has run time square root of big N the
00:11:59.600 --> 00:12:06.709
number of elements and say I chose my N
about the size of 2 to the small n, or n
00:12:06.709 --> 00:12:13.230
bits. Then solving this takes exponential
time in n, right, because the square root
00:12:13.230 --> 00:12:17.769
of 2 to the n is still pretty big. Okay,
this is about 2 to the n half, and if I
00:12:17.769 --> 00:12:24.980
make n a thousand is still 512 bits. So
this is a hard problem. But recently there
00:12:24.980 --> 00:12:33.540
has been a record for factoring and DLPing
over a seven hundred ninety five bit
00:12:33.540 --> 00:12:39.040
modulus and they use a bit of a better
algorithm, but still, I mean it still took
00:12:39.040 --> 00:12:46.019
them a long time. Okay, so if I remember
correctly, this feed took them 4000 core
00:12:46.019 --> 00:12:51.120
years on a two point one gigahertz
computer. I mean, that's still 4000 core
00:12:51.120 --> 00:12:55.089
years. So this is a long time. Okay. But
as you can see, it's possible to solve
00:12:55.089 --> 00:13:00.410
this. I mean, just put enough, if I have a
big enough hammer, I can solve this. Okay.
00:13:00.410 --> 00:13:05.399
But again, you can make N pretty big,
bigger than anything being able to solve
00:13:05.399 --> 00:13:10.629
this anymore. But. Okay, so there is a
quantum algorithm for this and this is
00:13:10.629 --> 00:13:16.279
this other paper from 95. Peter Shor. So
he thought of this algorithm that solves
00:13:16.279 --> 00:13:21.930
the DLP in polynomial time. Okay, now
remember our big N we took about two to
00:13:21.930 --> 00:13:26.770
the small n. And this Shor's algorithm
only takes small n to the cube? And I
00:13:26.770 --> 00:13:32.730
mean, if N is a hundred hundred cube, it's
not that big. And I can make a thousand by
00:13:32.730 --> 00:13:37.749
a thousand cube is still not that big.
Okay. So there is a good algorithm that
00:13:37.749 --> 00:13:41.519
assumes the existence of a quantum
computer. I mean as outlandish that might
00:13:41.519 --> 00:13:47.600
sound, but still this algorithm in theory
breaks the DLP. Okay. So I don't know,
00:13:47.600 --> 00:13:52.319
maybe in 20 years or 30 years, 100 years.
I don't know personally, but if there is a
00:13:52.319 --> 00:13:56.910
quantum computer eventually that somehow
runs this thing, okay, DLP's broken,
00:13:56.910 --> 00:14:05.350
classically. So. Well, what to do? As I
said, let's just try to come up with
00:14:05.350 --> 00:14:10.899
cryptography for which we don't know a
quantum algorithm. Okay. Or for which we
00:14:10.899 --> 00:14:15.170
expect there won't be a quantum algorithm
ever. There are a few candidates. Again,
00:14:15.170 --> 00:14:21.930
there's this zoo. Lattices, codes, this
long word, and isogenies. Okay. Now what I
00:14:21.930 --> 00:14:26.319
want to tell you about is what is an
isogeny, and how do I do key exchange with
00:14:26.319 --> 00:14:33.970
an isogeny? Okay. Because I know, it's a
fancy word, but what does it mean? Okay.
00:14:33.970 --> 00:14:37.300
There was this other word that started
with elliptic curve isogenies, so probably
00:14:37.300 --> 00:14:40.860
I should tell you about what is an
elliptic curve or give you a reminder if
00:14:40.860 --> 00:14:46.379
you've seen this before. So I look at this
equation in two variables and two
00:14:46.379 --> 00:14:51.529
constants, the variables X and Y, my
constants are A and B. And the equation is
00:14:51.529 --> 00:14:58.160
Y squared is X cubed plus AX plus B. And
now what I want to look at is all the
00:14:58.160 --> 00:15:02.920
solutions to this equation, all the
possible pairs Y and X or X and Y. And of
00:15:02.920 --> 00:15:06.990
course, they're going to look different
somehow for the different possible numbers
00:15:06.990 --> 00:15:11.370
that I can plug in for X and Y. And again,
you might have guessed it, first of all,
00:15:11.370 --> 00:15:14.760
we're going to look at it over the decimal
numbers and then later we want to consider
00:15:14.760 --> 00:15:20.730
this again over our finite field, okay,
because we like we like this discreteness.
00:15:20.730 --> 00:15:25.649
And over R, a simple equation, I just
chose some values for A and B, B I set to
00:15:25.649 --> 00:15:30.790
zero, A I set to 1, uh, A I set to zero, B
I set to one. The solution set looks like
00:15:30.790 --> 00:15:36.519
this. And actually it extends infinitely
far on the right side, up and down. Okay.
00:15:36.519 --> 00:15:41.470
So this is just somehow a snapshot of what
the solution set looks like. But over my
00:15:41.470 --> 00:15:45.540
finite field, and I chose one with one
hundred and one elements, it looks like
00:15:45.540 --> 00:15:50.850
the set of points. Okay. So elliptical
curves look differently over different
00:15:50.850 --> 00:15:57.510
fields. But that's fine. That's fine.
Okay. Now, quick reminder of why people
00:15:57.510 --> 00:16:01.550
like elliptic curves. So there is
something called the point addition law.
00:16:01.550 --> 00:16:05.490
So I can take two points on this curve and
I can somehow add them. Okay, but this is
00:16:05.490 --> 00:16:10.350
not really addition in the sense of
numbers. There is somehow a law that I have
00:16:10.350 --> 00:16:16.499
to apply. And let me quickly show off how
this is done. So how do I add two points
00:16:16.499 --> 00:16:21.220
on this curve? Well, you take these two
points, you put a line through it, and
00:16:21.220 --> 00:16:27.430
then there is a law that says that if I
put a line through two points, then it
00:16:27.430 --> 00:16:32.060
has, the line has to cut the curve from
the third point. Okay. So I put the line
00:16:32.060 --> 00:16:36.779
through these two points. It cut the curve
in the third point all the way up on the
00:16:36.779 --> 00:16:41.069
right. You know, what I'm going to do is
I'm going to reflect the point down on the
00:16:41.069 --> 00:16:46.379
X axis. Okay. So I draw this other line, I
reflect it down. And then what I define is
00:16:46.379 --> 00:16:56.110
that other, that I cut, this I define to
be the sum of these two points. Okay. So.
00:16:56.110 --> 00:17:00.649
And that works. Okay. I can add points, I
can subtract points. There will be the
00:17:00.649 --> 00:17:05.370
inverse. So this kind of like X like
integers mod N when you only consider
00:17:05.370 --> 00:17:09.559
addition, kind of, kind of, it's not
really the same, but you can also single
00:17:09.559 --> 00:17:16.770
out the special point O like beautiful O
we call the origin, whatever that is. And
00:17:16.770 --> 00:17:20.860
this origin kind of acts like a zero. So
if I add the origin to the point where I
00:17:20.860 --> 00:17:25.120
get the point again, or if I add the point
and its inverse I get that point, I get
00:17:25.120 --> 00:17:30.630
zero. Okay. So there's something like a
zero. And you can also multiply points,
00:17:30.630 --> 00:17:34.809
right. I mean what is multiplication, it's
just repeated addition. So in brackets n,
00:17:34.809 --> 00:17:38.919
this is what I write for point
multiplication, just add the point n times
00:17:38.919 --> 00:17:43.440
to itself. Okay. So there's nothing fancy
going on here. So you can somehow add
00:17:43.440 --> 00:17:49.510
points. You can multiply points. That's
pretty cool. And if you look closer, you
00:17:49.510 --> 00:17:55.780
can look at the special set here that I
denoted E brackets, big N. And these are
00:17:55.780 --> 00:18:00.600
all the points on the curve such that if I
multiplied this point for N it gives me
00:18:00.600 --> 00:18:08.130
zero. Okay. And this set for the
mathematically inclined people among us I
00:18:08.130 --> 00:18:12.500
know say this is somehow the N-torsion of
an elliptic curve, whatever that means.
00:18:12.500 --> 00:18:16.370
But if you're interested, you can look it
up. And this set kind of acts like
00:18:16.370 --> 00:18:23.520
additive integers mod n - like two copies
of it. Okay. And now this is where the
00:18:23.520 --> 00:18:26.980
term super singular comes from. One of the
definitions. This is not the only
00:18:26.980 --> 00:18:30.530
definition, but this is one of them. If
you look at the elliptic curve, not over
00:18:30.530 --> 00:18:36.029
the reals, okay, or whichever numbers, but
over this finite fields. And if you look
00:18:36.029 --> 00:18:41.980
at the torsion, the P-torsion, then this
behaves differently for different types of
00:18:41.980 --> 00:18:45.279
curves. Okay. The P-torsion is either
empty, then we call the curve super
00:18:45.279 --> 00:18:50.400
singular; or it's just one copy of of
integers mod P and then we call it
00:18:50.400 --> 00:18:55.149
ordinary. Okay. It's not really important
to know what that means. It just means
00:18:55.149 --> 00:18:59.980
that there is a distinction for curves
somehow that's somehow ingrained
00:18:59.980 --> 00:19:07.730
mathematically deep down there. And
because this E N torsion is somehow two
00:19:07.730 --> 00:19:13.809
copies of of integers mod N, additive
integers mod N, I can generate it by
00:19:13.809 --> 00:19:17.539
taking linear combinations of two points,
say P and Q, and these are like the
00:19:17.539 --> 00:19:21.679
generators we saw earlier. Right. But
these are not additive generators instead
00:19:21.679 --> 00:19:26.831
of somehow exponential generators. But it,
everything behaves kind of similar. And
00:19:26.831 --> 00:19:30.240
now you can really use this to do
cryptography already. If you wanted to
00:19:30.240 --> 00:19:35.899
write it. You can. You can somehow look at
the DLP in that group, but there is the
00:19:35.899 --> 00:19:40.510
problem again that the DLP in there,
there's Shor's algorithm again. Right. So
00:19:40.510 --> 00:19:46.970
even if you do cryptography in this group,
you run into the same problem. OK, so we
00:19:46.970 --> 00:19:51.481
have to do a bit better. We have to search
further. And this is where isogenies come
00:19:51.481 --> 00:20:03.860
on. Come into the play. So one way you can
think of an isogeny is, remember how we
00:20:03.860 --> 00:20:10.710
found integers mod N by somehow dividing
Z by all the N multiples. And you can do
00:20:10.710 --> 00:20:16.919
something similar with an elliptic curve.
if you can somehow take part of this
00:20:16.919 --> 00:20:24.029
N-torsion and you can divide an elliptic
curve by this. You can mod it out and it
00:20:24.029 --> 00:20:28.609
turns out this is mathematically well-
defined and it gives you another elliptic
00:20:28.609 --> 00:20:37.559
curve. Okay. So I take a curve, E1, I take
a part of my N-torsion. I divide elliptic
00:20:37.559 --> 00:20:42.840
curve E1 by G and I get another elliptic
curve E2. And there's something else that
00:20:42.840 --> 00:20:46.500
comes along with this construction. And
this is what we call the isogeny. This is
00:20:46.500 --> 00:20:53.380
a map. OK. Along with this construction
comes a map from E1 to E2. And this map is
00:20:53.380 --> 00:21:00.769
what we call an isogeny. An isogeny is the
map that takes us from one curve to
00:21:00.769 --> 00:21:07.140
another curve. And this map is kind of
special because it behaves in a nice way
00:21:07.140 --> 00:21:12.200
and it plays nicely with the structure
that's already ingrained in our curve.
00:21:12.200 --> 00:21:17.840
Namely, I can either add two points on my
starting curve and send it through that
00:21:17.840 --> 00:21:25.240
map to the other curve. Or it can take two
points on my starting curve. I can send it
00:21:25.240 --> 00:21:31.600
through the map and edit over there and it
gives me the same thing. So this map
00:21:31.600 --> 00:21:35.539
behaves nicely with point addition. That's
pretty nice, just as a side note. So this
00:21:35.539 --> 00:21:42.140
map is special. So this is just the
remainder of what I said: Adding points on
00:21:42.140 --> 00:21:47.250
E1 and sending the result to E2 is the
same as sending points to E2 and adding
00:21:47.250 --> 00:21:53.890
them there. So this map somehow plays nicely
with my laws on my elliptic curve. Now I
00:21:53.890 --> 00:22:01.820
have to make a definition: In mathematics,
the kernel of a map is the set of all the
00:22:01.820 --> 00:22:08.240
inputs to the map that are sent to zero.
And we saw this origin O here that acted
00:22:08.240 --> 00:22:12.470
like zero. So the kernel of my isogeny,
I'm just going to define as all the inputs
00:22:12.470 --> 00:22:18.240
to the isogeny that are sent to the zero
on the other curve. And in written
00:22:18.240 --> 00:22:25.230
notation, it's the set of all P in E1 such
that the map of P is 0. It turns out that
00:22:25.230 --> 00:22:34.512
this kernel for my isogeny, that I started
out with somehow recovers this part of the
00:22:34.512 --> 00:22:40.559
end portion that I used to construct. So
there's two ways now to think of an
00:22:40.559 --> 00:22:47.890
isogeny. So this is what we start with. We
reconsidered E1 mod G and it gave us this
00:22:47.890 --> 00:22:54.270
map from E1 to E2. But if I start with
this map from E1 to E2, we also find the G
00:22:54.270 --> 00:22:59.320
again. So there are two ways to represent
this map. We can think of a subgroup -
00:22:59.320 --> 00:23:06.630
this G - or we can think of the map. And
ultimately somehow there is a correspondence
00:23:06.630 --> 00:23:12.000
between the various subgroups for
different N and isogenies that are somehow
00:23:12.000 --> 00:23:15.900
emanating from a curve. We can think of
this link or the hairs on my head, they
00:23:15.900 --> 00:23:20.760
are going out and then they're going to
reach other electric curves maybe. And
00:23:20.760 --> 00:23:27.020
these notions can be used interchangeably.
So somehow there is a correspondence. And
00:23:27.020 --> 00:23:32.659
again, I can choose different ends. So some-
how from one curve, I can have many outgoing
00:23:32.659 --> 00:23:40.210
isogenies that are different in a sense. And
now the thing is in practice, we actually want to
00:23:40.210 --> 00:23:43.899
compute these maps. So right now, this is
just general abstract nonsense. I didn't
00:23:43.899 --> 00:23:47.470
tell you anything of how to compute these
things. I just told you there are some
00:23:47.470 --> 00:23:50.600
more correspondences. But I mean, what
does that even mean? Right. It's useless
00:23:50.600 --> 00:23:57.250
if I can't use it in practice. And then
there is another thing: You can compute
00:23:57.250 --> 00:24:00.409
these things, there are formulas, people
have worked on this. But somehow the cost
00:24:00.409 --> 00:24:08.000
grows if I enlarge N. So really, in
practice, for applications, I want to choose
00:24:08.000 --> 00:24:13.670
a small N. Maybe two or three - that would
be pretty good. And now the thing is, it's
00:24:13.670 --> 00:24:19.250
the supersingular curves for which I can some-
how control or choose the possible ends very
00:24:19.250 --> 00:24:27.091
very easily. So this is the reason why we
reconsider supersingular curves. Now I can
00:24:27.091 --> 00:24:33.699
choose my prime to be of this form and
then magically this is going to force 2
00:24:33.699 --> 00:24:39.559
and 3 being possible. So this is the
reason why we choose supersingular ones.
00:24:39.559 --> 00:24:45.080
There's some theory which is not
interesting for you, but it's important
00:24:45.080 --> 00:24:52.350
for implementation. And there's a way basically
for us to force the curve to have those
00:24:52.350 --> 00:24:57.490
isogenies that we like. But there is
another important reason and this is the
00:24:57.490 --> 00:25:01.450
reason that actually makes it
interesting for cryptography. So what I
00:25:01.450 --> 00:25:07.919
can do is: I start with an arbitrary
curve, and this just might not be a
00:25:07.919 --> 00:25:12.730
supersingular one, just any curve and say I
consider all the outgoing two isogenies if
00:25:12.730 --> 00:25:19.299
these are possible, 4 and 2. So there's
going to be 1, 2 and 3. And then again,
00:25:19.299 --> 00:25:24.930
from E1, I can again consider all the
outgoing isogenies, and so on and so
00:25:24.930 --> 00:25:28.970
forth. So what's going to happen here is:
This is going to generate a graph, where
00:25:28.970 --> 00:25:36.860
the vertices of my graph are elliptic curves
and the edges are isogenies. So somehow
00:25:36.860 --> 00:25:44.260
behind the scenes there is this graph
hidden. Now, it turns out that if you do
00:25:44.260 --> 00:25:48.580
this for a supersingular elliptic curve -
and I generated this yesterday for you,
00:25:48.580 --> 00:25:52.970
so this is one possible graph - I can
remember which prime I took. But here you
00:25:52.970 --> 00:25:57.350
can see all the ellipses are ellipitic
curves and all the edges between them are
00:25:57.350 --> 00:26:03.330
2 isogenies. So this is an example of a
supersingular 2-isogeny graph - okay, this
00:26:03.330 --> 00:26:11.169
looks pretty wild. I can do the same for N
= 3 if it's possible, or is 5 and so on
00:26:11.169 --> 00:26:17.020
and so forth. There are many many graphs
hidden. But why is the supersingular graph
00:26:17.020 --> 00:26:20.900
specific and important? Well, it turns out
that somehow the supersingular one is
00:26:20.900 --> 00:26:27.440
connected, and it's what we call a
Ramanujan graph. I'm going to explain
00:26:27.440 --> 00:26:33.740
this in a second. And as a bonus, for
implementation purposes, it turns out that
00:26:33.740 --> 00:26:39.559
you can do all your implementation in
arithmetics in the finite field with p^2
00:26:39.559 --> 00:26:45.409
elements. This is nice. So I'm just gonna
say that if you don't consider
00:26:45.409 --> 00:26:49.200
supersingular curves and you go along
these graphs, then what's going to happen
00:26:49.200 --> 00:26:54.330
is that somehow this "field of
definition", what we call it, could grow
00:26:54.330 --> 00:26:59.320
for you to be able to go further, but that
would suck for implementation. But
00:26:59.320 --> 00:27:04.279
supersingular ones is nice so, F_p^2 is
enough. So this is again, is good for
00:27:04.279 --> 00:27:10.300
implementation. So somehow magically many
many things happen here that are benefiting us.
00:27:10.300 --> 00:27:15.460
And again, why is it nice that this is a
Ramanujan graph? A Ramanujan graph has
00:27:15.460 --> 00:27:21.090
certain optimal expansion properties. This
means that if I start from a random point
00:27:21.090 --> 00:27:28.539
in my fraph, and I take a random walk with some-
how logarithmic steps of the total amount of
00:27:28.539 --> 00:27:38.130
vertices, then this will put me in a very
uniform place in that graph. And this is
00:27:38.130 --> 00:27:43.580
is good for cryptography. Because you only
need to take log many steps to somehow
00:27:43.580 --> 00:27:50.120
randomize yourself in that graph. And this
is what this could look like. I started at
00:27:50.120 --> 00:27:55.669
that red ellipses over there. This was my
starting point. And then I generated a few
00:27:55.669 --> 00:28:01.919
random walks, and the blue points are
where I got placed. This might not prove
00:28:01.919 --> 00:28:09.099
anything, but it gives you an idea of how, some-
how uniformly, it places me around that graph.
00:28:09.099 --> 00:28:17.080
So, it's good for cryptography, but there
are other reasons, so supersingular elliptic
00:28:17.080 --> 00:28:22.400
curves somehow I can actually compute how
many of these curves I will have in my
00:28:22.400 --> 00:28:26.540
graph. This is another reason to be
looking at these things. Because if I
00:28:26.540 --> 00:28:30.740
don't even know how many curves are in my
graph - well I can't really say anything
00:28:30.740 --> 00:28:35.179
about the security - but at least for
supersingular ones, I can see they're
00:28:35.179 --> 00:28:42.169
roughly p/ 12 many. Okay, and then again,
if I'd choose my p about n bits, well then
00:28:42.169 --> 00:28:47.660
I really know that my graph has about 2^n
elements. And at least there I can see
00:28:47.660 --> 00:28:51.830
something about the cryptographic
strength, right? I can make M big and then
00:28:51.830 --> 00:28:54.620
you can say: Oh yeah, you have this random
graph, you take some n-length walks and
00:28:54.620 --> 00:28:58.669
n-length walks and then it places you
randomly in there and the whole graph is
00:28:58.669 --> 00:29:04.320
about 2^n elements. And then I can say
something about the expected runtime of
00:29:04.320 --> 00:29:09.779
algorithms. So this is another reason why
we want to consider supersingular curves:
00:29:09.779 --> 00:29:16.139
Because I can tell you how many elements
are in this graph. So a quick summary of
00:29:16.139 --> 00:29:21.490
what we saw, why this is nice. So what you
get is a compact representation of an
00:29:21.490 --> 00:29:27.549
(l+1)-regular graph. And we saw examples,
e.g. l = 2, l = 3. Bigger values are
00:29:27.549 --> 00:29:30.700
possible, but we don't even care about
those because this is what gives us the
00:29:30.700 --> 00:29:38.510
fastest arithmetic such that we can work
with F_p^2. This is nice, this keeps our
00:29:38.510 --> 00:29:43.759
implementation fast. I can tell you how
many vertices are in the graph: about
00:29:43.759 --> 00:29:48.840
p/12. And again, such that the graph for
mixing properties that are useful for
00:29:48.840 --> 00:29:52.369
cryptographic applications. So because I
want to use this ultimately for
00:29:52.369 --> 00:29:59.850
cryptography. And again, that's what we
said: If I choose an n-bit prime p, then
00:29:59.850 --> 00:30:07.159
the graph has about 2^n vertices - so
exponentially many vertices. And it turns
00:30:07.159 --> 00:30:16.240
out that there are some hard problems that
I can ask you to solve in this graph that
00:30:16.240 --> 00:30:23.130
don't have good quantum algorithms. So one
hard problem is this: I take two super
00:30:23.130 --> 00:30:28.630
singular elliptic curves, so I just give you
two random curves in this graph and ask
00:30:28.630 --> 00:30:33.120
you to find a nice arch in the path
between those isognies, or three
00:30:33.120 --> 00:30:37.880
isogenies. And it turns out that this just
doesn't have a good quantum algorithm. So
00:30:37.880 --> 00:30:42.750
classically, I mean the numbers are super
important here, but classically the
00:30:42.750 --> 00:30:47.700
complexity is p, over the fourth root of p,
and the best quantum algorithm is a bit
00:30:47.700 --> 00:30:52.679
better at it. I mean again, it's not super
important what's there. What's important
00:30:52.679 --> 00:30:58.000
is that there is no polynomial time
algorithm compare to ideal p that we
00:30:58.000 --> 00:31:03.060
started with. So if I make this p very large
and your quantum computer, your
00:31:03.060 --> 00:31:07.910
hypothetical quantum computer, will
probably not solve this. Okay, so that's
00:31:07.910 --> 00:31:14.960
cool. So how do we do key exchange? I
start with a supersingular elliptic curve E,
00:31:14.960 --> 00:31:21.350
where I chose my prime p such that two and
three isogenies are possible. And then
00:31:21.350 --> 00:31:26.019
Alice - earlier I remember she chose a
random number a - but now Alice will
00:31:26.019 --> 00:31:35.539
choose a random subgroup A, and she will
send E mod A to Bob. This amounts to Alice
00:31:35.539 --> 00:31:40.940
for computing the nice isogeny. And again,
this is a very symmetrical key exchange,
00:31:40.940 --> 00:31:45.459
except that now Bob won't use the same
generator but Bob will use the 3
00:31:45.459 --> 00:31:50.830
isogenies. So Bob will choose a random
subgroup B, and then he will compute E mod
00:31:50.830 --> 00:31:58.190
B and send this to Alice. And this is the
picture: There's Alice, there's Bob. Alice
00:31:58.190 --> 00:32:04.520
chose A, Bob chooses B. Alice sends E mod
A to Bob, Bob sends E mod B to Alice. And
00:32:04.520 --> 00:32:12.129
then how do they agree on a shared key?
They will just mod out by their respective
00:32:12.129 --> 00:32:16.419
subgroups again. And it turns out that the
elliptic curve that they find is going to
00:32:16.419 --> 00:32:23.090
be the same for both of them. Okay, so how
does that work? Again, let's return to our
00:32:23.090 --> 00:32:32.610
graph: Say Alice and Bob agree on a black
curve - the black curve on the left side.
00:32:32.610 --> 00:32:36.929
And then Alice will compute these red
steps, which correspond to taking a
00:32:36.929 --> 00:32:42.030
subgroup. So Alice will compute these red
steps for her secret subgroup and she will
00:32:42.030 --> 00:32:48.669
end up at the red curve in the upper right
corner. And Bob will do the same. But now
00:32:48.669 --> 00:32:53.370
Bob is not in the 2-graph, but in the
3-graph - so this is the three graph. And
00:32:53.370 --> 00:32:57.600
the black curve that he started from in
the 3-graph is down there. He will also
00:32:57.600 --> 00:33:02.039
select a random subgroup, compute the
secret path and Bob will end up in the
00:33:02.039 --> 00:33:06.549
blue curve. Now Alice will send her red
curve to Bob. And Bob, will send his blue
00:33:06.549 --> 00:33:12.039
curve to Alice. And then Alice will
consider the blue curve in the 2-graph. So
00:33:12.039 --> 00:33:17.320
Alice starts from the blue curve that she
got from Bob - and this is the position in
00:33:17.320 --> 00:33:23.260
the 2-graph. And again, she computes that
same secret path and ends up in the green
00:33:23.260 --> 00:33:30.390
curve, which is up there. Bob got the red
curve from Alice. So Bob has the red curve
00:33:30.390 --> 00:33:34.335
there. Again, he computes the path and
then ends up at the green curve. And it
00:33:34.335 --> 00:33:38.440
turns out that the green curves here and
there are the same. And this is going to
00:33:38.440 --> 00:33:45.960
be the shared key for them. This is SIDH.
Okay. This is how you exchange a secret
00:33:45.960 --> 00:33:54.101
key using the supersingular isogeny graph.
That's the whole magic. And again, let's
00:33:54.101 --> 00:34:01.370
compare these two things a bit: the DLP-
based one and the SIDH one. So we had the
00:34:01.370 --> 00:34:07.730
square, Alice and Bob started in the upper
left corner and again ended up in the lower
00:34:07.730 --> 00:34:14.760
right corner. And SIDH looks very similar:
Alice and Bob start with this common curve
00:34:14.760 --> 00:34:22.720
E in the upper left corner. Again, Alice
computes only horizontal arrows because
00:34:22.720 --> 00:34:27.750
she knows her secret group A, and Bob only
computes the vertical arrows because only
00:34:27.750 --> 00:34:34.490
he knows his secret group B. And again,
they both end up in the lower right
00:34:34.490 --> 00:34:40.110
corner, where they define the shared key.
But now in this case, the shared key is
00:34:40.110 --> 00:34:44.860
not an element to the a^(ab), but elliptic
curve. But again, there's a mathematical
00:34:44.860 --> 00:34:51.881
way to attach a unique number to it. So
it's a solved problem to actually make
00:34:51.881 --> 00:34:59.660
some bytes out of this. And yeah, that's
SIDH. That's everything. This is a nice
00:34:59.660 --> 00:35:06.520
example of a post-quantum cryptography
scheme that we have today. And now
00:35:06.520 --> 00:35:13.290
let me finish with a quick conclusion. I
showed you this "zoo": There are several
00:35:13.290 --> 00:35:18.840
candidates somehow for post-quantum
cryptography. And among them are some
00:35:18.840 --> 00:35:26.090
schemes based on supersingular elliptic
curve isogenies, and we've seen that we
00:35:26.090 --> 00:35:30.460
know some hard problems involving these
isogenies that are hard for quantum
00:35:30.460 --> 00:35:40.511
computers, which makes this one possible
scheme for a quantum computer world. And
00:35:40.511 --> 00:35:44.950
probably I should say that we don't
envision a world here where we users like
00:35:44.950 --> 00:35:49.960
me or you are in possession of quantum
computers. Probably, what we think about
00:35:49.960 --> 00:35:55.210
is that state actors are in positions of
quantum computers. So this is even more
00:35:55.210 --> 00:36:01.500
important for us to be looking into these
things. And what we saw was to perform a
00:36:01.500 --> 00:36:05.290
Diffie-Hellman-like key exchange using
these isogenies. But - this is what I
00:36:05.290 --> 00:36:10.410
didn't tell you about in his talk - there
are also schemes for signature-based
00:36:10.410 --> 00:36:15.950
isogenies, there is this scheme for key-
encapsulation-based isogenies. So
00:36:15.950 --> 00:36:22.680
there are other possible candidates for
other cryptographic building blocks based
00:36:22.680 --> 00:36:29.110
on isogenies and these hard problems. And
if you're super interested about this, you
00:36:29.110 --> 00:36:36.660
can either ask me or come to our assembly
and if you like reading scientific papers,
00:36:36.660 --> 00:36:39.900
papers about such isogenies and
cryptography in general, you can find this
00:36:39.900 --> 00:36:45.240
on the eprint archive. So this is a web
page where people post pre-prints about
00:36:45.240 --> 00:36:50.370
their papers and there's a huge collection
about, among of them, isogeny papers. So
00:36:50.370 --> 00:36:58.380
if you're interested in this, this is the
place to research. And with that, I would
00:36:58.380 --> 00:37:01.440
like to thank you all for your attention.
00:37:01.440 --> 00:37:14.870
applause
00:37:14.870 --> 00:37:22.600
Herald Angel: Is there any question? OK, I
got the Signal Angel there, doing some
00:37:22.600 --> 00:37:27.640
Morse code?
Microphone 1: Yes. Can you recommend any
00:37:27.640 --> 00:37:33.280
literature for the theoretical background?
naehrwert: The theoretical background?
00:37:33.280 --> 00:37:41.510
There are a few papers that are nice.
Okay. The question again was literature
00:37:41.510 --> 00:37:46.050
about theoretical background. And yes,
there are a few papers that are giving
00:37:46.050 --> 00:37:53.180
some nice, even theoretically involved
summaries about the background. And your
00:37:53.180 --> 00:38:00.940
best bet is to go to eprint and you enter
'isogenies' in the mask of search terms,
00:38:00.940 --> 00:38:07.400
or 'SIDH', and look at the papers that
say, maybe, 'A Short Introduction to
00:38:07.400 --> 00:38:11.380
Isogenies' or something like that. I mean,
you will find them if you search for them.
00:38:11.380 --> 00:38:17.500
I don't know them from the top of my head,
but they're out there for sure. Yeah, and
00:38:17.500 --> 00:38:22.590
thanks for him - So there is a very recent
paper by Craig Costello, also somewhat
00:38:22.590 --> 00:38:26.670
titled 'A Short Introduction', something
like that. So this is also maybe a good
00:38:26.670 --> 00:38:30.830
source for you to look at.
Herald Angel: Um, yeah, 'Isogenies for
00:38:30.830 --> 00:38:32.730
Beginners'.
naehrwert: 'Isogenies for Beginners'.
00:38:32.730 --> 00:38:35.790
Thank you.
audience laughing
00:38:35.790 --> 00:38:44.500
Microphone 2: Hello. Yeah. So you've used
elleptic curve as an algebraic group,
00:38:44.500 --> 00:38:54.700
right, to compute these isogeny graphs.
Why do you use elliptic curves - what's
00:38:54.700 --> 00:39:02.770
the properties of elliptical curves as a
group? So, could you use any group to
00:39:02.770 --> 00:39:10.980
compute these graphs and could you use
these as the basis for your scheme or your
00:39:10.980 --> 00:39:14.890
key exchange scheme?
naehrwert: Okay, so the question was why
00:39:14.890 --> 00:39:21.280
use elliptical curves and the group
structure that the impose to look at
00:39:21.280 --> 00:39:26.220
isogeny graphs involving elliptical curves
and whether I could use other groups. And
00:39:26.220 --> 00:39:34.001
actually, there's a two-fold answer maybe.
So if I go back - or actually let me go to
00:39:34.001 --> 00:39:40.650
my backup slide, which gives you SIDH in
its full glory - you consider some extra
00:39:40.650 --> 00:39:46.170
information being sent, namely these
generators from my group and actually the
00:39:46.170 --> 00:39:51.700
same commutative diagram for SIDH. You
could, in theory, compute using another
00:39:51.700 --> 00:39:57.670
group as well, that has the proper
subgroup structure, but the graph that you
00:39:57.670 --> 00:40:03.910
will find is probably not going to be
interesting. I mean it's really somehow
00:40:03.910 --> 00:40:09.100
that Righello property that makes the
graph interesting for cryptography. But
00:40:09.100 --> 00:40:15.020
yes, in theory, the SIDH commutative
diagram you could also compute for other
00:40:15.020 --> 00:40:20.720
groups, yes.
Microphone 2: OK.
00:40:20.720 --> 00:40:28.910
Microphone 3: Uh... How good are classical
algorithms that tried to reverse that SIDH
00:40:28.910 --> 00:40:37.010
problem, because that will be the bound
for how large your keys have to be, to be
00:40:37.010 --> 00:40:39.931
secure.
naehrwert: Yes. So the question was: How
00:40:39.931 --> 00:40:46.980
good are classical algorithms? And again,
I said, I think the runtime for those is
00:40:46.980 --> 00:40:52.950
squared of p. And this tells you how big
you have to choose B.
00:40:52.950 --> 00:40:59.160
Microphone 3: And how confident are you
that this really is hard for quantum
00:40:59.160 --> 00:41:03.510
computers as well?
naehwert: Well, how confident am I that
00:41:03.510 --> 00:41:07.020
this is really hard for quantum
computers? So first of all, cryptography
00:41:07.020 --> 00:41:10.740
is all about confidence, right? So someone
proposes a problem, this problem gets
00:41:10.740 --> 00:41:15.350
crypto-analyzed. And if it's not broken
after 40 years, then people will say, I'm
00:41:15.350 --> 00:41:19.810
pretty, pretty confident this is good. And
maybe if the NSA doesn't tell you anything
00:41:19.810 --> 00:41:26.200
about it, or maybe if they don't have, you
know, anything on it, then you can also
00:41:26.200 --> 00:41:35.240
see that you're confident in it. But I
think this is really a question that only
00:41:35.240 --> 00:41:40.980
time can answer, right?
Microphone 4: Yeah. Is it possible to
00:41:40.980 --> 00:41:47.321
prove that no polynomial-time algorithms
for the isogenies problems can exist
00:41:47.321 --> 00:41:51.810
for a quantum computer?
naehrwert: Yeah, that's a good question.
00:41:51.810 --> 00:41:59.610
How do you prove that no algorithm exists?
This brings us into territories, like ...
00:41:59.610 --> 00:42:06.380
Yeah. I don't know. Yeah.
No. Let's not do that.
00:42:06.380 --> 00:42:16.500
Microphone 1: Yeah. Good talk by the way.
At the last slide you say that this is hard
00:42:16.500 --> 00:42:20.850
for a quantum [computer]. But that can't
be true because we don't even know if any
00:42:20.850 --> 00:42:25.600
algorithm is hard for classic computers.
Right? So, I'm guessing you're saying that
00:42:25.600 --> 00:42:31.340
intuitively it feels hard, which, you
know, is the same intuition I have about
00:42:31.340 --> 00:42:37.650
e.g. factoring in. So, you mention there's
multiple candidates for post-quantum
00:42:37.650 --> 00:42:44.120
cryptography, and they all intuitively
feel hard somehow. Do you know if this
00:42:44.120 --> 00:42:48.480
specific candidate, would this be your
horse in a race? Is there anything about
00:42:48.480 --> 00:42:54.320
this specific way that you think would be
the best fit for post-quantum
00:42:54.320 --> 00:42:59.310
cryptography?
naehrwert: Okay. Your opinion is very
00:42:59.310 --> 00:43:03.410
valid. Of course, we don't know if it's
hard, right? This connects back to the
00:43:03.410 --> 00:43:07.400
other questions: How do you trust
something like that? Again, people do
00:43:07.400 --> 00:43:11.950
crypto analysis for 40 years or whatever.
And then you say, oh, no one found
00:43:11.950 --> 00:43:16.030
anything - it's probably hard, right? But
it hasn't been an exact 40 years. You
00:43:16.030 --> 00:43:21.480
cannot say that. Indeed these things are
relatively new. And personally, I'm not
00:43:21.480 --> 00:43:28.430
gonna, I don't know, believe in any of
these things until some time passes. So my
00:43:28.430 --> 00:43:33.060
reason for looking into these things
really is more a mathematical curiosity,
00:43:33.060 --> 00:43:38.500
because I think these things are
beautiful. And the cryptography that
00:43:38.500 --> 00:43:43.370
arises from it is more of a side-effect
for me personally. So I'm not going to put
00:43:43.370 --> 00:43:51.180
out any guesses on which of these things
is actually going to win the PQ race or
00:43:51.180 --> 00:43:56.140
whatever.
Microphone 2: (Yeah. I am.) You showed or
00:43:56.140 --> 00:44:01.660
said you think it's hard for the classical
way and for the quantum cryptography way.
00:44:01.660 --> 00:44:08.830
I think I just read a paper last year
about a combined way in classical and
00:44:08.830 --> 00:44:14.261
quantum cryptography combined, which
outperforms either one of those ways. Do
00:44:14.261 --> 00:44:23.820
you think this could also be relevant or
gonna make this one way to put in
00:44:23.820 --> 00:44:27.600
computable in polynomial time?
naehrwert: Are you talking about an
00:44:27.600 --> 00:44:32.640
algorithm that somehow combines a
classical step and a quantum step to break
00:44:32.640 --> 00:44:33.900
this?
Microphone 2: Yes.
00:44:33.900 --> 00:44:39.390
naehwert: Yeah well, most algorithms that
we say use a quantum computer involve a
00:44:39.390 --> 00:44:43.330
classical part anyways. If you think about
Shor's algorithm, there's a classical part
00:44:43.330 --> 00:44:49.600
and a quantum computer part. So I'm not
sure which algorithm you read about, but
00:44:49.600 --> 00:44:53.560
I'm sure that somehow all the quantum
algorithms involve a classical part
00:44:53.560 --> 00:44:58.690
implicitly anyways.
Herald: Signal Angel?
00:44:58.690 --> 00:45:03.400
Microphone 3: Yeah. Can you please name
the mentioned contestants in the list
00:45:03.400 --> 00:45:10.400
'Challenge-based Isogenies'?
naehrwert: So there is SSIKE, I believe:
00:45:10.400 --> 00:45:16.170
supersingular isogeny key encapsulation,
but actually I don't really follow the
00:45:16.170 --> 00:45:22.080
NIST thingy closely, so I actually
couldn't even name all the names that are
00:45:22.080 --> 00:45:27.440
involved in it, but you can look it up on the
NIST website and I believe somewhere there
00:45:27.440 --> 00:45:33.190
is also a classification of the contenders
into this view. So they will tell you
00:45:33.190 --> 00:45:37.180
which contenders are based on lattices and
which contenders are based on codes and
00:45:37.180 --> 00:45:41.400
which ones are somehow based on isogenies.
But off the top of my head, actually, I
00:45:41.400 --> 00:45:49.990
don't even know. Sorry.
Microphone 1: So if I got everything
00:45:49.990 --> 00:45:56.730
correctly, though, those isogenies are
group homomorphisms between the elliptic
00:45:56.730 --> 00:46:03.580
curves and the factor group of the
elliptic curve by g. And which has kernel
00:46:03.580 --> 00:46:05.040
g again.
naehrwert: Yes.
00:46:05.040 --> 00:46:10.170
Microphone 1: And you said that finding
the isogeny path in the graph is rather
00:46:10.170 --> 00:46:15.720
difficult. But wouldn't the real
difficulty rather be finding the subgroups
00:46:15.720 --> 00:46:20.290
G - because a group homomorphism between
the elliptic curve and the factor group
00:46:20.290 --> 00:46:23.450
with kernel g is simply the canonical
protection.
00:46:23.450 --> 00:46:29.500
naehrtwert: Exactly. So I see you are
mathematically trained, which is very nice
00:46:29.500 --> 00:46:34.140
and I appreciate that, this is great and I
am very happy about that. And yeah, if you
00:46:34.140 --> 00:46:41.440
look at the slide actually, the secrets
are these alphas and betas, which somehow
00:46:41.440 --> 00:46:46.420
determine the subgroup. And yes, finding
those isogeny path is equivalent to
00:46:46.420 --> 00:46:50.240
finding the alpha, somehow, that generates
this group. And as you said correctly,
00:46:50.240 --> 00:46:56.670
finding the isogeny path is somehow
finding this group. But it's just
00:46:56.670 --> 00:47:00.940
restating the problem. But it's still hard
somehow to find this group. Yeah.
00:47:00.940 --> 00:47:05.430
Microhone 1: All right. Thanks.
naehrwert: Thank you. Very cool.
00:47:05.430 --> 00:47:08.940
Microphone 2: Yeah, thank you for the
great talk. So, can you play this game a
00:47:08.940 --> 00:47:15.270
little bit further? I mean, can you choose
higher-dimensional abelian varieties to
00:47:15.270 --> 00:47:19.440
make it even more secure? Or is it just
absolutely inaccessible? I mean, from the
00:47:19.440 --> 00:47:24.160
computation perspective, the choice of
field of definition is difficult, for
00:47:24.160 --> 00:47:26.430
example, so...
naehrwert: Okay, so the question was on
00:47:26.430 --> 00:47:30.510
whether you can use higher-dimensional
abelian varieties and maybe for the people
00:47:30.510 --> 00:47:35.760
who don't know what that means: You can
attach a dimension to these things in the
00:47:35.760 --> 00:47:41.270
elliptic curves, somehow have a dimension
1 attached to them. And the question was,
00:47:41.270 --> 00:47:45.720
can you somehow look at dimension 2,
dimension 3 or higher? And actually, back
00:47:45.720 --> 00:47:51.210
in the days when people were thinking
about the DLP problem on the points of
00:47:51.210 --> 00:47:55.570
elliptic curves that I mentioned briefly,
people had the idea of maybe using
00:47:55.570 --> 00:48:01.231
dimension 2 or dimension 3. But it turns
out, that the DLP problem actually, at
00:48:01.231 --> 00:48:06.170
some point, gets easier in higher
dimensions. So, classically if you look at
00:48:06.170 --> 00:48:10.250
the DLP, you somehow want to stay at
dimension 2, but now, what you can do is,
00:48:10.250 --> 00:48:14.570
you can look at isogenies between
dimension-2 and dimension-3 ones. And
00:48:14.570 --> 00:48:17.860
actually the problem that arises there -
and this makes elliptical curves very
00:48:17.860 --> 00:48:23.260
special - is that we can compute isogenies
rather efficiently for elliptical curves
00:48:23.260 --> 00:48:27.510
because of Velu's formulas. Okay. So
this gives us a very direct means of
00:48:27.510 --> 00:48:32.670
computing D, but it actually gets hard as
the dimension grows. For example, for
00:48:32.670 --> 00:48:40.090
dimension 2 already, the only isogenies
that I am able to efficiently compute are
00:48:40.090 --> 00:48:45.890
2- and 3-isogenies. So there are some
packages out there that can compute higher
00:48:45.890 --> 00:48:50.850
ones, but only if my prime is very small
and for dimension 3 and higher it gets
00:48:50.850 --> 00:48:55.810
even harder. And then there is another
thing that comes into play. So dimension-2
00:48:55.810 --> 00:49:00.300
varieties, they all arise from what we
call hyperelliptic curves. But if we look
00:49:00.300 --> 00:49:07.260
at dimension-3s and higher, then sometimes
you land at a point in your graph that
00:49:07.260 --> 00:49:11.600
does not come from a hyperelliptic curve
anymore. So there is another complication.
00:49:11.600 --> 00:49:17.600
So I mean, I had a friend who was looking
into genus-2 isogenies and it's possible
00:49:17.600 --> 00:49:24.260
to go there. But I don't know. I think
personally this is more of a toy than
00:49:24.260 --> 00:49:31.440
something that's good in practice.
Microphone 2: Can you use this scheme to
00:49:31.440 --> 00:49:35.650
implement a fully homomorphic encryption
scheme? Or is it already?
00:49:35.650 --> 00:49:40.860
naehrwert: Uhhh... No. No.
laughing
00:49:40.860 --> 00:49:45.440
naehrwert: Yeah, no fully homomorphic
encryption is somehow a pipe dream, but I
00:49:45.440 --> 00:49:51.030
mean sometimes it's possible. So the idea
is that you can add cipher texts and get
00:49:51.030 --> 00:49:55.840
the sum of the ciphered texts and have a
second operation, namely you should be
00:49:55.840 --> 00:50:00.120
able to multiply ciphertexts and get the
multiplication of two ciphertexts. But we
00:50:00.120 --> 00:50:07.490
didn't even talk about encryption.
Microphone 2: Yeah. Another question: Is
00:50:07.490 --> 00:50:12.110
there any crypto primitive used in the
isogeny approach that cannot be Stark-
00:50:12.110 --> 00:50:16.020
reduced to finding a hidden
subgroup in an abelian group?
00:50:16.020 --> 00:50:18.870
naehrwert: Could you repeat the
question, please?
00:50:18.870 --> 00:50:22.960
Microphone 2: Is there any crypto
primitive used in the isogeny approach
00:50:22.960 --> 00:50:28.560
that cannot be Stark-reduced to finding a
hidden subgroup in an abelian group?
00:50:28.560 --> 00:50:36.860
naehrwert: Okay. I think this question
tries to connect back to the hidden shift
00:50:36.860 --> 00:50:44.110
problem or the hidden subgroup problem and
Berg's algorithm. But I think I'm not able
00:50:44.110 --> 00:50:47.670
to answer that question now without
talking to the person that actually asked
00:50:47.670 --> 00:50:55.130
it because it's a bit vague.
So I'm sorry about that.
00:50:55.130 --> 00:50:59.050
Microphone 3: How do you send an
elliptical over the wire?
00:50:59.050 --> 00:51:02.680
naehrwert: Yeah, maybe I should answer
that actually. So we saw the
00:51:02.680 --> 00:51:09.000
parameterization of the curve that had
these coefficients A and B. But what
00:51:09.000 --> 00:51:14.510
I didn't tell you is that to an elliptic
curve you can actually attach what we call
00:51:14.510 --> 00:51:19.770
an invariant in mathematics and for an
elliptical curve, this is called a
00:51:19.770 --> 00:51:25.670
j-invariant and it's a single integer
which determines this elliptical curve
00:51:25.670 --> 00:51:29.600
uniquely. So if I want to send an
elliptical curve, I can simply send you
00:51:29.600 --> 00:51:34.600
its j-invariant. And if you know the field
of definition, you're going to be able to
00:51:34.600 --> 00:51:40.190
somehow recompute it just from the single
value. So it's actually quite a compact
00:51:40.190 --> 00:51:45.970
representation which makes
this also interesting. Yeah.
00:51:45.970 --> 00:51:49.260
Herald: I guess this is all. Thank you.
00:51:49.260 --> 00:51:54.860
applause
00:51:54.860 --> 00:51:58.800
postroll music
00:51:58.800 --> 00:52:23.000
subtitles created by c3subtitles.de
in the year 2020. Join, and help us!