36C3 - (Post-Quantum) Isogeny Cryptography

36C3 preroll music
Applause

naehrwert: Yeah. Thank you for the
audience and thanks that you came. Thanks

for the Congress for giving me the
opportunity to be here tonight, to be able

to tell you a bit about post quantum
cryptography, a bit about as isogenies. I

mean, just educate the people a bit about
what that means, even, because I'm not too

sure how many of you heard about that
before. Yeah, let's just jump right in. So

my day job is being a mathematics PhD
student at an undisclosed university. You

can ask me in private if you're
interested. So previously I did physics. I

was also or maybe I'm still a bit active
in the console hacking scene. And if

you're interested about that shameless
plug, you can find us at Nintenbros

Assembly later. You can ask us all about
our somehow console hacking endeavors. But

enough about that. So I brought you some
pictures, screenshots of websites. So I

don't know if you have seen the chatter on
social media and the blogs here recently

about that Google paper on quantum
supremacy. So there is a Nature article

about that beyond quantum supremacy. And
there is a Verge article that Google

confirms quantum supremacy and
breakthrough, whatever that means. There

is Google's own blog post about it. Notice
there are always these shiny pictures of

these huge tubs filled with helium where
they house these quantum computers. So

supremacy means the state or condition of
being superior to all others in authority,

power, or status. So calling something
quantum supremacy, I mean, that screams

something being pretty amazing. But what
actually does this mean for us? What does

it mean for cryptography? And I think I
can relieve you all about from from maybe

some fears that you had for us in
practice. Maybe today it doesn't really

mean anything yet. So for cryptography
none of our underlying assumptions,

whatever it means for now, are being
actively broken yet as we know or that we

know of. But in theory, they are broken.
Okay. And because they're only broken in

theory, that's pretty good. So we can
still blame the designers and implementers

of whatever we cook up for when things go
wrong. So that's nice, too. But as I

already wrote in the abstract a bit for
this talk, we should be, somehow, better

be safe than sorry. So instead of somehow
waiting until the point of where quantum

computers somehow become feasible to break
our cryptography, we should probably

research it today. It's a bit with the
climate change, right? Suppose it's right

to save our climate today instead of
waiting until it's too late. So if we're

going to be reborn to do the same for
cryptography. There are also three

upcoming talks I want to advertise here a
bit. I think I don't remember the days,

but descriptions look pretty interesting.
So I'm going to leave that up for a few

seconds. There is one called Provable
Insecurity, one called Cryptography

Demystified and one about high assurance
cryptography software. I'm sure this is

gonna be interesting. Okay, let's return
back to what I want to talk about. So

there's something I chucklingly call the
Post-Quantum Cryptography Zoo. There are a

few buzzwords up there. You don't really
have to know what they mean. I'm just

going to say them out loud. Lattices,
codes, multivariate polynomial systems.

That's also a bit of a mouthful. And hash
based cryptography. And there is the one

that I want to briefly talk about tonight
called supersingular elliptic curve

isogenies. OK, so this is the stuff that I
really like. Isogenies, they are great.

And now I'm going to tell you why they're
so great. All right. So I don't know how

many of you have a mathematics background.
Maybe I can do a test. Can people raise

their hands where if they have some formal
training in, say, algebra? Yeah. Okay. So

that's pretty good. So I'm just gonna tell
you some something about it. There are

decimal numbers. This is Pi. Then there
are rational numbers somehow the are, one

half, one third and so on and so forth.
Then there are integers from minus

infinity to plus infinity and they follow
nice whole steps. But for working with

those numbers and for cryptography, we
want something that's nicer behaved. We

want somehow a finite set. OK. So this is
just important for implementation. And the

ones that we want to work with, I'm just
going to remind you, are the integers

modulo N, so we take some positive integer
N, big N, and then we consider the set

from zero to N minus one. Okay. And these
numbers do follow certain addition and

multiplication rules and it pretty much
works like a clock face. OK. I chose N is

12 here and, just bear with me, imagine my
clock face goes from zero to eleven

instead of from one to twelve. But it's
really the same. For example, if I tried

to add ten to five. OK, I start from ten.
I go two steps and then I arrive at zero.

This is where my clock ticks over. Right.
Like on a real clock. And then you go

three more steps. And so ten plus five mod
twelve is three. So it's numbers that kind

of behave this way. Think of addition on
on a clock face. And for the computer

scientists out there or, I mean, everyone
probably knows about that, for a computer

they're like the 8 bit integers where N is
2 to the 8. And then these are the numbers

from 0 to 255, and so on and so forth. So
these are the numbers that we want to work

with. Just to set the stage a bit. And
these isogenies. We will live in a world

where we we work with somehow related
numbers to these integers mod N. And now

