*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!