(Post-Quantum) Isogeny Cryptography
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 254 | |
| Author | ||
| License | CC Attribution 4.0 International: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/53213 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
36C3: Resource Exhaustion36 / 254
1
7
8
9
10
11
24
26
27
28
35
39
40
41
43
44
47
49
50
55
56
60
62
63
64
68
71
72
74
75
77
78
79
82
88
93
99
100
102
106
109
111
112
113
118
119
122
124
125
127
132
133
135
136
137
138
140
141
142
143
144
145
146
150
151
156
157
158
161
162
164
165
166
167
170
173
175
177
179
180
182
183
187
201
202
208
213
219
224
226
233
234
235
237
239
240
241
244
246
247
249
251
253
00:00
Student's t-testHacker (term)QuantumComputerSystem programmingInclusion mapNP-hardBootingCryptographySoftwareCodierung <Programmierung>PolynomialHash functionType theoryDifferent (Kate Ryan album)IntegerInfinitySet (mathematics)Module (mathematics)AdditionModulo (jargon)Element (mathematics)Prime idealDecimalField (computer science)DecimalProcess (computing)Arithmetic meanPower (physics)Universe (mathematics)MathematicsComputer sciencePhysical systemVideo game consoleTheoryPhysicalism2 (number)Quantum computerHash functionHypermediaDescriptive statisticsNormal (geometry)Real numberOrder (biology)Inheritance (object-oriented programming)BitConnected spaceQuantumCASE <Informatik>CurveAdditionRight angleWave packetState of matterFormal grammarNumberControl flowNeuroinformatikData miningSchlüsselverteilungStudent's t-testGoogolMathematical singularity1 (number)Rule of inferenceMultiplicationCondition numberElement (mathematics)CryptographyInfinityQuantum cryptographyElectronic signaturePoint (geometry)Key (cryptography)BlogCuboidInformation securitySet (mathematics)CAN busZoom lensElliptic curveFinite setPolynomialField (computer science)Natural numberCase moddingFinitismusImplementationIsogenieIntegerGalois-FeldLevel (video gaming)MultilaterationRational numberWebsiteComputer animation
07:35
InformationMetropolitan area networkDirection (geometry)Prime idealExponentiationComputerArrow of timeLogarithmMathematicsCryptographyDirection (geometry)Set (mathematics)Case moddingKey (cryptography)Power (physics)BitPrime idealElement (mathematics)RandomizationDiskreter LogarithmusCommutatorArrow of timeIntegerAssociative propertyDiscrete groupNumberBit rateNeuroinformatikComputer configurationMetreAlgorithmRight angleClassical physicsNP-hardGeneric programmingReal numberTouch typingDegree (graph theory)Food energySymmetric-key algorithmError messageSinc functionSummierbarkeitLogarithmSchlüsselverteilungDiagramRow (database)WordLecture/ConferenceMeeting/InterviewComputer animation
11:30
AlgorithmExponential functionLine (geometry)RSA (algorithm)Type theoryElectronic mailing listMereologyRevision controlPrime idealPolynomialFactorizationQuantum computerDigital signalComputerPhysical computingIntegerCode refactoringNumerical digitoutputQuantumClassical physicsBasis <Mathematik>NP-hardCodierung <Programmierung>System programmingHash functionNichtlineares GleichungssystemPoint (geometry)Single-precision floating-point formatModule (mathematics)Exception handlingLinear mapQuantumCase moddingNeuroinformatikQuantum computerSquare numberRun time (program lifecycle phase)Point (geometry)BitElliptic curveRootInheritance (object-oriented programming)AdditionMultiplication signRow (database)Generic programmingNumberAlgorithmImage resolutionExistenceNichtlineares GleichungssystemCubeControl flowTheoryVariable (mathematics)WordLogical constantPotenz <Mathematik>CurveCore dumpSimilarity (geometry)Classical physicsCryptographyDivisorPolynomialSet (mathematics)IntegerElectric generatorCombinational logicNP-hardElement (mathematics)DecimalDiscrete groupFinitismusPhysical lawLine (geometry)Poisson-KlammerSummierbarkeitCASE <Informatik>Arithmetic meanComputer programmingDifferent (Kate Ryan album)DemoscenePeer-to-peerField (computer science)InfinityMeasurementRight angleModule (mathematics)Beat (acoustics)MathematicsGroup actionKey (cryptography)Type theoryMUDInverse elementDecision theoryFerry CorstenMultiplicationObservational studyReal numberTorsion (mechanics)Computer animation
20:00
Similarity (geometry)System callAdditionPoint (geometry)outputKernel (computing)AerodynamicsDirection (geometry)Cellular automatonCurveControl flowGraph (mathematics)Connected spaceExpandierender GraphImplementationThermal expansionMathematical optimizationRandom numberInfinityPrime idealVertex (graph theory)Correspondence (mathematics)Forcing (mathematics)SubgroupGraph (mathematics)Graph (mathematics)Mathematical singularityCurvePoint (geometry)EllipseElliptic curveLatent heatLevel (video gaming)Similarity (geometry)Inheritance (object-oriented programming)Data structureImplementationResultantSeries (mathematics)Set (mathematics)Physical lawMereologyMathematical optimizationTorsion (mechanics)Thermal expansionCase moddingRandom walkDifferent (Kate Ryan album)IsogenieIntegerMultiplicationConstructor (object-oriented programming)Field (computer science)Vertex (graph theory)2 (number)Goodness of fit1 (number)Category of beingKernel (computing)outputAdditionGalois-FeldDrop (liquid)Exception handlingSquare numberElement (mathematics)Interrupt <Informatik>Information securityComputer configurationGrass (card game)DemosceneCASE <Informatik>Physical systemMetropolitan area networkTotal S.A.TunisGroup actionVideo gameCryptographyMathematicsData recoveryKey (cryptography)NeuroinformatikMappingCartesian coordinate systemWell-formed formulaTheoryOnline helpComputer animation
28:30
Graph (mathematics)Element (mathematics)Prime idealMathematical optimizationThermal expansionRandom numberInfinityCurveVertex (graph theory)Compact spaceRegular graphAlgorithmNP-hardKolmogorov complexityQuantumCommunications protocolSimilarity (geometry)Arrow of timeComputerCryptographyElement (mathematics)QuantumKey (cryptography)Random number generationCurveQuantum computerGroup actionNumbering schemeNumberGraph (mathematics)Arrow of timeAlgorithmIsogenieRandomizationVertex (graph theory)Web pageElectronic signaturePrime idealState of matterElliptic curveEncapsulation (object-oriented programming)CryptographyFile archiverBuildingBlock (periodic table)RootComplex (psychology)Multiplication signCartesian coordinate systemSubgroupHypothesisCategory of beingLengthRepresentation (politics)PolynomialSchlüsselverteilungPosition operatorRow (database)NeuroinformatikKerr-LösungPower (physics)CASE <Informatik>Degree (graph theory)BitMatching (graph theory)Right anglePhysical lawReal-time operating system1 (number)ImplementationSymmetric-key algorithmSquare numberSheaf (mathematics)Mixed realityForm (programming)AuthorizationVariety (linguistics)EllipseLetterpress printingNetwork topologyDifferent (Kate Ryan album)Axiom of choiceWordComputer configurationRouting
37:00
Source codeDisk read-and-write headProcess (computing)TheoryTerm (mathematics)Auditory maskingType theoryElliptic curveCodeComputer animationLecture/ConferenceMeeting/Interview
38:41
ComputerIntegerRandom numberAlgorithmGroup actionQuantum cryptographyCurveQuantum computerCategory of beingWeightQuantumRight angleNumbering schemeMereologyWebsiteEncapsulation (object-oriented programming)Key (cryptography)Data structureBackupGrass (card game)Electric generatorDiagramTouchscreenMultiplication signConfidence intervalNeuroinformatikInformationGraph (mathematics)TheoryMathematicsPeripheralNP-hardDivisorField (computer science)Fitness functionCryptographyLatent heatMathematical analysisBit rateClassical physicsSound effectSubgroupCommutatorNational Institute of Standards and TechnologySquare numberRootRun time (program lifecycle phase)PolynomialLine (geometry)Elliptic curveSchlüsselverteilungGoodness of fitSlide ruleIsogenieCryptanalysisMessage passingControl flowBasis <Mathematik>Inheritance (object-oriented programming)Mathematical singularityGraph (mathematics)Lecture/Conference
45:19
ComputerIntegerRandom numberInheritance (object-oriented programming)Hyperelliptische KurveElliptic curveNational Institute of Standards and TechnologyAbelsche GruppeDimensional analysisField (computer science)EllipseNeuroinformatikAxiom of choiceGame theoryBitAbelsche MannigfaltigkeitArithmetic meanCode1 (number)Group actionNumbering schemeIsogenieEncryptionKernel (computing)SummierbarkeitHomomorphismusSubgroupCryptographyMultiplication3 (number)Goodness of fitPoint (geometry)Quotient groupShift operatorIntegerGraph (mathematics)CurveInvariant (mathematics)Parametrische ErregungAlpha (investment)Projective planeUniqueness quantificationSlide ruleRepresentation (politics)HoaxOperator (mathematics)CausalityCASE <Informatik>Sound effectPhysical systemArmMathematicsChainWave packetPower (physics)Software testingPerspective (visual)Well-formed formulaAreaMeeting/Interview
51:58
Computer animation
Transcript: English(auto-generated)
00:26
Thank you for the audience. 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 isogenies.
00:40
I mean, just educate the people a bit about what that means even, because I'm not so 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.
01:01
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 Ninten Bros. 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.
01:24
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's a nature article about that, Beyond Quantum Supremacy. And there is a Verge article
01:42
that Google confirms quantum supremacy, a 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
02:01
of being superior to all others in authority, power, or status. So, calling something quantum supremacy, I mean, that screams of 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
02:21
about 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 that means for now, are being actively broken yet, as we know of,
02:40
or that we know of. But in theory, they are broken, okay? And because they're only broken in theory, it's very good, so we can still blame the designers and the 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,
03:02
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? Should probably try to save our climate today instead of waiting until it's too late. So, we're gonna, we want to do the same for cryptography.
03:24
There are also three upcoming talks I wanna advertise here a bit. I think, I don't remember the days, but descriptions look pretty interesting, so I'm gonna leave that up for a few seconds. So, there's one on provable insecurity, one called Cryptography Demystified,
03:40
and one about high-assurance cryptography software, so 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 jokingly call the Postpondent Cryptography Zoom. There are a few buzzwords up there. You don't really have to know what they mean. I'm just gonna say them out loud. Lattices, codes, multivariate polynomial systems.
04:02
That's also a bit of a mouthful. Hash-based cryptography. And there's the one that I wanna briefly talk about tonight called Supersingular Elliptic Curve Isogeny. Okay, so this is the stuff that I really like. Isogeny is still 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
04:23
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 or, yeah, okay. So, that's pretty good. So, just gonna tell you something about it. So, there are decimal numbers. This is pi.
04:40
Then there are rational numbers. Somehow they are 1.5, 1.3, and so on and so forth. Then there are the 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. So, this is just important for implementation.
05:01
And the ones that we want to work with, I'm just gonna remind you, are the integers modulo N. So, we take some positive integer N, big N, and then you consider the set from zero to N minus one. And these numbers, you follow certain addition and multiplication rules, and it pretty much works like a clock face. I chose N is 12 here, and just bear with me.
05:22
Imagine my clock face goes from zero to 11 instead of from one to 12, but it's really the same. For example, if I try to add 10 to five, I start from 10, I go two steps, and then I arrive at zero. This is when my clock ticks over, like on a real clock. And then you go three more steps.
05:40
And so, 10 plus five mod 12 is three. So, it's numbers that kind of behave this way. Think of addition on a clock face. And for the computer scientists out there, or, I mean, everyone probably knows about that. For a computer, they are like the eight-bit integers where N is two to the eighth, and then these are the numbers from zero to 255,
06:00
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, they will live in a world where we work with somehow related numbers to these integers mod N. And now for big N, we choose a prime, P,
06:22
and then this integers mod P, they represent what we call the finite field with P elements. And you can think of this as a set that has exactly P elements, and it really kind of behaves like the real numbers. You can add numbers, you can subtract numbers, you can divide by everything but zero.
06:41
And this finite field with P elements works really the same. It's just a finite set, but everything is invertible except zero. And these are the numbers that we're going 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 mod P to the R.
07:03
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's all you need to know. Okay, so the cryptographic problem that I want to focus in this talk is simple key exchange. I'm not gonna talk about signatures, not gonna talk about encryption, nothing.
07:22
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 couldn't bring it to Alice, or I could somehow pay someone to bring the suitcase to Alice. Or maybe people heard about that thing
07:41
where I put my lock on the box, and I ship it to Alice, and she puts her lock on the box, and then she ships it back, and I remove my lock, and then I ship it to Alice again. Okay, so there are countless ways, but we want to somehow do this in a nice instantaneous kind of way using mathematics. So this simple problem is what we're going to focus on.
08:01
And classically, whatever that means for now, this has been solved by Diffie and 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
08:22
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 that we just saw,
08:41
and the 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's Alice and Bob,
09:01
and they agree on these two parameters, okay? And now, how do they 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 as G to the small a mod N to Bob. And as you might have guessed it, because I said it symmetrical, Bob does the same.
09:23
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, now they have to combine this somehow, right, and how did they do this?
09:42
So this is nice. They compute this shared KK, 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, through mathematics, they both get the same small K. And now,
10:02
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, I wanna teach you a bit about that as well. So this is this diagram, this commutative diagram,
10:21
somehow that represents this key exchange that just happened. Okay, so Bob and Alice, they both start in the left upper corner with the G, and they both end up in the lower right corner, the G to 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.
10:41
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 he knows, and no one else does. And I mean, by the commutativity and associativity of exponentiation, they just agree on the same G to the AB,
11:01
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,
11:23
it's hard to find the small x. It's 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.
11:43
And the best classic 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 this DLP problem. The best algorithm somehow has runtime square root of big N of the number of elements.
12:01
And say I chose my N about the size of two to the small N, so N bits. Then solving this takes exponential time in N, right? Because the square root of two to the N is still pretty big. Okay, this is about two to the N half, and if I make N, I don't know, 1,000,
12:20
it's still 512 bits. So this is a hard problem. But recently there has been a record for factoring and DLPing over a 795 bit modulus. And they used a bit of a better algorithm, but still, I mean, it still took them a long time, okay?
12:40
So if I remember correctly, this feat took them 4,000 core years on a 2.1 gigahertz computer. I mean, it's still 4,000 core years. So this is a long time, okay? But as you can see, it's possible to solve this. I mean, if I just put enough, if I have big enough hammer, I can solve this, okay? But again, you can make N pretty big,
13:03
bigger than anything being able to solve this anymore. But, okay, so there's 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,
13:21
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 100, 100 cube, it's not that big. And I can make N 1,000 by 1,000 cube, it's 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,
13:42
but still, this algorithm in theory breaks the DLP, okay? So I don't know, maybe in 20 years, or in 30 years, or 100 years, I don't know personally, but if there is a quantum computer eventually that somehow runs this thing, okay, DLP is broken, classically. So, well, what to do?
14:01
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 the zoo, let's use codes, this long word, anisotenies, okay?
14:21
Now what I want to tell you about is what is anisoteny, and how do I do key exchange with anisoteny, okay? Because I don't know, it's a fancy word, but what does it mean, okay? And there was this other word that started with elliptic curve isoteny, so probably I should tell you about what is an elliptic curve, or give you a remainder if you've seen this before.
14:43
So I look at this equation in two variables and two constants, the variables are 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.
15:03
And of course you'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 this discreteness.
15:21
And over r, a simple equation, I just chose some values for a and b, b is set to zero, a is set to one, a is set to zero, b is 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.
15:41
But over my finite field, and I chose one with 101 elements, it looks like this set of points, okay? So elliptic curves look differently over different fields, but that's fine, that's fine. Okay, now a quick reminder of why people like elliptic curves. So there's something called the point addition law.
16:02
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's somehow a law that I have to apply, and let me quickly show off how this is done. So how do you add two points on this curve? Well, you take these two points, you put a line through it,
16:21
and then there is a law that says that if I put a line through two points, then this line has to cut the curve in the third point. So I put the line through these two points, it cut the curve in the third point all the way up on the right, and now what I'm going to do is I'm going to reflect the point down on the x-axis.
16:42
So I draw this other line, I reflect it down, and then what I define is that other 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 inverses,
17:01
so this kind of like acts 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 a 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,
17:21
well, 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 at the point n times two itself, okay?
17:40
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 this special set here that I denoted E brackets big N, and these are all the points on the curve, such that if I multiply this point by n,
18:00
it gives me zero, okay? And this set, for the mathematically inclined people among us, I will say this is somehow the n-tortion of the elliptic curve, whatever that means, but if you're interested, you can look it up. This set kind of acts like additive integers mod n, like two copies of it, okay?
18:22
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 which other numbers, but over this finite field, and if you look at the p-tortion, the p-tortion, then this behaves differently for different types of curves,
18:42
okay, the p-tortion is either empty, then we call the curve super singular, or it's just one copy 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 somehow ingrained mathematically deep down there.
19:04
And because this E n-tortion is somehow two copies 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
19:21
instead of somehow exponential generators, but everything behaves kind of similar. And now you can really use this to do cryptography already, if you wanted to, right? You can somehow look at the DLP in that group, but there is the problem again that the DLP in there, but there is Shor's algorithm again, right? So even if you do cryptography in this group,
19:44
you run into the same problem. Okay, so we have to do a bit better, we have to search further. And this is where isortinies come into play. So one way you can think of an isortiny
20:02
is remember how we found the integers mod n by somehow dividing set by all the n multiples. And you can do something similar with an elliptic curve. You can somehow take part of this n torsion and you can divide an elliptic curve by this,
20:22
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.
20:41
And there's something else that comes along with this construction. And this is what we call the isortiny. This is a map, okay? Along with this construction comes a map from e1 to e2, and this map is what we call an isortiny. So for us now, an isortiny is just a map that takes us from one curve to another curve, okay?
21:04
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,
21:20
or I can take two points on my starting curve, I can send it through the map and add it over there, and it gives me the same thing, okay? So this map somehow behaves nicely with point addition. That's pretty nice, just as a side note. So this map is special. So this is just a remainder of what I said.
21:41
Adding points on e1 and sending the result to e2 is the same as somehow sending points to e2 and adding them there. So this map somehow plays nicely with my laws on my elliptic curve. And now I have to make a definition. So in mathematics, we call the kernel of a map.
22:00
We call the set of all the inputs to the map that are sent to zero, okay? 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, okay? And in written notation, it's the set of all P on e1
22:21
such that the map of P is zero. And turns out that this kernel for my isogeny that I started out with somehow recovers this part of the end torsion that I used to construct it. Okay, so there are somehow two ways now to think of an isogeny.
22:42
So this is what we started with. We considered 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, okay? So somehow there are two ways to represent this map. We can think of a subgroup, this G,
23:00
or we can think of the map. And ultimately, somehow there is a correspondence between the various subgroups for different N, and isogeny is somehow emanating from a curve. You can think of this like all the hairs on my head, they're going out, and then they're going to reach other elliptic curves maybe. And these notions can be used interchangeably.
23:23
So somehow there's a correspondence. And again, I can choose different Ns, okay? So somehow from one curve, I can have many, many outgoing isogenies that are different in a sense. And now the thing is, in practice, we actually want to compute with these maps.
23:41
So right now, this is just general abstract nonsense. I didn't tell you anything of how to compute with these things. I just told you there are somehow correspondences, but I mean, what does it even mean, right? It's useless if I can't use it in practice. And then there's another thing, you can compute these things, there are formulas, people have worked on this, but somehow the cost grows if I enlarge an N.
24:04
Okay, so really in practice for applications, I want to choose small N, okay? Maybe two or three, that would be pretty good. And now the thing is, it's the super singular curves for which I can somehow control or choose the possible Ns very, very easily, okay?
24:20
So this is the reason why we consider super singular curves. And now I can choose my prime to be of this form, and then magically, this is going to force two and three being possible, okay? So this is the reason why we choose super singular ones. There's some theory, which is not interesting for you,
24:42
but it's just, it's important for implementation, and there's a way, basically, for us to force the curve to have those isotrophes that we like. But there's another important reason, okay? And this is the reason that actually makes it interesting for cryptography.
25:01
So what I can do is, I start with an arbitrary curve, and this might not be a super singular one, just any curve, and say I consider all the outgoing two isotrophes, if these are possible, for N is two. So there's going to be one, two, and three. And then again, from E1, I can again consider
25:22
all the outgoing isotrophes, 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 isotrophes, okay? So somehow, behind the scenes, there's this graph hidden. And now, it turns out that if you do this
25:44
for a super singular elliptic curve, then I generated this yesterday for you. So this is one possible graph. I can't remember which prime I took, but here you can see all the ellipses are elliptic curves and all the edges between them are two isotrophes. So this is an example of a super singular
26:01
two isotrophes graph. Okay, this looks pretty wild. So I can do the same for, say, N is three, if it's possible, or N is five, and so on and so forth. So there are many, many graphs hidden. But why is the super singular graph specific and important? Well, it turns out that somehow the super singular one is connected,
26:22
and it's what we call a Ramanujan graph, okay? And this is, 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 arithmetic in the finite field with P squared elements.
26:40
This is nice, okay? So I'm just gonna say that if you don't consider super singular elliptic 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, okay? But super singular ones is nice.
27:01
So FP squared is enough for us. 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? So a Ramanujan graph has certain optimal expansion properties. And this means that if I start from a random point
27:21
in my graph and I take a random walk with somehow logarithmic, log many steps of the total amount of vertices, then this will put me in a very uniform place in that graph, okay? And this is good for cryptography, okay?
27:41
Because you only need to take log many steps to somehow randomize yourself in that graph. And this is what this could look like. So I started at that red ellipsis over there. This was my starting point. And then I generated a few random walks. And the blue points are where I got placed.
28:01
This might not prove anything, but it gives you an idea of how somehow uniformly it places me around that graph, okay? So it's good for cryptography, but there are other reasons. So super-singular curves somehow, I can actually compute how many of these curves
28:22
I will have in my graph. So 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 super-singular ones, I can say they're roughly p over 12 many, okay? And then again, if I choose my p about n bits,
28:42
well, then I will know that my graph is about two to the n elements. And at least there I can say something about the cryptographic strength, right? I can make n big, and then you can say, oh yeah, you have this random graph, you take some n length walks, and then it places you randomly in there, and the whole graph is about two to the n elements,
29:00
and then I can say something about the expected runtime of algorithms, right? So this is another reason why we want to consider super-singular curves, because I can tell you how many elements are in this graph. Okay, so a quick summary of what we saw, why this is nice. So what you get is somehow a compact representation
29:21
of an L plus one regular graph, and we saw examples, for example, L is two or L is three. Bigger values are possible, but we don't even care about those because this is what gives us the fastest somehow arithmetic such that we can work over f p squared. This is nice, this keeps our implementation fast.
29:41
I can tell you how many vertices are in my graph, about p over 12, and again, such that the graph has some 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 big prime p, then the graph has about two to the n vertices,
30:02
so exponentially many vertices. And 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.
30:22
I take two super singular elliptic curves, so I just give you two random curves in this graph, and I ask you, find an isogeny path between those of two isogenies, or three isogenies. And it turns out somehow that this doesn't have good quantum algorithm. So classically, the numbers are not super important here,
30:41
but classically the complexity is p over, the fourth root of p, and the best quantum algorithm is a bit better. I mean, again, it's not super important what's there. What's important is that there is no polynomial time algorithm compared to our DLP that we started with. So if I make this p very large,
31:02
your quantum computer, your hypothetical quantum computer will probably not solve this. So that's cool. So how do we do key exchange? So I start with a super singular elliptic curve e where I chose my prime p such that two and three isogenies are possible.
31:21
And then Alice, earlier remember she chose a random number a, but now Alice will choose a random subgroup big A, and she will send e mod a to Bob. This amounts to Alice for computing an isogeny. And again, this is a very symmetrical key exchange,
31:41
except that now Bob won't use the same generator, but Bob will use the three 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. Again, Alice chose a, Bob chooses b.
32:00
Alice sends e mod a to Bob. Bob sends e mod b to Alice. And then how do they somehow agree on the shared key? Well, the way they're going to agree is they will just mod out by their respective subgroups again. And turns out the elliptic curve that they find is going to be the same for both of them. Okay, so how does that work?
32:21
Again, let's return to our graph. So say Alice and Bob, they agree on the 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
32:43
at the red curve in the upper right corner. And Bob will do the same, but now Bob is not in the two graph, but in the three graph, so this is the three graph. And the black curve that they started from in the three graph is down there. And he will also select the random subgroup, compute the secret path,
33:01
and Bob will end up in the blue curve. And 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 two graph. Okay, so Alice, she starts from the blue curve that you got from Bob. And this is the position in the two graph. And again, she computes that same secret path,
33:22
and ends up in the green curve, which is up there. Bob got the red curve from Alice. So Bob, he has the red curve there. Again, computes that path, and then ends up at the green curve. And it turns out that the green curves here and there, they are the same. And this is going to be the shared key for them.
33:40
This is SIDH. Okay, this is how you exchange a secret key using the super-singular isogenic graph. And that's somehow the whole magic. And again, let's compare these two things a bit, the DLP-based one and the SIDH one.
34:01
So we had this square, where Alice and Bob started in the upper left corner, and again, ended up in the lower right corner. And now SIDH looks very similar, okay? So Alice and Bob start with this common curve E in the upper left corner. Again, Alice computes only the horizontal arrows
34:22
because she knows her secret group big A. Bob only computes the vertical arrows because only he knows his secret group big B. And again, they both end up in the lower right corner, where they find a shared key. But now in this case, the shared key is not this element G to the AB,
34:42
but an elliptic curve. But again, there's a mathematical way somehow to attach a unique number to it. So it's a solved problem to somehow actually make some bytes out of this. And yeah, that's SIDH, that's everything. This is a nice example of a post-quantum,
35:03
somehow cryptography scheme that we have today. And now let me finish with a quick conclusion. So I showed you the SU. There are several candidates somehow for post-quantum cryptography. And among of them are some schemes based on super-singular elliptic curve isogonies.
35:23
And we've seen that we know some hard problems involving these isogonies that are somehow hard for quantum computers, which makes this one possible scheme for somehow a quantum computer world. And probably I should say that we don't envision
35:43
a world here where users like me or you are in possession of quantum computers. Probably what we think about is somehow that state actors are in possession of quantum computers. So this is even more important for us to be looking into these things. And what we saw was somehow to perform
36:01
a Diffie-Hellman-like key exchange using these isogonies. And this is what I didn't tell you about in this talk. There are also schemes for signatures based on isogonies. There is a scheme for key encapsulation based on isogonies. So there are other possible candidates for other somehow cryptographic building blocks
36:22
based on isogonies 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 somehow scientific papers, about isogonies and cryptography in general, you can find this on the ePrint archive.
36:42
So this is a web page where people post pre-prints about the papers. And there's a huge collection about among of them, isogony papers. So if you're interested in this, this is somehow the place to research. And with that, I would like to thank you all for your attention.
37:11
Okay, yeah. Yeah, is there any question?
37:20
Okay, I got the signal angel there doing some Morse code. Yes, can you recommend any literature for the theoretical background? Theoretical background. There are a few papers that are nice. Okay, the question again was
37:41
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 isogonies in the mask of search terms
38:01
or SIDH and you look at the papers that somehow say maybe a short introduction to isogonies, 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 are out there for sure. Yeah, and thanks for him. So there is a very recent paper by Craig Costello,
38:22
also somehow titled The Short Introduction, something like that. Yeah, so this is also maybe a good source for you to look at. Yeah, isogonies for beginners. Isogonies for beginners, thank you. Yeah. Hello, yeah. Yeah. So, you've used elliptic curve as an algebraic group,
38:45
right, to compute these isogony graphs. So why do you use elliptic curves? What's the properties of elliptic curves as a group? So, could you use any group to compute these graphs
39:04
and could you use these as the basis for your scheme, for your key exchange scheme? Okay, so the question was why use elliptic curves and the group structure that they impose to look at isogony graphs involving elliptic curves
39:23
and whether I could use maybe other groups. And actually, there's a twofold answer maybe. So if I go back, or actually let me go to my backup slide, which gives you SIDH in its full glory. I see there's some extra information being sent,
39:42
namely these generators for 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.
40:01
Okay, I mean it's really, really somehow that Richelieu property that makes the graph interesting for cryptography. But yes, in theory, the SIDH commutative diagram, you could also compute for other groups, yes.
40:20
Okay, how good are classical algorithms that try to reverse that SIDH problem? Because that will be the bound for how large your keys have to be secure. Yes, so the question was, how good are classical algorithms?
40:42
And again, I said, I think the runtime for those is square root of P. And this tells you how big you have to choose P. And how confident are you that this really is hard for a quantum computer as well?
41:01
Well, how confident am I that this is really hard for quantum computers? So first of all, cryptography is all about confidence. So someone proposes a problem, this problem gets cryptanalyzed. And if it's not broken after 40 years, then people will say, oh yeah, I'm pretty confident this is good. And maybe if the NSA doesn't tell you anything about it
41:20
or maybe if they don't have anything on it, then you can also see that you're confident in it. But I think this is really an answer that only time, this is a question that only time can answer, right? Yeah, I have a question from the same line. Is it possible to prove
41:41
that no polynomial time algorithms for the isogeny's problems can exist for a quantum computer? Yeah, that's a good question. How do you prove that no algorithm exists? This brings us into territories like, I don't know.
42:00
Yeah, no, let's not do that. Microphone one. Yeah, good talk by the way. The last slide you say that this is hard for a quantum, but that can't be true because we don't even know
42:20
if any algorithm's hard for classic computers, right? So I'm guessing you're saying that intuitively it feels hard, which is the same intuition we have about factoring and so on. So you mentioned there's multiple candidates for post quantum cryptography, and they all intuitively feel hard somehow.
42:42
Do you know if this specific candidate, would this be your horse in the race? Is there anything about this specific way that you think would be the best fit for post quantum cryptography? Okay, so your opinion is very valid. Of course, we don't know if it's hard, right?
43:02
This again connects back to the other questions. How do you trust something like that? Again, people do cryptanalysis for 40 years or whatever, and then you say, no one found anything, it's probably hard. Right, but it hasn't been 40 years for this. Exactly, you cannot say that. These things are relatively new.
43:20
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 somehow a mathematical curiosity, because I think these things are beautiful. And somehow the cryptography that arises from it is more of a side effect for me personally.
43:42
So I'm not gonna put out any somehow, guesses on which of these things is actually gonna win the PQ race or whatever, yeah. Hi, you showed or said you think it's hard for the classical way and for the quantum cryptography
44:00
way. I think I just read a paper last year about a combined way doing classical and quantum cryptography combined, which outperforms either one of those ways. Do you think this could also be, can be relevant or yeah, make this one way, yeah,
44:23
in computable and polynomial time? So are you talking about an algorithm that somehow combines a classical step and a quantum step to break this? Yeah, well, I mean, most algorithms somehow that we see use a quantum computer involve a classical part anyways.
44:41
I mean, 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, yeah. So, yeah. Signal Angel. Can you please name the mentioned contestants
45:02
in the NIST challenge based on isogenies? So there is PSYCH, I believe, super singular isogeny key encapsulation, but I actually, I don't really follow the NIST thing closely, so I actually couldn't even name all the names
45:22
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 the zoo. So they will tell you which contenders are based on legacies and which contenders are based on codes and which ones are somehow based on isogenies. But off the top of my head,
45:40
I actually, I don't even know, no? Sorry. Hey, microphone one. So if I got everything correctly, those isogenies are group homomorphisms between the elliptic curves and the factor group of the elliptic curve by G,
46:02
and which has kernel G again. And while 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 group homomorphism between the elliptic curve and the factor group with kernel G
46:22
is simply the canonical projection. 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 this slide actually, so the secrets are these alphas and betas,
46:40
which somehow determine the subgroup, and yes, so finding the 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 somehow restating the problem, but it's still hard somehow to find the subgroup.
47:01
All right, thanks. Thank you, very cool. Microphone two. Okay, 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,
47:21
like the choice of field of definition is difficult, for example, so. 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, somehow you can attach a dimension to these things in elliptic curves, somehow have a dimension one attached to them, and the question one was
47:41
can you somehow look at dimension two or dimension three 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 two or dimension three, but it turns out somehow that this DLP problem
48:00
actually at some point gets easier in higher dimension. Okay, so classically, if you look at the DLP, you somehow want to stay at dimension two, but now what you can do, of course, is you can look at isogenies between dimension two and dimension three ones, and actually the problem that arises there, and this makes elliptic curves very special, is that we can compute isogenies
48:21
rather efficiently for elliptic curves because of Beelu's formulas, okay? So somehow this gives us a very direct means of computing these, but it actually gets hard as the dimension grows. For example, for dimension two already, the only isogenies that I somehow am able to efficiently compute are two and three isogenies.
48:42
So there are some packages out there that can compute higher ones, but only if my prime is very small, and for dimension three and higher, it gets even harder, okay? And then there is another thing that comes into play. So dimension two varieties, somehow they all arise from what we call hyper-elliptic curves, but if you look at dimension threes and higher,
49:02
then somehow, sometimes you land at the point in your graph that does not come from a hyper-elliptic curve anymore, so there is another complication. So I mean, I had a friend who was looking into genus two isogenies, and it's possible to do there, but I don't know, I think personally this is more
49:22
of a toy than something that's good in practice, yeah. Can you use this scheme to implement a fully homomorphic encryption scheme, or is it already? No. No. No, yeah.
49:41
No, fully homomorphic encryption is somehow a pipe dream, but I mean, sometimes it's possible, so the idea is somehow that you can add ciphertexts and get the sum of the ciphertexts, and have a second somehow operation, namely you should be able to multiply ciphertexts and get the multiplication of those ciphertexts, but we didn't even talk
50:01
about encryption, okay, so, yeah. Another question, is there any crypto primitive used in the isogony approach that cannot be stark reduced to finding a hidden subgroup in an abling group? Could you repeat the question, please? Is there any crypto primitive used
50:21
in the isogony approach that cannot be stark reduced to finding a hidden subgroup in an abling group? Okay, so this, I think, this question tries to connect back to somehow maybe the hidden shift problem or the hidden subgroup problem in Kupferberg's algorithm,
50:41
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. What do you send an elliptic curve over the y? Yeah, maybe I should answer that, actually.
51:02
So, we saw the parametrization of the curve that had these coefficients, big A and big 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 elliptic curve, this is called a J invariant, it's a single integer
51:22
which somehow determines this elliptic curve uniquely. So, if I want to send an elliptic 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
51:41
which makes this also interesting. This isn't true. I get this is all. Thank you.
Recommendations
Series of 13 media