for big N, we choose a prime P and then
these integers mod P, they represent what

we call the finite field with P elements.
Okay. And you can think of this as a set

that has exactly P elements and really
kind of behaves like the real numbers.

Okay. You can add numbers, you can
subtract numbers. You can divide by

everything but zero. Okay. And this finite
field with P elements works really the

same. It's just a finite set, but
everything is invertable except zero.

Okay. And these are the numbers that we
want to work with and computers can do

that. So that's fine. And just for the
sake of telling you, there are also fields

that have somehow P to the R elements, but
they are not the same as what people are.

Okay. But there is a way to construct it.
But that's all you need to know about. So

this is really the set of numbers that
we're going to work over and that that's

all you need to know. Okay. So the
cryptographic problem that I want to focus

on this talk is simple key exchange. I'm
not gonna talk about signatures, I'm not

going to talk about encryption, nothing.
Let's just focus on this one simple

problem of how do Alice and Bob exchange a
key without anyone else somehow getting

access to that key? And I mean, there are
somehow classical solutions to that. I

could put my key in a suitcase and I could
bring it to Alice or I could somehow pay

someone to bring the suitcase to Alice. Or
maybe people heard about the thing where I

put my lock on the box and I ship it to
Alice and she puts her lock on the box and

she ships ships it back now I remove my
lock and I ship it to Alice again. OK, so

there are countless ways, but we want to
somehow do this in a nice, instantaneous

kind of way using mathematics. Okay. So
this simple problem is what we're going to

focus on. And classically (whatever that
means for now) this has been set off by

Diffie-Hellman. And this is this nice
paper from 1979 the title is New

Directions in Cryptography. So this
already tells you that something important

must be going on and what you somehow
invented there was a way to exchange keys

between two parties using a nice, well-
defined problem. Okay. And how does it

work? Okay. I'm just gonna tell you how it
works. So there are two parties, Alice and

Bob. A and B. They agree on a safe prime
modulus, N. Okay. So this is the integers

mod N, which I saw, and a generator G. So
what does that mean? Basically in my set,

from zero to N, I want to single out one
element such that every element can be

written as a power of that element. And
somehow this means it generates it. Right.

So every Y can be written as G to the X
mod N. Okay, this is my setup. And then

there is Alice and Bob and they agree on
these two parameters. Okay. And now how do

we do the key exchange? So it's very
symmetrical. So Alice chooses a random A

in the set from one to N minus one. And
she sends big A is G to the small a mod N

to Bob. And as you might have guessed it,
because I said it's symmetrical, Bob does

the same. Okay. So how does the picture
go? So Alice on the left, she chooses a

random small A. And she sends that big A
to Bob. Bob chooses a random small B. He

sends the big B to Alice. And then
somehow, you know, you have to combine

them somehow. Right. How do you do this?
So this is nice to compute the shared k,

the shared key. So Alice takes the B, she
got from Bob and raises it to the power of

her own random secret value. And Bob does
the same. And magically from mathematics,

they both get the same small k. And now
I'm going to tell you why, somehow, this

is hard for anyone else to get the same
small k. So now bear with me. I'm gonna

write it down mathematically, first of
all, why not teach you a bit about that as

well? So this is this diagram, this
commutative diagram that somehow

represents this key exchange that just
happened. Okay. So Bob and Alice, they

both started in the left upper corner with
the G and they both end up in the lower

right corner, the G the AB. So they both
are able to somehow compute G to the AB

and no one else is. And how does that
work? Well, Alice will only compute the

horizontal arrows, so she only raises to
the power of small A because that's her

random secret that only she knows. And Bob
only computes the vertical arrows, so he

only raises to the power of small B,
because that's the secret to he knows and

no one else does. And I mean by the
commutativity and the associativity of

exponentiation, they just agree on the
same G to the AB which is which is cool.

And somewhere in there there hides a
problem that we like to call the discrete

logarithm problem and it just happens for
integers mod N if I choose my N

appropriately, I'm not gonna tell you how,
but just believe me if I choose it

appropriately. If I give you Y and G, for
you it's hard to find the small X. Somehow

like taking a logarithm, and we call it
the discrete logarithm because it's a

discrete set of numbers instead of the
continuous decimal numbers, what we

started with was this discrete finite set
of numbers and this DLP is hard. Okay.

This is a hard problem for classical
computers. And the best classical generic

algorithm - I'm not gonna talk about
somehow algorithms that specifically

target integers mod N, I'm just going to
talk about generic algorithms for for this

DLP problem. The best algorithm somehow
has run time square root of big N the

number of elements and say I chose my N
about the size of 2 to the small n, or n

bits. Then solving this takes exponential
time in n, right, because the square root

of 2 to the n is still pretty big. Okay,
this is about 2 to the n half, and if I

