1
00:00:00,000 --> 00:00:25,280
*36C3 preroll music*
*Applause*
2
00:00:25,280 --> 00:00:30,369
naehrwert: Yeah. Thank you for the
audience and thanks that you came. Thanks
3
00:00:30,369 --> 00:00:34,530
for the Congress for giving me the
opportunity to be here tonight, to be able
4
00:00:34,530 --> 00:00:39,880
to tell you a bit about post quantum
cryptography, a bit about as isogenies. I
5
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
6
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
7
00:00:52,500 --> 00:00:57,410
my day job is being a mathematics PhD
student at an undisclosed university. You
8
00:00:57,410 --> 00:01:03,320
can ask me in private if you're
interested. So previously I did physics. I
9
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
10
00:01:07,450 --> 00:01:12,320
you're interested about that shameless
plug, you can find us at Nintenbros
11
00:01:12,320 --> 00:01:17,220
Assembly later. You can ask us all about
our somehow console hacking endeavors. But
12
00:01:17,220 --> 00:01:24,220
enough about that. So I brought you some
pictures, screenshots of websites. So I
13
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
14
00:01:28,670 --> 00:01:36,210
about that Google paper on quantum
supremacy. So there is a Nature article
15
00:01:36,210 --> 00:01:42,280
about that beyond quantum supremacy. And
there is a Verge article that Google
16
00:01:42,280 --> 00:01:47,701
confirms quantum supremacy and
breakthrough, whatever that means. There
17
00:01:47,701 --> 00:01:52,020
is Google's own blog post about it. Notice
there are always these shiny pictures of
18
00:01:52,020 --> 00:01:57,909
these huge tubs filled with helium where
they house these quantum computers. So
19
00:01:57,909 --> 00:02:04,079
supremacy means the state or condition of
being superior to all others in authority,
20
00:02:04,079 --> 00:02:11,129
power, or status. So calling something
quantum supremacy, I mean, that screams
21
00:02:11,129 --> 00:02:16,420
something being pretty amazing. But what
actually does this mean for us? What does
22
00:02:16,420 --> 00:02:22,980
it mean for cryptography? And I think I
can relieve you all about from from maybe
23
00:02:22,980 --> 00:02:29,290
some fears that you had for us in
practice. Maybe today it doesn't really
24
00:02:29,290 --> 00:02:36,230
mean anything yet. So for cryptography
none of our underlying assumptions,
25
00:02:36,230 --> 00:02:40,601
whatever it means for now, are being
actively broken yet as we know or that we
26
00:02:40,601 --> 00:02:46,910
know of. But in theory, they are broken.
Okay. And because they're only broken in
27
00:02:46,910 --> 00:02:50,349
theory, that's pretty good. So we can
still blame the designers and implementers
28
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
29
00:02:57,080 --> 00:03:01,970
already wrote in the abstract a bit for
this talk, we should be, somehow, better
30
00:03:01,970 --> 00:03:06,980
be safe than sorry. So instead of somehow
waiting until the point of where quantum
31
00:03:06,980 --> 00:03:11,060
computers somehow become feasible to break
our cryptography, we should probably
32
00:03:11,060 --> 00:03:16,069
research it today. It's a bit with the
climate change, right? Suppose it's right
33
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
34
00:03:19,500 --> 00:03:24,900
going to be reborn to do the same for
cryptography. There are also three
35
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,
36
00:03:30,920 --> 00:03:34,519
but descriptions look pretty interesting.
So I'm going to leave that up for a few
37
00:03:34,519 --> 00:03:38,870
seconds. There is one called Provable
Insecurity, one called Cryptography
38
00:03:38,870 --> 00:03:42,819
Demystified and one about high assurance
cryptography software. I'm sure this is
39
00:03:42,819 --> 00:03:48,590
gonna be interesting. Okay, let's return
back to what I want to talk about. So
40
00:03:48,590 --> 00:03:53,810
there's something I chucklingly call the
Post-Quantum Cryptography Zoo. There are a
41
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
42
00:03:57,780 --> 00:04:01,600
going to say them out loud. Lattices,
codes, multivariate polynomial systems.
43
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
44
00:04:07,310 --> 00:04:11,760
that I want to briefly talk about tonight
called supersingular elliptic curve
45
00:04:11,760 --> 00:04:16,199
isogenies. OK, so this is the stuff that I
really like. Isogenies, they are great.
46
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
47
00:04:21,970 --> 00:04:26,369
many of you have a mathematics background.
Maybe I can do a test. Can people raise
48
00:04:26,369 --> 00:04:32,879
their hands where if they have some formal
training in, say, algebra? Yeah. Okay. So
49
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
50
00:04:37,759 --> 00:04:42,580
decimal numbers. This is Pi. Then there
are rational numbers somehow the are, one
51
00:04:42,580 --> 00:04:46,339
half, one third and so on and so forth.
Then there are integers from minus
52
00:04:46,339 --> 00:04:52,889
infinity to plus infinity and they follow
nice whole steps. But for working with
53
00:04:52,889 --> 00:04:56,619
those numbers and for cryptography, we
want something that's nicer behaved. We
54
00:04:56,619 --> 00:05:01,499
want somehow a finite set. OK. So this is
just important for implementation. And the
55
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
56
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
57
00:05:11,620 --> 00:05:16,599
from zero to N minus one. Okay. And these
numbers do follow certain addition and
58
00:05:16,599 --> 00:05:20,249
multiplication rules and it pretty much
works like a clock face. OK. I chose N is
59
00:05:20,249 --> 00:05:24,569
12 here and, just bear with me, imagine my
clock face goes from zero to eleven
60
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
61
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.
62
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
63
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
64
00:05:44,129 --> 00:05:49,550
of behave this way. Think of addition on
on a clock face. And for the computer
65
00:05:49,550 --> 00:05:54,530
scientists out there or, I mean, everyone
probably knows about that, for a computer
66
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
67
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
68
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
69
00:06:12,719 --> 00:06:18,020
where we we work with somehow related
numbers to these integers mod N. And now
70
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
71
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
72
00:06:30,689 --> 00:06:35,929
that has exactly P elements and really
kind of behaves like the real numbers.
73
00:06:35,929 --> 00:06:39,020
Okay. You can add numbers, you can
subtract numbers. You can divide by
74
00:06:39,020 --> 00:06:42,919
everything but zero. Okay. And this finite
field with P elements works really the
75
00:06:42,919 --> 00:06:46,839
same. It's just a finite set, but
everything is invertable except zero.
76
00:06:46,839 --> 00:06:50,199
Okay. And these are the numbers that we
want to work with and computers can do
77
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
78
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.
79
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
80
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
81
00:07:09,930 --> 00:07:15,580
all you need to know. Okay. So the
cryptographic problem that I want to focus
82
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
83
00:07:20,149 --> 00:07:23,639
going to talk about encryption, nothing.
Let's just focus on this one simple
84
00:07:23,639 --> 00:07:29,529
problem of how do Alice and Bob exchange a
key without anyone else somehow getting
85
00:07:29,529 --> 00:07:33,319
access to that key? And I mean, there are
somehow classical solutions to that. I
86
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
87
00:07:37,050 --> 00:07:41,380
someone to bring the suitcase to Alice. Or
maybe people heard about the thing where I
88
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
89
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
90
00:07:49,009 --> 00:07:53,610
there are countless ways, but we want to
somehow do this in a nice, instantaneous
91
00:07:53,610 --> 00:07:59,979
kind of way using mathematics. Okay. So
this simple problem is what we're going to
92
00:07:59,979 --> 00:08:05,949
focus on. And classically (whatever that
means for now) this has been set off by
93
00:08:05,949 --> 00:08:09,780
Diffie-Hellman. And this is this nice
paper from 1979 the title is New
94
00:08:09,780 --> 00:08:13,849
Directions in Cryptography. So this
already tells you that something important
95
00:08:13,849 --> 00:08:20,259
must be going on and what you somehow
invented there was a way to exchange keys
96
00:08:20,259 --> 00:08:27,179
between two parties using a nice, well-
defined problem. Okay. And how does it
97
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
98
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
99
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,
100
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
101
00:08:50,160 --> 00:08:54,569
written as a power of that element. And
somehow this means it generates it. Right.
102
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
103
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
104
00:09:06,250 --> 00:09:12,199
we do the key exchange? So it's very
symmetrical. So Alice chooses a random A
105
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
106
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
107
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
108
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
109
00:09:33,290 --> 00:09:38,120
sends the big B to Alice. And then
somehow, you know, you have to combine
110
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,
111
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
112
00:09:50,550 --> 00:09:56,379
her own random secret value. And Bob does
the same. And magically from mathematics,
113
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
114
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
115
00:10:11,750 --> 00:10:16,120
write it down mathematically, first of
all, why not teach you a bit about that as
116
00:10:16,120 --> 00:10:21,290
well? So this is this diagram, this
commutative diagram that somehow
117
00:10:21,290 --> 00:10:24,931
represents this key exchange that just
happened. Okay. So Bob and Alice, they
118
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
119
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
120
00:10:35,269 --> 00:10:39,089
and no one else is. And how does that
work? Well, Alice will only compute the
121
00:10:39,089 --> 00:10:43,990
horizontal arrows, so she only raises to
the power of small A because that's her
122
00:10:43,990 --> 00:10:48,540
random secret that only she knows. And Bob
only computes the vertical arrows, so he
123
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
124
00:10:51,800 --> 00:10:57,490
no one else does. And I mean by the
commutativity and the associativity of
125
00:10:57,490 --> 00:11:02,819
exponentiation, they just agree on the
same G to the AB which is which is cool.
126
00:11:02,819 --> 00:11:08,519
And somewhere in there there hides a
problem that we like to call the discrete
127
00:11:08,519 --> 00:11:13,549
logarithm problem and it just happens for
integers mod N if I choose my N
128
00:11:13,549 --> 00:11:17,410
appropriately, I'm not gonna tell you how,
but just believe me if I choose it
129
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
130
00:11:25,670 --> 00:11:30,040
like taking a logarithm, and we call it
the discrete logarithm because it's a
131
00:11:30,040 --> 00:11:33,720
discrete set of numbers instead of the
continuous decimal numbers, what we
132
00:11:33,720 --> 00:11:37,720
started with was this discrete finite set
of numbers and this DLP is hard. Okay.
133
00:11:37,720 --> 00:11:44,780
This is a hard problem for classical
computers. And the best classical generic
134
00:11:44,780 --> 00:11:49,720
algorithm - I'm not gonna talk about
somehow algorithms that specifically
135
00:11:49,720 --> 00:11:54,889
target integers mod N, I'm just going to
talk about generic algorithms for for this
136
00:11:54,889 --> 00:11:59,600
DLP problem. The best algorithm somehow
has run time square root of big N the
137
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
138
00:12:06,709 --> 00:12:13,230
bits. Then solving this takes exponential
time in n, right, because the square root
139
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
140
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
141
00:12:24,980 --> 00:12:33,540
has been a record for factoring and DLPing
over a seven hundred ninety five bit
142
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
143
00:12:39,040 --> 00:12:46,019
them a long time. Okay, so if I remember
correctly, this feed took them 4000 core
144
00:12:46,019 --> 00:12:51,120
years on a two point one gigahertz
computer. I mean, that's still 4000 core
145
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
146
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.
147
00:13:00,410 --> 00:13:05,399
But again, you can make N pretty big,
bigger than anything being able to solve
148
00:13:05,399 --> 00:13:10,629
this anymore. But. Okay, so there is a
quantum algorithm for this and this is
149
00:13:10,629 --> 00:13:16,279
this other paper from 95. Peter Shor. So
he thought of this algorithm that solves
150
00:13:16,279 --> 00:13:21,930
the DLP in polynomial time. Okay, now
remember our big N we took about two to
151
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
152
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
153
00:13:32,730 --> 00:13:37,749
a thousand cube is still not that big.
Okay. So there is a good algorithm that
154
00:13:37,749 --> 00:13:41,519
assumes the existence of a quantum
computer. I mean as outlandish that might
155
00:13:41,519 --> 00:13:47,600
sound, but still this algorithm in theory
breaks the DLP. Okay. So I don't know,
156
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
157
00:13:52,319 --> 00:13:56,910
quantum computer eventually that somehow
runs this thing, okay, DLP's broken,
158
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
159
00:14:05,350 --> 00:14:10,899
cryptography for which we don't know a
quantum algorithm. Okay. Or for which we
160
00:14:10,899 --> 00:14:15,170
expect there won't be a quantum algorithm
ever. There are a few candidates. Again,
161
00:14:15,170 --> 00:14:21,930
there's this zoo. Lattices, codes, this
long word, and isogenies. Okay. Now what I
162
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
163
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.
164
00:14:33,970 --> 00:14:37,300
There was this other word that started
with elliptic curve isogenies, so probably
165
00:14:37,300 --> 00:14:40,860
I should tell you about what is an
elliptic curve or give you a reminder if
166
00:14:40,860 --> 00:14:46,379
you've seen this before. So I look at this
equation in two variables and two
167
00:14:46,379 --> 00:14:51,529
constants, the variables X and Y, my
constants are A and B. And the equation is
168
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
169
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
170
00:15:02,920 --> 00:15:06,990
course, they're going to look different
somehow for the different possible numbers
171
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,
172
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
173
00:15:14,760 --> 00:15:20,730
this again over our finite field, okay,
because we like we like this discreteness.
174
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
175
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
176
00:15:30,790 --> 00:15:36,519
this. And actually it extends infinitely
far on the right side, up and down. Okay.
177
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
178
00:15:41,470 --> 00:15:45,540
finite field, and I chose one with one
hundred and one elements, it looks like
179
00:15:45,540 --> 00:15:50,850
the set of points. Okay. So elliptical
curves look differently over different
180
00:15:50,850 --> 00:15:57,510
fields. But that's fine. That's fine.
Okay. Now, quick reminder of why people
181
00:15:57,510 --> 00:16:01,550
like elliptic curves. So there is
something called the point addition law.
182
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
183
00:16:05,490 --> 00:16:10,350
not really addition in the sense of
numbers. There is somehow a law that I have
184
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
185
00:16:16,499 --> 00:16:21,220
on this curve? Well, you take these two
points, you put a line through it, and
186
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
187
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
188
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
189
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
190
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
191
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.
192
00:16:56,110 --> 00:17:00,649
And that works. Okay. I can add points, I
can subtract points. There will be the
193
00:17:00,649 --> 00:17:05,370
inverse. So this kind of like X like
integers mod N when you only consider
194
00:17:05,370 --> 00:17:09,559
addition, kind of, kind of, it's not
really the same, but you can also single
195
00:17:09,559 --> 00:17:16,770
out the special point O like beautiful O
we call the origin, whatever that is. And
196
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
197
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
198
00:17:25,120 --> 00:17:30,630
zero. Okay. So there's something like a
zero. And you can also multiply points,
199
00:17:30,630 --> 00:17:34,809
right. I mean what is multiplication, it's
just repeated addition. So in brackets n,
200
00:17:34,809 --> 00:17:38,919
this is what I write for point
multiplication, just add the point n times
201
00:17:38,919 --> 00:17:43,440
to itself. Okay. So there's nothing fancy
going on here. So you can somehow add
202
00:17:43,440 --> 00:17:49,510
points. You can multiply points. That's
pretty cool. And if you look closer, you
203
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
204
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
205
00:18:00,600 --> 00:18:08,130
zero. Okay. And this set for the
mathematically inclined people among us I
206
00:18:08,130 --> 00:18:12,500
know say this is somehow the N-torsion of
an elliptic curve, whatever that means.
207
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
208
00:18:16,370 --> 00:18:23,520
additive integers mod n - like two copies
of it. Okay. And now this is where the
209
00:18:23,520 --> 00:18:26,980
term super singular comes from. One of the
definitions. This is not the only
210
00:18:26,980 --> 00:18:30,530
definition, but this is one of them. If
you look at the elliptic curve, not over
211
00:18:30,530 --> 00:18:36,029
the reals, okay, or whichever numbers, but
over this finite fields. And if you look
212
00:18:36,029 --> 00:18:41,980
at the torsion, the P-torsion, then this
behaves differently for different types of
213
00:18:41,980 --> 00:18:45,279
curves. Okay. The P-torsion is either
empty, then we call the curve super
214
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
215
00:18:50,400 --> 00:18:55,149
ordinary. Okay. It's not really important
to know what that means. It just means
216
00:18:55,149 --> 00:18:59,980
that there is a distinction for curves
somehow that's somehow ingrained
217
00:18:59,980 --> 00:19:07,730
mathematically deep down there. And
because this E N torsion is somehow two
218
00:19:07,730 --> 00:19:13,809
copies of of integers mod N, additive
integers mod N, I can generate it by
219
00:19:13,809 --> 00:19:17,539
taking linear combinations of two points,
say P and Q, and these are like the
220
00:19:17,539 --> 00:19:21,679
generators we saw earlier. Right. But
these are not additive generators instead
221
00:19:21,679 --> 00:19:26,831
of somehow exponential generators. But it,
everything behaves kind of similar. And
222
00:19:26,831 --> 00:19:30,240
now you can really use this to do
cryptography already. If you wanted to
223
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
224
00:19:35,899 --> 00:19:40,510
problem again that the DLP in there,
there's Shor's algorithm again. Right. So
225
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
226
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
227
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
228
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
229
00:20:10,710 --> 00:20:16,919
something similar with an elliptic curve.
if you can somehow take part of this
230
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
231
00:20:24,029 --> 00:20:28,609
turns out this is mathematically well-
defined and it gives you another elliptic
232
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
233
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
234
00:20:42,840 --> 00:20:46,500
comes along with this construction. And
this is what we call the isogeny. This is
235
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
236
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
237
00:21:00,769 --> 00:21:07,140
another curve. And this map is kind of
special because it behaves in a nice way
238
00:21:07,140 --> 00:21:12,200
and it plays nicely with the structure
that's already ingrained in our curve.
239
00:21:12,200 --> 00:21:17,840
Namely, I can either add two points on my
starting curve and send it through that
240
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
241
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
242
00:21:31,600 --> 00:21:35,539
behaves nicely with point addition. That's
pretty nice, just as a side note. So this
243
00:21:35,539 --> 00:21:42,140
map is special. So this is just the
remainder of what I said: Adding points on
244
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
245
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
246
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
247
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
248
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
249
00:22:12,470 --> 00:22:18,240
to the isogeny that are sent to the zero
on the other curve. And in written
250
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
251
00:22:25,230 --> 00:22:34,512
this kernel for my isogeny, that I started
out with somehow recovers this part of the
252
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
253
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
254
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
255
00:22:54,270 --> 00:22:59,320
again. So there are two ways to represent
this map. We can think of a subgroup -
256
00:22:59,320 --> 00:23:06,630
this G - or we can think of the map. And
ultimately somehow there is a correspondence
257
00:23:06,630 --> 00:23:12,000
between the various subgroups for
different N and isogenies that are somehow
258
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
259
00:23:15,900 --> 00:23:20,760
are going out and then they're going to
reach other electric curves maybe. And
260
00:23:20,760 --> 00:23:27,020
these notions can be used interchangeably.
So somehow there is a correspondence. And
261
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
262
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
263
00:23:40,210 --> 00:23:43,899
compute these maps. So right now, this is
just general abstract nonsense. I didn't
264
00:23:43,899 --> 00:23:47,470
tell you anything of how to compute these
things. I just told you there are some
265
00:23:47,470 --> 00:23:50,600
more correspondences. But I mean, what
does that even mean? Right. It's useless
266
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
267
00:23:57,250 --> 00:24:00,409
these things, there are formulas, people
have worked on this. But somehow the cost
268
00:24:00,409 --> 00:24:08,000
grows if I enlarge N. So really, in
practice, for applications, I want to choose
269
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
270
00:24:13,670 --> 00:24:19,250
the supersingular curves for which I can some-
how control or choose the possible ends very
271
00:24:19,250 --> 00:24:27,091
very easily. So this is the reason why we
reconsider supersingular curves. Now I can
272
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
273
00:24:33,699 --> 00:24:39,559
and 3 being possible. So this is the
reason why we choose supersingular ones.
274
00:24:39,559 --> 00:24:45,080
There's some theory which is not
interesting for you, but it's important
275
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
276
00:24:52,350 --> 00:24:57,490
isogenies that we like. But there is
another important reason and this is the
277
00:24:57,490 --> 00:25:01,450
reason that actually makes it
interesting for cryptography. So what I
278
00:25:01,450 --> 00:25:07,919
can do is: I start with an arbitrary
curve, and this just might not be a
279
00:25:07,919 --> 00:25:12,730
supersingular one, just any curve and say I
consider all the outgoing two isogenies if
280
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,
281
00:25:19,299 --> 00:25:24,930
from E1, I can again consider all the
outgoing isogenies, and so on and so
282
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
283
00:25:28,970 --> 00:25:36,860
the vertices of my graph are elliptic curves
and the edges are isogenies. So somehow
284
00:25:36,860 --> 00:25:44,260
behind the scenes there is this graph
hidden. Now, it turns out that if you do
285
00:25:44,260 --> 00:25:48,580
this for a supersingular elliptic curve -
and I generated this yesterday for you,
286
00:25:48,580 --> 00:25:52,970
so this is one possible graph - I can
remember which prime I took. But here you
287
00:25:52,970 --> 00:25:57,350
can see all the ellipses are ellipitic
curves and all the edges between them are
288
00:25:57,350 --> 00:26:03,330
2 isogenies. So this is an example of a
supersingular 2-isogeny graph - okay, this
289
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
290
00:26:11,169 --> 00:26:17,020
and so forth. There are many many graphs
hidden. But why is the supersingular graph
291
00:26:17,020 --> 00:26:20,900
specific and important? Well, it turns out
that somehow the supersingular one is
292
00:26:20,900 --> 00:26:27,440
connected, and it's what we call a
Ramanujan graph. I'm going to explain
293
00:26:27,440 --> 00:26:33,740
this in a second. And as a bonus, for
implementation purposes, it turns out that
294
00:26:33,740 --> 00:26:39,559
you can do all your implementation in
arithmetics in the finite field with p^2
295
00:26:39,559 --> 00:26:45,409
elements. This is nice. So I'm just gonna
say that if you don't consider
296
00:26:45,409 --> 00:26:49,200
supersingular curves and you go along
these graphs, then what's going to happen
297
00:26:49,200 --> 00:26:54,330
is that somehow this "field of
definition", what we call it, could grow
298
00:26:54,330 --> 00:26:59,320
for you to be able to go further, but that
would suck for implementation. But
299
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
300
00:27:04,279 --> 00:27:10,300
implementation. So somehow magically many
many things happen here that are benefiting us.
301
00:27:10,300 --> 00:27:15,460
And again, why is it nice that this is a
Ramanujan graph? A Ramanujan graph has
302
00:27:15,460 --> 00:27:21,090
certain optimal expansion properties. This
means that if I start from a random point
303
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
304
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
305
00:27:38,130 --> 00:27:43,580
is good for cryptography. Because you only
need to take log many steps to somehow
306
00:27:43,580 --> 00:27:50,120
randomize yourself in that graph. And this
is what this could look like. I started at
307
00:27:50,120 --> 00:27:55,669
that red ellipses over there. This was my
starting point. And then I generated a few
308
00:27:55,669 --> 00:28:01,919
random walks, and the blue points are
where I got placed. This might not prove
309
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.
310
00:28:09,099 --> 00:28:17,080
So, it's good for cryptography, but there
are other reasons, so supersingular elliptic
311
00:28:17,080 --> 00:28:22,400
curves somehow I can actually compute how
many of these curves I will have in my
312
00:28:22,400 --> 00:28:26,540
graph. This is another reason to be
looking at these things. Because if I
313
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
314
00:28:30,740 --> 00:28:35,179
about the security - but at least for
supersingular ones, I can see they're
315
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
316
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
317
00:28:47,660 --> 00:28:51,830
something about the cryptographic
strength, right? I can make M big and then
318
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
319
00:28:54,620 --> 00:28:58,669
n-length walks and then it places you
randomly in there and the whole graph is
320
00:28:58,669 --> 00:29:04,320
about 2^n elements. And then I can say
something about the expected runtime of
321
00:29:04,320 --> 00:29:09,779
algorithms. So this is another reason why
we want to consider supersingular curves:
322
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
323
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
324
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
325
00:29:27,549 --> 00:29:30,700
possible, but we don't even care about
those because this is what gives us the
326
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
327
00:29:38,510 --> 00:29:43,759
implementation fast. I can tell you how
many vertices are in the graph: about
328
00:29:43,759 --> 00:29:48,840
p/12. And again, such that the graph for
mixing properties that are useful for
329
00:29:48,840 --> 00:29:52,369
cryptographic applications. So because I
want to use this ultimately for
330
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
331
00:29:59,850 --> 00:30:07,159
the graph has about 2^n vertices - so
exponentially many vertices. And it turns
332
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
333
00:30:16,240 --> 00:30:23,130
don't have good quantum algorithms. So one
hard problem is this: I take two super
334
00:30:23,130 --> 00:30:28,630
singular elliptic curves, so I just give you
two random curves in this graph and ask
335
00:30:28,630 --> 00:30:33,120
you to find a nice arch in the path
between those isognies, or three
336
00:30:33,120 --> 00:30:37,880
isogenies. And it turns out that this just
doesn't have a good quantum algorithm. So
337
00:30:37,880 --> 00:30:42,750
classically, I mean the numbers are super
important here, but classically the
338
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
339
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
340
00:30:52,679 --> 00:30:58,000
is that there is no polynomial time
algorithm compare to ideal p that we
341
00:30:58,000 --> 00:31:03,060
started with. So if I make this p very large
and your quantum computer, your
342
00:31:03,060 --> 00:31:07,910
hypothetical quantum computer, will
probably not solve this. Okay, so that's
343
00:31:07,910 --> 00:31:14,960
cool. So how do we do key exchange? I
start with a supersingular elliptic curve E,
344
00:31:14,960 --> 00:31:21,350
where I chose my prime p such that two and
three isogenies are possible. And then
345
00:31:21,350 --> 00:31:26,019
Alice - earlier I remember she chose a
random number a - but now Alice will
346
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
347
00:31:35,539 --> 00:31:40,940
for computing the nice isogeny. And again,
this is a very symmetrical key exchange,
348
00:31:40,940 --> 00:31:45,459
except that now Bob won't use the same
generator but Bob will use the 3
349
00:31:45,459 --> 00:31:50,830
isogenies. So Bob will choose a random
subgroup B, and then he will compute E mod
350
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
351
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
352
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
353
00:32:12,129 --> 00:32:16,419
subgroups again. And it turns out that the
elliptic curve that they find is going to
354
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
355
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.
356
00:32:32,610 --> 00:32:36,929
And then Alice will compute these red
steps, which correspond to taking a
357
00:32:36,929 --> 00:32:42,030
subgroup. So Alice will compute these red
steps for her secret subgroup and she will
358
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
359
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
360
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
361
00:32:57,600 --> 00:33:02,039
select a random subgroup, compute the
secret path and Bob will end up in the
362
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
363
00:33:06,549 --> 00:33:12,039
curve to Alice. And then Alice will
consider the blue curve in the 2-graph. So
364
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
365
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
366
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
367
00:33:30,390 --> 00:33:34,335
there. Again, he computes the path and
then ends up at the green curve. And it
368
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
369
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
370
00:33:45,960 --> 00:33:54,101
key using the supersingular isogeny graph.
That's the whole magic. And again, let's
371
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
372
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
373
00:34:07,730 --> 00:34:14,760
right corner. And SIDH looks very similar:
Alice and Bob start with this common curve
374
00:34:14,760 --> 00:34:22,720
E in the upper left corner. Again, Alice
computes only horizontal arrows because
375
00:34:22,720 --> 00:34:27,750
she knows her secret group A, and Bob only
computes the vertical arrows because only
376
00:34:27,750 --> 00:34:34,490
he knows his secret group B. And again,
they both end up in the lower right
377
00:34:34,490 --> 00:34:40,110
corner, where they define the shared key.
But now in this case, the shared key is
378
00:34:40,110 --> 00:34:44,860
not an element to the a^(ab), but elliptic
curve. But again, there's a mathematical
379
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
380
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
381
00:34:59,660 --> 00:35:06,520
example of a post-quantum cryptography
scheme that we have today. And now
382
00:35:06,520 --> 00:35:13,290
let me finish with a quick conclusion. I
showed you this "zoo": There are several
383
00:35:13,290 --> 00:35:18,840
candidates somehow for post-quantum
cryptography. And among them are some
384
00:35:18,840 --> 00:35:26,090
schemes based on supersingular elliptic
curve isogenies, and we've seen that we
385
00:35:26,090 --> 00:35:30,460
know some hard problems involving these
isogenies that are hard for quantum
386
00:35:30,460 --> 00:35:40,511
computers, which makes this one possible
scheme for a quantum computer world. And
387
00:35:40,511 --> 00:35:44,950
probably I should say that we don't
envision a world here where we users like
388
00:35:44,950 --> 00:35:49,960
me or you are in possession of quantum
computers. Probably, what we think about
389
00:35:49,960 --> 00:35:55,210
is that state actors are in positions of
quantum computers. So this is even more
390
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
391
00:36:01,500 --> 00:36:05,290
Diffie-Hellman-like key exchange using
these isogenies. But - this is what I
392
00:36:05,290 --> 00:36:10,410
didn't tell you about in his talk - there
are also schemes for signature-based
393
00:36:10,410 --> 00:36:15,950
isogenies, there is this scheme for key-
encapsulation-based isogenies. So
394
00:36:15,950 --> 00:36:22,680
there are other possible candidates for
other cryptographic building blocks based
395
00:36:22,680 --> 00:36:29,110
on isogenies and these hard problems. And
if you're super interested about this, you
396
00:36:29,110 --> 00:36:36,660
can either ask me or come to our assembly
and if you like reading scientific papers,
397
00:36:36,660 --> 00:36:39,900
papers about such isogenies and
cryptography in general, you can find this
398
00:36:39,900 --> 00:36:45,240
on the eprint archive. So this is a web
page where people post pre-prints about
399
00:36:45,240 --> 00:36:50,370
their papers and there's a huge collection
about, among of them, isogeny papers. So
400
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
401
00:36:58,380 --> 00:37:01,440
like to thank you all for your attention.
402
00:37:01,440 --> 00:37:14,870
*applause*
403
00:37:14,870 --> 00:37:22,600
Herald Angel: Is there any question? OK, I
got the Signal Angel there, doing some
404
00:37:22,600 --> 00:37:27,640
Morse code?
Microphone 1: Yes. Can you recommend any
405
00:37:27,640 --> 00:37:33,280
literature for the theoretical background?
naehrwert: The theoretical background?
406
00:37:33,280 --> 00:37:41,510
There are a few papers that are nice.
Okay. The question again was literature
407
00:37:41,510 --> 00:37:46,050
about theoretical background. And yes,
there are a few papers that are giving
408
00:37:46,050 --> 00:37:53,180
some nice, even theoretically involved
summaries about the background. And your
409
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,
410
00:38:00,940 --> 00:38:07,400
or 'SIDH', and look at the papers that
say, maybe, 'A Short Introduction to
411
00:38:07,400 --> 00:38:11,380
Isogenies' or something like that. I mean,
you will find them if you search for them.
412
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
413
00:38:17,500 --> 00:38:22,590
thanks for him - So there is a very recent
paper by Craig Costello, also somewhat
414
00:38:22,590 --> 00:38:26,670
titled 'A Short Introduction', something
like that. So this is also maybe a good
415
00:38:26,670 --> 00:38:30,830
source for you to look at.
Herald Angel: Um, yeah, 'Isogenies for
416
00:38:30,830 --> 00:38:32,730
Beginners'.
naehrwert: 'Isogenies for Beginners'.
417
00:38:32,730 --> 00:38:35,790
Thank you.
*audience laughing*
418
00:38:35,790 --> 00:38:44,500
Microphone 2: Hello. Yeah. So you've used
elleptic curve as an algebraic group,
419
00:38:44,500 --> 00:38:54,700
right, to compute these isogeny graphs.
Why do you use elliptic curves - what's
420
00:38:54,700 --> 00:39:02,770
the properties of elliptical curves as a
group? So, could you use any group to
421
00:39:02,770 --> 00:39:10,980
compute these graphs and could you use
these as the basis for your scheme or your
422
00:39:10,980 --> 00:39:14,890
key exchange scheme?
naehrwert: Okay, so the question was why
423
00:39:14,890 --> 00:39:21,280
use elliptical curves and the group
structure that the impose to look at
424
00:39:21,280 --> 00:39:26,220
isogeny graphs involving elliptical curves
and whether I could use other groups. And
425
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
426
00:39:34,001 --> 00:39:40,650
my backup slide, which gives you SIDH in
its full glory - you consider some extra
427
00:39:40,650 --> 00:39:46,170
information being sent, namely these
generators from my group and actually the
428
00:39:46,170 --> 00:39:51,700
same commutative diagram for SIDH. You
could, in theory, compute using another
429
00:39:51,700 --> 00:39:57,670
group as well, that has the proper
subgroup structure, but the graph that you
430
00:39:57,670 --> 00:40:03,910
will find is probably not going to be
interesting. I mean it's really somehow
431
00:40:03,910 --> 00:40:09,100
that Righello property that makes the
graph interesting for cryptography. But
432
00:40:09,100 --> 00:40:15,020
yes, in theory, the SIDH commutative
diagram you could also compute for other
433
00:40:15,020 --> 00:40:20,720
groups, yes.
Microphone 2: OK.
434
00:40:20,720 --> 00:40:28,910
Microphone 3: Uh... How good are classical
algorithms that tried to reverse that SIDH
435
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
436
00:40:37,010 --> 00:40:39,931
secure.
naehrwert: Yes. So the question was: How
437
00:40:39,931 --> 00:40:46,980
good are classical algorithms? And again,
I said, I think the runtime for those is
438
00:40:46,980 --> 00:40:52,950
squared of p. And this tells you how big
you have to choose B.
439
00:40:52,950 --> 00:40:59,160
Microphone 3: And how confident are you
that this really is hard for quantum
440
00:40:59,160 --> 00:41:03,510
computers as well?
naehwert: Well, how confident am I that
441
00:41:03,510 --> 00:41:07,020
this is really hard for quantum
computers? So first of all, cryptography
442
00:41:07,020 --> 00:41:10,740
is all about confidence, right? So someone
proposes a problem, this problem gets
443
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
444
00:41:15,350 --> 00:41:19,810
pretty, pretty confident this is good. And
maybe if the NSA doesn't tell you anything
445
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
446
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
447
00:41:35,240 --> 00:41:40,980
time can answer, right?
Microphone 4: Yeah. Is it possible to
448
00:41:40,980 --> 00:41:47,321
prove that no polynomial-time algorithms
for the isogenies problems **can** exist
449
00:41:47,321 --> 00:41:51,810
for a quantum computer?
naehrwert: Yeah, that's a good question.
450
00:41:51,810 --> 00:41:59,610
How do you prove that no algorithm exists?
This brings us into territories, like ...
451
00:41:59,610 --> 00:42:06,380
Yeah. I don't know. Yeah.
No. Let's not do that.
452
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
453
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
454
00:42:20,850 --> 00:42:25,600
algorithm is hard for classic computers.
Right? So, I'm guessing you're saying that
455
00:42:25,600 --> 00:42:31,340
**intuitively** it feels hard, which, you
know, is the same intuition I have about
456
00:42:31,340 --> 00:42:37,650
e.g. factoring in. So, you mention there's
multiple candidates for post-quantum
457
00:42:37,650 --> 00:42:44,120
cryptography, and they all intuitively
feel hard somehow. Do you know if this
458
00:42:44,120 --> 00:42:48,480
specific candidate, would this be your
horse in a race? Is there anything about
459
00:42:48,480 --> 00:42:54,320
this specific way that you think would be
the best fit for post-quantum
460
00:42:54,320 --> 00:42:59,310
cryptography?
naehrwert: Okay. Your opinion is very
461
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
462
00:43:03,410 --> 00:43:07,400
other questions: How do you trust
something like that? Again, people do
463
00:43:07,400 --> 00:43:11,950
crypto analysis for 40 years or whatever.
And then you say, oh, no one found
464
00:43:11,950 --> 00:43:16,030
anything - it's probably hard, right? But
it hasn't been an exact 40 years. You
465
00:43:16,030 --> 00:43:21,480
cannot say that. Indeed these things are
relatively new. And personally, I'm not
466
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
467
00:43:28,430 --> 00:43:33,060
reason for looking into these things
really is more a mathematical curiosity,
468
00:43:33,060 --> 00:43:38,500
because I think these things are
beautiful. And the cryptography that
469
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
470
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
471
00:43:51,180 --> 00:43:56,140
whatever.
Microphone 2: (Yeah. I am.) You showed or
472
00:43:56,140 --> 00:44:01,660
said you think it's hard for the classical
way and for the quantum cryptography way.
473
00:44:01,660 --> 00:44:08,830
I think I just read a paper last year
about a combined way in classical and
474
00:44:08,830 --> 00:44:14,261
quantum cryptography combined, which
outperforms either one of those ways. Do
475
00:44:14,261 --> 00:44:23,820
you think this could also be relevant or
gonna make this one way to put in
476
00:44:23,820 --> 00:44:27,600
computable in polynomial time?
naehrwert: Are you talking about an
477
00:44:27,600 --> 00:44:32,640
algorithm that somehow combines a
classical step and a quantum step to break
478
00:44:32,640 --> 00:44:33,900
this?
Microphone 2: Yes.
479
00:44:33,900 --> 00:44:39,390
naehwert: Yeah well, most algorithms that
we say use a quantum computer involve a
480
00:44:39,390 --> 00:44:43,330
classical part anyways. If you think about
Shor's algorithm, there's a classical part
481
00:44:43,330 --> 00:44:49,600
and a quantum computer part. So I'm not
sure which algorithm you read about, but
482
00:44:49,600 --> 00:44:53,560
I'm sure that somehow all the quantum
algorithms involve a classical part
483
00:44:53,560 --> 00:44:58,690
implicitly anyways.
Herald: Signal Angel?
484
00:44:58,690 --> 00:45:03,400
Microphone 3: Yeah. Can you please name
the mentioned contestants in the list
485
00:45:03,400 --> 00:45:10,400
'Challenge-based Isogenies'?
naehrwert: So there is SSIKE, I believe:
486
00:45:10,400 --> 00:45:16,170
supersingular isogeny key encapsulation,
but actually I don't really follow the
487
00:45:16,170 --> 00:45:22,080
NIST thingy closely, so I actually
couldn't even name all the names that are
488
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
489
00:45:27,440 --> 00:45:33,190
is also a classification of the contenders
into this view. So they will tell you
490
00:45:33,190 --> 00:45:37,180
which contenders are based on lattices and
which contenders are based on codes and
491
00:45:37,180 --> 00:45:41,400
which ones are somehow based on isogenies.
But off the top of my head, actually, I
492
00:45:41,400 --> 00:45:49,990
don't even know. Sorry.
Microphone 1: So if I got everything
493
00:45:49,990 --> 00:45:56,730
correctly, though, those isogenies are
group homomorphisms between the elliptic
494
00:45:56,730 --> 00:46:03,580
curves and the factor group of the
elliptic curve by g. And which has kernel
495
00:46:03,580 --> 00:46:05,040
g again.
naehrwert: Yes.
496
00:46:05,040 --> 00:46:10,170
Microphone 1: And you said that finding
the isogeny path in the graph is rather
497
00:46:10,170 --> 00:46:15,720
difficult. But wouldn't the real
difficulty rather be finding the subgroups
498
00:46:15,720 --> 00:46:20,290
G - because a group homomorphism between
the elliptic curve and the factor group
499
00:46:20,290 --> 00:46:23,450
with kernel g is simply the canonical
protection.
500
00:46:23,450 --> 00:46:29,500
naehrtwert: Exactly. So I see you are
mathematically trained, which is very nice
501
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
502
00:46:34,140 --> 00:46:41,440
look at the slide actually, the secrets
are these alphas and betas, which somehow
503
00:46:41,440 --> 00:46:46,420
determine the subgroup. And yes, finding
those isogeny path is equivalent to
504
00:46:46,420 --> 00:46:50,240
finding the alpha, somehow, that generates
this group. And as you said correctly,
505
00:46:50,240 --> 00:46:56,670
finding the isogeny path is somehow
finding this group. But it's just
506
00:46:56,670 --> 00:47:00,940
restating the problem. But it's still hard
somehow to find this group. Yeah.
507
00:47:00,940 --> 00:47:05,430
Microhone 1: All right. Thanks.
naehrwert: Thank you. Very cool.
508
00:47:05,430 --> 00:47:08,940
Microphone 2: Yeah, thank you for the
great talk. So, can you play this game a
509
00:47:08,940 --> 00:47:15,270
little bit further? I mean, can you choose
higher-dimensional abelian varieties to
510
00:47:15,270 --> 00:47:19,440
make it even more secure? Or is it just
absolutely inaccessible? I mean, from the
511
00:47:19,440 --> 00:47:24,160
computation perspective, the choice of
field of definition is difficult, for
512
00:47:24,160 --> 00:47:26,430
example, so...
naehrwert: Okay, so the question was on
513
00:47:26,430 --> 00:47:30,510
whether you can use higher-dimensional
abelian varieties and maybe for the people
514
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
515
00:47:35,760 --> 00:47:41,270
elliptic curves, somehow have a dimension
1 attached to them. And the question was,
516
00:47:41,270 --> 00:47:45,720
can you somehow look at dimension 2,
dimension 3 or higher? And actually, back
517
00:47:45,720 --> 00:47:51,210
in the days when people were thinking
about the DLP problem on the points of
518
00:47:51,210 --> 00:47:55,570
elliptic curves that I mentioned briefly,
people had the idea of maybe using
519
00:47:55,570 --> 00:48:01,231
dimension 2 or dimension 3. But it turns
out, that the DLP problem actually, at
520
00:48:01,231 --> 00:48:06,170
some point, gets easier in higher
dimensions. So, classically if you look at
521
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,
522
00:48:10,250 --> 00:48:14,570
you can look at isogenies between
dimension-2 and dimension-3 ones. And
523
00:48:14,570 --> 00:48:17,860
actually the problem that arises there -
and this makes elliptical curves very
524
00:48:17,860 --> 00:48:23,260
special - is that we can compute isogenies
rather efficiently for elliptical curves
525
00:48:23,260 --> 00:48:27,510
because of Velu's formulas. Okay. So
this gives us a very direct means of
526
00:48:27,510 --> 00:48:32,670
computing D, but it actually gets hard as
the dimension grows. For example, for
527
00:48:32,670 --> 00:48:40,090
dimension 2 already, the only isogenies
that I am able to efficiently compute are
528
00:48:40,090 --> 00:48:45,890
2- and 3-isogenies. So there are some
packages out there that can compute higher
529
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
530
00:48:50,850 --> 00:48:55,810
even harder. And then there is another
thing that comes into play. So dimension-2
531
00:48:55,810 --> 00:49:00,300
varieties, they all arise from what we
call hyperelliptic curves. But if we look
532
00:49:00,300 --> 00:49:07,260
at dimension-3s and higher, then sometimes
you land at a point in your graph that
533
00:49:07,260 --> 00:49:11,600
does not come from a hyperelliptic curve
anymore. So there is another complication.
534
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
535
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
536
00:49:24,260 --> 00:49:31,440
something that's good in practice.
Microphone 2: Can you use this scheme to
537
00:49:31,440 --> 00:49:35,650
implement a fully homomorphic encryption
scheme? Or is it already?
538
00:49:35,650 --> 00:49:40,860
naehrwert: Uhhh... No. No.
*laughing*
539
00:49:40,860 --> 00:49:45,440
naehrwert: Yeah, no fully homomorphic
encryption is somehow a pipe dream, but I
540
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
541
00:49:51,030 --> 00:49:55,840
the sum of the ciphered texts and have a
second operation, namely you should be
542
00:49:55,840 --> 00:50:00,120
able to multiply ciphertexts and get the
multiplication of two ciphertexts. But we
543
00:50:00,120 --> 00:50:07,490
didn't even talk about encryption.
Microphone 2: Yeah. Another question: Is
544
00:50:07,490 --> 00:50:12,110
there any crypto primitive used in the
isogeny approach that cannot be Stark-
545
00:50:12,110 --> 00:50:16,020
reduced to finding a hidden
subgroup in an abelian group?
546
00:50:16,020 --> 00:50:18,870
naehrwert: Could you repeat the
question, please?
547
00:50:18,870 --> 00:50:22,960
Microphone 2: Is there any crypto
primitive used in the isogeny approach
548
00:50:22,960 --> 00:50:28,560
that cannot be Stark-reduced to finding a
hidden subgroup in an abelian group?
549
00:50:28,560 --> 00:50:36,860
naehrwert: Okay. I think this question
tries to connect back to the hidden shift
550
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
551
00:50:44,110 --> 00:50:47,670
to answer that question now without
talking to the person that actually asked
552
00:50:47,670 --> 00:50:55,130
it because it's a bit vague.
So I'm sorry about that.
553
00:50:55,130 --> 00:50:59,050
Microphone 3: How do you send an
elliptical over the wire?
554
00:50:59,050 --> 00:51:02,680
naehrwert: Yeah, maybe I should answer
that actually. So we saw the
555
00:51:02,680 --> 00:51:09,000
parameterization of the curve that had
these coefficients A and B. But what
556
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
557
00:51:14,510 --> 00:51:19,770
an invariant in mathematics and for an
elliptical curve, this is called a
558
00:51:19,770 --> 00:51:25,670
j-invariant and it's a single integer
which determines this elliptical curve
559
00:51:25,670 --> 00:51:29,600
uniquely. So if I want to send an
elliptical curve, I can simply send you
560
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
561
00:51:34,600 --> 00:51:40,190
somehow recompute it just from the single
value. So it's actually quite a compact
562
00:51:40,190 --> 00:51:45,970
representation which makes
this also interesting. Yeah.
563
00:51:45,970 --> 00:51:49,260
Herald: I guess this is all. Thank you.
564
00:51:49,260 --> 00:51:54,860
*applause*
565
00:51:54,860 --> 00:51:58,800
*postroll music*
566
00:51:58,800 --> 00:52:23,000
subtitles created by c3subtitles.de
in the year 2020. Join, and help us!