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