make n a thousand is still 512 bits. So
this is a hard problem. But recently there

has been a record for factoring and DLPing
over a seven hundred ninety five bit

modulus and they use a bit of a better
algorithm, but still, I mean it still took

them a long time. Okay, so if I remember
correctly, this feed took them 4000 core

years on a two point one gigahertz
computer. I mean, that's still 4000 core

years. So this is a long time. Okay. But
as you can see, it's possible to solve

this. I mean, just put enough, if I have a
big enough hammer, I can solve this. Okay.

But again, you can make N pretty big,
bigger than anything being able to solve

this anymore. But. Okay, so there is a
quantum algorithm for this and this is

this other paper from 95. Peter Shor. So
he thought of this algorithm that solves

the DLP in polynomial time. Okay, now
remember our big N we took about two to

the small n. And this Shor's algorithm
only takes small n to the cube? And I

mean, if N is a hundred hundred cube, it's
not that big. And I can make a thousand by

a thousand cube is still not that big.
Okay. So there is a good algorithm that

assumes the existence of a quantum
computer. I mean as outlandish that might

sound, but still this algorithm in theory
breaks the DLP. Okay. So I don't know,

maybe in 20 years or 30 years, 100 years.
I don't know personally, but if there is a

quantum computer eventually that somehow
runs this thing, okay, DLP's broken,

classically. So. Well, what to do? As I
said, let's just try to come up with

cryptography for which we don't know a
quantum algorithm. Okay. Or for which we

expect there won't be a quantum algorithm
ever. There are a few candidates. Again,

there's this zoo. Lattices, codes, this
long word, and isogenies. Okay. Now what I

want to tell you about is what is an
isogeny, and how do I do key exchange with

an isogeny? Okay. Because I know, it's a
fancy word, but what does it mean? Okay.

There was this other word that started
with elliptic curve isogenies, so probably

I should tell you about what is an
elliptic curve or give you a reminder if

you've seen this before. So I look at this
equation in two variables and two

constants, the variables X and Y, my
constants are A and B. And the equation is

Y squared is X cubed plus AX plus B. And
now what I want to look at is all the

solutions to this equation, all the
possible pairs Y and X or X and Y. And of

course, they're going to look different
somehow for the different possible numbers

that I can plug in for X and Y. And again,
you might have guessed it, first of all,

we're going to look at it over the decimal
numbers and then later we want to consider

this again over our finite field, okay,
because we like we like this discreteness.

And over R, a simple equation, I just
chose some values for A and B, B I set to

zero, A I set to 1, uh, A I set to zero, B
I set to one. The solution set looks like

this. And actually it extends infinitely
far on the right side, up and down. Okay.

So this is just somehow a snapshot of what
the solution set looks like. But over my

finite field, and I chose one with one
hundred and one elements, it looks like

the set of points. Okay. So elliptical
curves look differently over different

fields. But that's fine. That's fine.
Okay. Now, quick reminder of why people

like elliptic curves. So there is
something called the point addition law.

So I can take two points on this curve and
I can somehow add them. Okay, but this is

not really addition in the sense of
numbers. There is somehow a law that I have

to apply. And let me quickly show off how
this is done. So how do I add two points

on this curve? Well, you take these two
points, you put a line through it, and

then there is a law that says that if I
put a line through two points, then it

has, the line has to cut the curve from
the third point. Okay. So I put the line

through these two points. It cut the curve
in the third point all the way up on the

right. You know, what I'm going to do is
I'm going to reflect the point down on the

X axis. Okay. So I draw this other line, I
reflect it down. And then what I define is

that other, that I cut, this I define to
be the sum of these two points. Okay. So.

And that works. Okay. I can add points, I
can subtract points. There will be the

inverse. So this kind of like X like
integers mod N when you only consider

addition, kind of, kind of, it's not
really the same, but you can also single

out the special point O like beautiful O
we call the origin, whatever that is. And

this origin kind of acts like a zero. So
if I add the origin to the point where I

get the point again, or if I add the point
and its inverse I get that point, I get

zero. Okay. So there's something like a
zero. And you can also multiply points,

right. I mean what is multiplication, it's
just repeated addition. So in brackets n,

this is what I write for point
multiplication, just add the point n times

to itself. Okay. So there's nothing fancy
going on here. So you can somehow add

points. You can multiply points. That's
pretty cool. And if you look closer, you

can look at the special set here that I
denoted E brackets, big N. And these are

all the points on the curve such that if I
multiplied this point for N it gives me

zero. Okay. And this set for the
mathematically inclined people among us I

know say this is somehow the N-torsion of
an elliptic curve, whatever that means.

But if you're interested, you can look it
up. And this set kind of acts like

additive integers mod n - like two copies
of it. Okay. And now this is where the

term super singular comes from. One of the
definitions. This is not the only

definition, but this is one of them. If
you look at the elliptic curve, not over

the reals, okay, or whichever numbers, but
over this finite fields. And if you look

at the torsion, the P-torsion, then this
behaves differently for different types of

curves. Okay. The P-torsion is either
empty, then we call the curve super

singular; or it's just one copy of of
integers mod P and then we call it

ordinary. Okay. It's not really important
to know what that means. It just means

that there is a distinction for curves
somehow that's somehow ingrained

mathematically deep down there. And
because this E N torsion is somehow two

copies of of integers mod N, additive
integers mod N, I can generate it by

taking linear combinations of two points,
say P and Q, and these are like the

generators we saw earlier. Right. But
these are not additive generators instead

of somehow exponential generators. But it,
everything behaves kind of similar. And

now you can really use this to do
cryptography already. If you wanted to

write it. You can. You can somehow look at
the DLP in that group, but there is the

problem again that the DLP in there,
there's Shor's algorithm again. Right. So

even if you do cryptography in this group,
you run into the same problem. OK, so we

have to do a bit better. We have to search
further. And this is where isogenies come

on. Come into the play. So one way you can
think of an isogeny is, remember how we

found integers mod N by somehow dividing
Z by all the N multiples. And you can do

something similar with an elliptic curve.
if you can somehow take part of this

N-torsion and you can divide an elliptic
curve by this. You can mod it out and it

turns out this is mathematically well-
defined and it gives you another elliptic

curve. Okay. So I take a curve, E1, I take
a part of my N-torsion. I divide elliptic

curve E1 by G and I get another elliptic
curve E2. And there's something else that

comes along with this construction. And
this is what we call the isogeny. This is

a map. OK. Along with this construction
comes a map from E1 to E2. And this map is

what we call an isogeny. An isogeny is the
map that takes us from one curve to

another curve. And this map is kind of
special because it behaves in a nice way

and it plays nicely with the structure
that's already ingrained in our curve.

Namely, I can either add two points on my
starting curve and send it through that

map to the other curve. Or it can take two
points on my starting curve. I can send it

through the map and edit over there and it
gives me the same thing. So this map

behaves nicely with point addition. That's
pretty nice, just as a side note. So this

map is special. So this is just the
remainder of what I said: Adding points on

E1 and sending the result to E2 is the
same as sending points to E2 and adding

them there. So this map somehow plays nicely
with my laws on my elliptic curve. Now I

have to make a definition: In mathematics,
the kernel of a map is the set of all the

inputs to the map that are sent to zero.
And we saw this origin O here that acted

like zero. So the kernel of my isogeny,
I'm just going to define as all the inputs

to the isogeny that are sent to the zero
on the other curve. And in written

notation, it's the set of all P in E1 such
that the map of P is 0. It turns out that

this kernel for my isogeny, that I started
out with somehow recovers this part of the

end portion that I used to construct. So
there's two ways now to think of an

isogeny. So this is what we start with. We
reconsidered E1 mod G and it gave us this

map from E1 to E2. But if I start with
this map from E1 to E2, we also find the G

again. So there are two ways to represent
this map. We can think of a subgroup -

this G - or we can think of the map. And
ultimately somehow there is a correspondence

between the various subgroups for
different N and isogenies that are somehow

emanating from a curve. We can think of
this link or the hairs on my head, they

are going out and then they're going to
reach other electric curves maybe. And

these notions can be used interchangeably.
So somehow there is a correspondence. And

again, I can choose different ends. So some-
how from one curve, I can have many outgoing

isogenies that are different in a sense. And
now the thing is in practice, we actually want to

compute these maps. So right now, this is
just general abstract nonsense. I didn't

tell you anything of how to compute these
things. I just told you there are some

more correspondences. But I mean, what
does that even mean? Right. It's useless

if I can't use it in practice. And then
there is another thing: You can compute

these things, there are formulas, people
have worked on this. But somehow the cost

grows if I enlarge N. So really, in
practice, for applications, I want to choose

a small N. Maybe two or three - that would
be pretty good. And now the thing is, it's

the supersingular curves for which I can some-
how control or choose the possible ends very

very easily. So this is the reason why we
reconsider supersingular curves. Now I can

choose my prime to be of this form and
then magically this is going to force 2

and 3 being possible. So this is the
reason why we choose supersingular ones.

There's some theory which is not
interesting for you, but it's important

for implementation. And there's a way basically
for us to force the curve to have those

isogenies that we like. But there is
another important reason and this is the

reason that actually makes it
interesting for cryptography. So what I

can do is: I start with an arbitrary
curve, and this just might not be a

supersingular one, just any curve and say I
consider all the outgoing two isogenies if

these are possible, 4 and 2. So there's
going to be 1, 2 and 3. And then again,

from E1, I can again consider all the
outgoing isogenies, and so on and so

forth. So what's going to happen here is:
This is going to generate a graph, where

the vertices of my graph are elliptic curves
and the edges are isogenies. So somehow

behind the scenes there is this graph
hidden. Now, it turns out that if you do

this for a supersingular elliptic curve -
and I generated this yesterday for you,

so this is one possible graph - I can
remember which prime I took. But here you

can see all the ellipses are ellipitic
curves and all the edges between them are

2 isogenies. So this is an example of a
supersingular 2-isogeny graph - okay, this

looks pretty wild. I can do the same for N
= 3 if it's possible, or is 5 and so on

and so forth. There are many many graphs
hidden. But why is the supersingular graph

specific and important? Well, it turns out
that somehow the supersingular one is

connected, and it's what we call a
Ramanujan graph. I'm going to explain

this in a second. And as a bonus, for
implementation purposes, it turns out that

you can do all your implementation in
arithmetics in the finite field with p^2

elements. This is nice. So I'm just gonna
say that if you don't consider

supersingular curves and you go along
these graphs, then what's going to happen

is that somehow this "field of
definition", what we call it, could grow

for you to be able to go further, but that
would suck for implementation. But

supersingular ones is nice so, F_p^2 is
enough. So this is again, is good for

implementation. So somehow magically many
many things happen here that are benefiting us.

And again, why is it nice that this is a
Ramanujan graph? A Ramanujan graph has

certain optimal expansion properties. This
means that if I start from a random point

in my fraph, and I take a random walk with some-
how logarithmic steps of the total amount of

vertices, then this will put me in a very
uniform place in that graph. And this is

is good for cryptography. Because you only
need to take log many steps to somehow

randomize yourself in that graph. And this
is what this could look like. I started at

that red ellipses over there. This was my
starting point. And then I generated a few

random walks, and the blue points are
where I got placed. This might not prove

anything, but it gives you an idea of how, some-
how uniformly, it places me around that graph.

So, it's good for cryptography, but there
are other reasons, so supersingular elliptic

curves somehow I can actually compute how
many of these curves I will have in my

graph. This is another reason to be
looking at these things. Because if I

don't even know how many curves are in my
graph - well I can't really say anything

about the security - but at least for
supersingular ones, I can see they're

roughly p/ 12 many. Okay, and then again,
if I'd choose my p about n bits, well then

I really know that my graph has about 2^n
elements. And at least there I can see

something about the cryptographic
strength, right? I can make M big and then

you can say: Oh yeah, you have this random
graph, you take some n-length walks and

n-length walks and then it places you
randomly in there and the whole graph is

about 2^n elements. And then I can say
something about the expected runtime of

algorithms. So this is another reason why
we want to consider supersingular curves:

Because I can tell you how many elements
are in this graph. So a quick summary of

what we saw, why this is nice. So what you
get is a compact representation of an

(l+1)-regular graph. And we saw examples,
e.g. l = 2, l = 3. Bigger values are

possible, but we don't even care about
those because this is what gives us the

fastest arithmetic such that we can work
with F_p^2. This is nice, this keeps our

implementation fast. I can tell you how
many vertices are in the graph: about

p/12. And again, such that the graph for
mixing properties that are useful for

cryptographic applications. So because I
want to use this ultimately for

cryptography. And again, that's what we
said: If I choose an n-bit prime p, then

the graph has about 2^n vertices - so
exponentially many vertices. And it turns

out that there are some hard problems that
I can ask you to solve in this graph that

don't have good quantum algorithms. So one
hard problem is this: I take two super

singular elliptic curves, so I just give you
two random curves in this graph and ask

you to find a nice arch in the path
between those isognies, or three

isogenies. And it turns out that this just
doesn't have a good quantum algorithm. So

classically, I mean the numbers are super
important here, but classically the

complexity is p, over the fourth root of p,
and the best quantum algorithm is a bit

better at it. I mean again, it's not super
important what's there. What's important

is that there is no polynomial time
algorithm compare to ideal p that we

started with. So if I make this p very large
and your quantum computer, your

hypothetical quantum computer, will
probably not solve this. Okay, so that's

cool. So how do we do key exchange? I
start with a supersingular elliptic curve E,

where I chose my prime p such that two and
three isogenies are possible. And then

Alice - earlier I remember she chose a
random number a - but now Alice will

choose a random subgroup A, and she will
send E mod A to Bob. This amounts to Alice

for computing the nice isogeny. And again,
this is a very symmetrical key exchange,

except that now Bob won't use the same
generator but Bob will use the 3

isogenies. So Bob will choose a random
subgroup B, and then he will compute E mod

B and send this to Alice. And this is the
picture: There's Alice, there's Bob. Alice

chose A, Bob chooses B. Alice sends E mod
A to Bob, Bob sends E mod B to Alice. And

then how do they agree on a shared key?
They will just mod out by their respective

subgroups again. And it turns out that the
elliptic curve that they find is going to

be the same for both of them. Okay, so how
does that work? Again, let's return to our

graph: Say Alice and Bob agree on a black
curve - the black curve on the left side.

And then Alice will compute these red
steps, which correspond to taking a

subgroup. So Alice will compute these red
steps for her secret subgroup and she will

end up at the red curve in the upper right
corner. And Bob will do the same. But now

Bob is not in the 2-graph, but in the
3-graph - so this is the three graph. And

the black curve that he started from in
the 3-graph is down there. He will also

select a random subgroup, compute the
secret path and Bob will end up in the

blue curve. Now Alice will send her red
curve to Bob. And Bob, will send his blue

curve to Alice. And then Alice will
consider the blue curve in the 2-graph. So

Alice starts from the blue curve that she
got from Bob - and this is the position in

the 2-graph. And again, she computes that
same secret path and ends up in the green

curve, which is up there. Bob got the red
curve from Alice. So Bob has the red curve

there. Again, he computes the path and
then ends up at the green curve. And it

turns out that the green curves here and
there are the same. And this is going to

be the shared key for them. This is SIDH.
Okay. This is how you exchange a secret

key using the supersingular isogeny graph.
That's the whole magic. And again, let's

compare these two things a bit: the DLP-
based one and the SIDH one. So we had the

square, Alice and Bob started in the upper
left corner and again ended up in the lower

right corner. And SIDH looks very similar:
Alice and Bob start with this common curve

E in the upper left corner. Again, Alice
computes only horizontal arrows because

she knows her secret group A, and Bob only
computes the vertical arrows because only

he knows his secret group B. And again,
they both end up in the lower right

corner, where they define the shared key.
But now in this case, the shared key is

not an element to the a^(ab), but elliptic
curve. But again, there's a mathematical

way to attach a unique number to it. So
it's a solved problem to actually make

some bytes out of this. And yeah, that's
SIDH. That's everything. This is a nice

example of a post-quantum cryptography
scheme that we have today. And now

let me finish with a quick conclusion. I
showed you this "zoo": There are several

candidates somehow for post-quantum
cryptography. And among them are some

schemes based on supersingular elliptic
curve isogenies, and we've seen that we

know some hard problems involving these
isogenies that are hard for quantum

computers, which makes this one possible
scheme for a quantum computer world. And

probably I should say that we don't
envision a world here where we users like

me or you are in possession of quantum
computers. Probably, what we think about

is that state actors are in positions of
quantum computers. So this is even more

important for us to be looking into these
things. And what we saw was to perform a

Diffie-Hellman-like key exchange using
these isogenies. But - this is what I

didn't tell you about in his talk - there
are also schemes for signature-based

isogenies, there is this scheme for key-
encapsulation-based isogenies. So

there are other possible candidates for
other cryptographic building blocks based

on isogenies and these hard problems. And
if you're super interested about this, you

can either ask me or come to our assembly
and if you like reading scientific papers,

papers about such isogenies and
cryptography in general, you can find this

on the eprint archive. So this is a web
page where people post pre-prints about

their papers and there's a huge collection
about, among of them, isogeny papers. So

if you're interested in this, this is the
place to research. And with that, I would

like to thank you all for your attention.

applause

Herald Angel: Is there any question? OK, I
got the Signal Angel there, doing some

Morse code?
Microphone 1: Yes. Can you recommend any

literature for the theoretical background?
naehrwert: The theoretical background?

There are a few papers that are nice.
Okay. The question again was literature

about theoretical background. And yes,
there are a few papers that are giving

some nice, even theoretically involved
summaries about the background. And your

best bet is to go to eprint and you enter
'isogenies' in the mask of search terms,

or 'SIDH', and look at the papers that
say, maybe, 'A Short Introduction to

Isogenies' or something like that. I mean,
you will find them if you search for them.

I don't know them from the top of my head,
but they're out there for sure. Yeah, and

thanks for him - So there is a very recent
paper by Craig Costello, also somewhat

titled 'A Short Introduction', something
like that. So this is also maybe a good

source for you to look at.
Herald Angel: Um, yeah, 'Isogenies for

Beginners'.
naehrwert: 'Isogenies for Beginners'.

Thank you.
audience laughing

Microphone 2: Hello. Yeah. So you've used
elleptic curve as an algebraic group,

right, to compute these isogeny graphs.
Why do you use elliptic curves - what's

the properties of elliptical curves as a
group? So, could you use any group to

compute these graphs and could you use
these as the basis for your scheme or your

key exchange scheme?
naehrwert: Okay, so the question was why

use elliptical curves and the group
structure that the impose to look at

isogeny graphs involving elliptical curves
and whether I could use other groups. And

actually, there's a two-fold answer maybe.
So if I go back - or actually let me go to

my backup slide, which gives you SIDH in
its full glory - you consider some extra

information being sent, namely these
generators from my group and actually the

same commutative diagram for SIDH. You
could, in theory, compute using another

group as well, that has the proper
subgroup structure, but the graph that you

will find is probably not going to be
interesting. I mean it's really somehow

that Righello property that makes the
graph interesting for cryptography. But

yes, in theory, the SIDH commutative
diagram you could also compute for other

groups, yes.
Microphone 2: OK.

Microphone 3: Uh... How good are classical
algorithms that tried to reverse that SIDH

problem, because that will be the bound
for how large your keys have to be, to be

secure.
naehrwert: Yes. So the question was: How

good are classical algorithms? And again,
I said, I think the runtime for those is

squared of p. And this tells you how big
you have to choose B.

Microphone 3: And how confident are you
that this really is hard for quantum

computers as well?
naehwert: Well, how confident am I that

this is really hard for quantum
computers? So first of all, cryptography

is all about confidence, right? So someone
proposes a problem, this problem gets

crypto-analyzed. And if it's not broken
after 40 years, then people will say, I'm

pretty, pretty confident this is good. And
maybe if the NSA doesn't tell you anything

about it, or maybe if they don't have, you
know, anything on it, then you can also

see that you're confident in it. But I
think this is really a question that only

time can answer, right?
Microphone 4: Yeah. Is it possible to

prove that no polynomial-time algorithms
for the isogenies problems can exist

for a quantum computer?
naehrwert: Yeah, that's a good question.

How do you prove that no algorithm exists?
This brings us into territories, like ...

Yeah. I don't know. Yeah.
No. Let's not do that.

Microphone 1: Yeah. Good talk by the way.
At the last slide you say that this is hard

for a quantum [computer]. But that can't
be true because we don't even know if any

algorithm is hard for classic computers.
Right? So, I'm guessing you're saying that

intuitively it feels hard, which, you
know, is the same intuition I have about

e.g. factoring in. So, you mention there's
multiple candidates for post-quantum

cryptography, and they all intuitively
feel hard somehow. Do you know if this

specific candidate, would this be your
horse in a race? Is there anything about

this specific way that you think would be
the best fit for post-quantum

cryptography?
naehrwert: Okay. Your opinion is very

valid. Of course, we don't know if it's
hard, right? This connects back to the

other questions: How do you trust
something like that? Again, people do

crypto analysis for 40 years or whatever.
And then you say, oh, no one found

anything - it's probably hard, right? But
it hasn't been an exact 40 years. You

cannot say that. Indeed these things are
relatively new. And personally, I'm not

gonna, I don't know, believe in any of
these things until some time passes. So my

reason for looking into these things
really is more a mathematical curiosity,

because I think these things are
beautiful. And the cryptography that

arises from it is more of a side-effect
for me personally. So I'm not going to put

out any guesses on which of these things
is actually going to win the PQ race or

whatever.
Microphone 2: (Yeah. I am.) You showed or

said you think it's hard for the classical
way and for the quantum cryptography way.

I think I just read a paper last year
about a combined way in classical and

quantum cryptography combined, which
outperforms either one of those ways. Do

you think this could also be relevant or
gonna make this one way to put in

computable in polynomial time?
naehrwert: Are you talking about an

algorithm that somehow combines a
classical step and a quantum step to break

this?
Microphone 2: Yes.

naehwert: Yeah well, most algorithms that
we say use a quantum computer involve a

classical part anyways. If you think about
Shor's algorithm, there's a classical part

and a quantum computer part. So I'm not
sure which algorithm you read about, but

I'm sure that somehow all the quantum
algorithms involve a classical part

implicitly anyways.
Herald: Signal Angel?

Microphone 3: Yeah. Can you please name
the mentioned contestants in the list

'Challenge-based Isogenies'?
naehrwert: So there is SSIKE, I believe:

supersingular isogeny key encapsulation,
but actually I don't really follow the

NIST thingy closely, so I actually
couldn't even name all the names that are

involved in it, but you can look it up on the
NIST website and I believe somewhere there

is also a classification of the contenders
into this view. So they will tell you

which contenders are based on lattices and
which contenders are based on codes and

which ones are somehow based on isogenies.
But off the top of my head, actually, I

don't even know. Sorry.
Microphone 1: So if I got everything

correctly, though, those isogenies are
group homomorphisms between the elliptic

curves and the factor group of the
elliptic curve by g. And which has kernel

g again.
naehrwert: Yes.

Microphone 1: And you said that finding
the isogeny path in the graph is rather

difficult. But wouldn't the real
difficulty rather be finding the subgroups

G - because a group homomorphism between
the elliptic curve and the factor group

with kernel g is simply the canonical
protection.

naehrtwert: Exactly. So I see you are
mathematically trained, which is very nice

and I appreciate that, this is great and I
am very happy about that. And yeah, if you

look at the slide actually, the secrets
are these alphas and betas, which somehow

determine the subgroup. And yes, finding
those isogeny path is equivalent to

finding the alpha, somehow, that generates
this group. And as you said correctly,

finding the isogeny path is somehow
finding this group. But it's just

restating the problem. But it's still hard
somehow to find this group. Yeah.

Microhone 1: All right. Thanks.
naehrwert: Thank you. Very cool.

Microphone 2: Yeah, thank you for the
great talk. So, can you play this game a

little bit further? I mean, can you choose
higher-dimensional abelian varieties to

make it even more secure? Or is it just
absolutely inaccessible? I mean, from the

computation perspective, the choice of
field of definition is difficult, for

example, so...
naehrwert: Okay, so the question was on

whether you can use higher-dimensional
abelian varieties and maybe for the people

who don't know what that means: You can
attach a dimension to these things in the

elliptic curves, somehow have a dimension
1 attached to them. And the question was,

can you somehow look at dimension 2,
dimension 3 or higher? And actually, back

in the days when people were thinking
about the DLP problem on the points of

elliptic curves that I mentioned briefly,
people had the idea of maybe using

dimension 2 or dimension 3. But it turns
out, that the DLP problem actually, at

some point, gets easier in higher
dimensions. So, classically if you look at

the DLP, you somehow want to stay at
dimension 2, but now, what you can do is,

you can look at isogenies between
dimension-2 and dimension-3 ones. And

actually the problem that arises there -
and this makes elliptical curves very

special - is that we can compute isogenies
rather efficiently for elliptical curves

because of Velu's formulas. Okay. So
this gives us a very direct means of

computing D, but it actually gets hard as
the dimension grows. For example, for

dimension 2 already, the only isogenies
that I am able to efficiently compute are

2- and 3-isogenies. So there are some
packages out there that can compute higher

ones, but only if my prime is very small
and for dimension 3 and higher it gets

even harder. And then there is another
thing that comes into play. So dimension-2

varieties, they all arise from what we
call hyperelliptic curves. But if we look

at dimension-3s and higher, then sometimes
you land at a point in your graph that

does not come from a hyperelliptic curve
anymore. So there is another complication.

So I mean, I had a friend who was looking
into genus-2 isogenies and it's possible

to go there. But I don't know. I think
personally this is more of a toy than

something that's good in practice.
Microphone 2: Can you use this scheme to

implement a fully homomorphic encryption
scheme? Or is it already?

naehrwert: Uhhh... No. No.
laughing

naehrwert: Yeah, no fully homomorphic
encryption is somehow a pipe dream, but I

mean sometimes it's possible. So the idea
is that you can add cipher texts and get

the sum of the ciphered texts and have a
second operation, namely you should be

able to multiply ciphertexts and get the
multiplication of two ciphertexts. But we

didn't even talk about encryption.
Microphone 2: Yeah. Another question: Is

there any crypto primitive used in the
isogeny approach that cannot be Stark-

reduced to finding a hidden
subgroup in an abelian group?

naehrwert: Could you repeat the
question, please?

Microphone 2: Is there any crypto
primitive used in the isogeny approach

that cannot be Stark-reduced to finding a
hidden subgroup in an abelian group?

naehrwert: Okay. I think this question
tries to connect back to the hidden shift

problem or the hidden subgroup problem and
Berg's algorithm. But I think I'm not able

to answer that question now without
talking to the person that actually asked

it because it's a bit vague.
So I'm sorry about that.

Microphone 3: How do you send an
elliptical over the wire?

naehrwert: Yeah, maybe I should answer
that actually. So we saw the

parameterization of the curve that had
these coefficients A and B. But what

I didn't tell you is that to an elliptic
curve you can actually attach what we call

an invariant in mathematics and for an
elliptical curve, this is called a

j-invariant and it's a single integer
which determines this elliptical curve

uniquely. So if I want to send an
elliptical curve, I can simply send you

its j-invariant. And if you know the field
of definition, you're going to be able to

somehow recompute it just from the single
value. So it's actually quite a compact

representation which makes
this also interesting. Yeah.

Herald: I guess this is all. Thank you.

applause

postroll music

subtitles created by c3subtitles.de
in the year 2020. Join, and help us!