[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:25.28,Default,,0000,0000,0000,,{\i1}36C3 preroll music{\i0}\N{\i1}Applause{\i0}
Dialogue: 0,0:00:25.28,0:00:30.37,Default,,0000,0000,0000,,naehrwert: Yeah. Thank you for the\Naudience and thanks that you came. Thanks
Dialogue: 0,0:00:30.37,0:00:34.53,Default,,0000,0000,0000,,for the Congress for giving me the\Nopportunity to be here tonight, to be able
Dialogue: 0,0:00:34.53,0:00:39.88,Default,,0000,0000,0000,,to tell you a bit about post quantum\Ncryptography, a bit about as isogenies. I
Dialogue: 0,0:00:39.88,0:00:44.39,Default,,0000,0000,0000,,mean, just educate the people a bit about\Nwhat that means, even, because I'm not too
Dialogue: 0,0:00:44.39,0:00:52.50,Default,,0000,0000,0000,,sure how many of you heard about that\Nbefore. Yeah, let's just jump right in. So
Dialogue: 0,0:00:52.50,0:00:57.41,Default,,0000,0000,0000,,my day job is being a mathematics PhD\Nstudent at an undisclosed university. You
Dialogue: 0,0:00:57.41,0:01:03.32,Default,,0000,0000,0000,,can ask me in private if you're\Ninterested. So previously I did physics. I
Dialogue: 0,0:01:03.32,0:01:07.45,Default,,0000,0000,0000,,was also or maybe I'm still a bit active\Nin the console hacking scene. And if
Dialogue: 0,0:01:07.45,0:01:12.32,Default,,0000,0000,0000,,you're interested about that shameless\Nplug, you can find us at Nintenbros
Dialogue: 0,0:01:12.32,0:01:17.22,Default,,0000,0000,0000,,Assembly later. You can ask us all about\Nour somehow console hacking endeavors. But
Dialogue: 0,0:01:17.22,0:01:24.22,Default,,0000,0000,0000,,enough about that. So I brought you some\Npictures, screenshots of websites. So I
Dialogue: 0,0:01:24.22,0:01:28.67,Default,,0000,0000,0000,,don't know if you have seen the chatter on\Nsocial media and the blogs here recently
Dialogue: 0,0:01:28.67,0:01:36.21,Default,,0000,0000,0000,,about that Google paper on quantum\Nsupremacy. So there is a Nature article
Dialogue: 0,0:01:36.21,0:01:42.28,Default,,0000,0000,0000,,about that beyond quantum supremacy. And\Nthere is a Verge article that Google
Dialogue: 0,0:01:42.28,0:01:47.70,Default,,0000,0000,0000,,confirms quantum supremacy and\Nbreakthrough, whatever that means. There
Dialogue: 0,0:01:47.70,0:01:52.02,Default,,0000,0000,0000,,is Google's own blog post about it. Notice\Nthere are always these shiny pictures of
Dialogue: 0,0:01:52.02,0:01:57.91,Default,,0000,0000,0000,,these huge tubs filled with helium where\Nthey house these quantum computers. So
Dialogue: 0,0:01:57.91,0:02:04.08,Default,,0000,0000,0000,,supremacy means the state or condition of\Nbeing superior to all others in authority,
Dialogue: 0,0:02:04.08,0:02:11.13,Default,,0000,0000,0000,,power, or status. So calling something\Nquantum supremacy, I mean, that screams
Dialogue: 0,0:02:11.13,0:02:16.42,Default,,0000,0000,0000,,something being pretty amazing. But what\Nactually does this mean for us? What does
Dialogue: 0,0:02:16.42,0:02:22.98,Default,,0000,0000,0000,,it mean for cryptography? And I think I\Ncan relieve you all about from from maybe
Dialogue: 0,0:02:22.98,0:02:29.29,Default,,0000,0000,0000,,some fears that you had for us in\Npractice. Maybe today it doesn't really
Dialogue: 0,0:02:29.29,0:02:36.23,Default,,0000,0000,0000,,mean anything yet. So for cryptography\Nnone of our underlying assumptions,
Dialogue: 0,0:02:36.23,0:02:40.60,Default,,0000,0000,0000,,whatever it means for now, are being\Nactively broken yet as we know or that we
Dialogue: 0,0:02:40.60,0:02:46.91,Default,,0000,0000,0000,,know of. But in theory, they are broken.\NOkay. And because they're only broken in
Dialogue: 0,0:02:46.91,0:02:50.35,Default,,0000,0000,0000,,theory, that's pretty good. So we can\Nstill blame the designers and implementers
Dialogue: 0,0:02:50.35,0:02:57.08,Default,,0000,0000,0000,,of whatever we cook up for when things go\Nwrong. So that's nice, too. But as I
Dialogue: 0,0:02:57.08,0:03:01.97,Default,,0000,0000,0000,,already wrote in the abstract a bit for\Nthis talk, we should be, somehow, better
Dialogue: 0,0:03:01.97,0:03:06.98,Default,,0000,0000,0000,,be safe than sorry. So instead of somehow\Nwaiting until the point of where quantum
Dialogue: 0,0:03:06.98,0:03:11.06,Default,,0000,0000,0000,,computers somehow become feasible to break\Nour cryptography, we should probably
Dialogue: 0,0:03:11.06,0:03:16.07,Default,,0000,0000,0000,,research it today. It's a bit with the\Nclimate change, right? Suppose it's right
Dialogue: 0,0:03:16.07,0:03:19.50,Default,,0000,0000,0000,,to save our climate today instead of\Nwaiting until it's too late. So if we're
Dialogue: 0,0:03:19.50,0:03:24.90,Default,,0000,0000,0000,,going to be reborn to do the same for\Ncryptography. There are also three
Dialogue: 0,0:03:24.90,0:03:30.92,Default,,0000,0000,0000,,upcoming talks I want to advertise here a\Nbit. I think I don't remember the days,
Dialogue: 0,0:03:30.92,0:03:34.52,Default,,0000,0000,0000,,but descriptions look pretty interesting.\NSo I'm going to leave that up for a few
Dialogue: 0,0:03:34.52,0:03:38.87,Default,,0000,0000,0000,,seconds. There is one called Provable\NInsecurity, one called Cryptography
Dialogue: 0,0:03:38.87,0:03:42.82,Default,,0000,0000,0000,,Demystified and one about high assurance\Ncryptography software. I'm sure this is
Dialogue: 0,0:03:42.82,0:03:48.59,Default,,0000,0000,0000,,gonna be interesting. Okay, let's return\Nback to what I want to talk about. So
Dialogue: 0,0:03:48.59,0:03:53.81,Default,,0000,0000,0000,,there's something I chucklingly call the\NPost-Quantum Cryptography Zoo. There are a
Dialogue: 0,0:03:53.81,0:03:57.78,Default,,0000,0000,0000,,few buzzwords up there. You don't really\Nhave to know what they mean. I'm just
Dialogue: 0,0:03:57.78,0:04:01.60,Default,,0000,0000,0000,,going to say them out loud. Lattices,\Ncodes, multivariate polynomial systems.
Dialogue: 0,0:04:01.60,0:04:07.31,Default,,0000,0000,0000,,That's also a bit of a mouthful. And hash\Nbased cryptography. And there is the one
Dialogue: 0,0:04:07.31,0:04:11.76,Default,,0000,0000,0000,,that I want to briefly talk about tonight\Ncalled supersingular elliptic curve
Dialogue: 0,0:04:11.76,0:04:16.20,Default,,0000,0000,0000,,isogenies. OK, so this is the stuff that I\Nreally like. Isogenies, they are great.
Dialogue: 0,0:04:16.20,0:04:21.97,Default,,0000,0000,0000,,And now I'm going to tell you why they're\Nso great. All right. So I don't know how
Dialogue: 0,0:04:21.97,0:04:26.37,Default,,0000,0000,0000,,many of you have a mathematics background.\NMaybe I can do a test. Can people raise
Dialogue: 0,0:04:26.37,0:04:32.88,Default,,0000,0000,0000,,their hands where if they have some formal\Ntraining in, say, algebra? Yeah. Okay. So
Dialogue: 0,0:04:32.88,0:04:37.76,Default,,0000,0000,0000,,that's pretty good. So I'm just gonna tell\Nyou some something about it. There are
Dialogue: 0,0:04:37.76,0:04:42.58,Default,,0000,0000,0000,,decimal numbers. This is Pi. Then there\Nare rational numbers somehow the are, one
Dialogue: 0,0:04:42.58,0:04:46.34,Default,,0000,0000,0000,,half, one third and so on and so forth.\NThen there are integers from minus
Dialogue: 0,0:04:46.34,0:04:52.89,Default,,0000,0000,0000,,infinity to plus infinity and they follow\Nnice whole steps. But for working with
Dialogue: 0,0:04:52.89,0:04:56.62,Default,,0000,0000,0000,,those numbers and for cryptography, we\Nwant something that's nicer behaved. We
Dialogue: 0,0:04:56.62,0:05:01.50,Default,,0000,0000,0000,,want somehow a finite set. OK. So this is\Njust important for implementation. And the
Dialogue: 0,0:05:01.50,0:05:05.35,Default,,0000,0000,0000,,ones that we want to work with, I'm just\Ngoing to remind you, are the integers
Dialogue: 0,0:05:05.35,0:05:11.62,Default,,0000,0000,0000,,modulo N, so we take some positive integer\NN, big N, and then we consider the set
Dialogue: 0,0:05:11.62,0:05:16.60,Default,,0000,0000,0000,,from zero to N minus one. Okay. And these\Nnumbers do follow certain addition and
Dialogue: 0,0:05:16.60,0:05:20.25,Default,,0000,0000,0000,,multiplication rules and it pretty much\Nworks like a clock face. OK. I chose N is
Dialogue: 0,0:05:20.25,0:05:24.57,Default,,0000,0000,0000,,12 here and, just bear with me, imagine my\Nclock face goes from zero to eleven
Dialogue: 0,0:05:24.57,0:05:28.93,Default,,0000,0000,0000,,instead of from one to twelve. But it's\Nreally the same. For example, if I tried
Dialogue: 0,0:05:28.93,0:05:35.24,Default,,0000,0000,0000,,to add ten to five. OK, I start from ten.\NI go two steps and then I arrive at zero.
Dialogue: 0,0:05:35.24,0:05:38.79,Default,,0000,0000,0000,,This is where my clock ticks over. Right.\NLike on a real clock. And then you go
Dialogue: 0,0:05:38.79,0:05:44.13,Default,,0000,0000,0000,,three more steps. And so ten plus five mod\Ntwelve is three. So it's numbers that kind
Dialogue: 0,0:05:44.13,0:05:49.55,Default,,0000,0000,0000,,of behave this way. Think of addition on\Non a clock face. And for the computer
Dialogue: 0,0:05:49.55,0:05:54.53,Default,,0000,0000,0000,,scientists out there or, I mean, everyone\Nprobably knows about that, for a computer
Dialogue: 0,0:05:54.53,0:05:58.93,Default,,0000,0000,0000,,they're like the 8 bit integers where N is\N2 to the 8. And then these are the numbers
Dialogue: 0,0:05:58.93,0:06:03.67,Default,,0000,0000,0000,,from 0 to 255, and so on and so forth. So\Nthese are the numbers that we want to work
Dialogue: 0,0:06:03.67,0:06:12.72,Default,,0000,0000,0000,,with. Just to set the stage a bit. And\Nthese isogenies. We will live in a world
Dialogue: 0,0:06:12.72,0:06:18.02,Default,,0000,0000,0000,,where we we work with somehow related\Nnumbers to these integers mod N. And now
Dialogue: 0,0:06:18.02,0:06:25.25,Default,,0000,0000,0000,,for big N, we choose a prime P and then\Nthese integers mod P, they represent what
Dialogue: 0,0:06:25.25,0:06:30.69,Default,,0000,0000,0000,,we call the finite field with P elements.\NOkay. And you can think of this as a set
Dialogue: 0,0:06:30.69,0:06:35.93,Default,,0000,0000,0000,,that has exactly P elements and really\Nkind of behaves like the real numbers.
Dialogue: 0,0:06:35.93,0:06:39.02,Default,,0000,0000,0000,,Okay. You can add numbers, you can\Nsubtract numbers. You can divide by
Dialogue: 0,0:06:39.02,0:06:42.92,Default,,0000,0000,0000,,everything but zero. Okay. And this finite\Nfield with P elements works really the
Dialogue: 0,0:06:42.92,0:06:46.84,Default,,0000,0000,0000,,same. It's just a finite set, but\Neverything is invertable except zero.
Dialogue: 0,0:06:46.84,0:06:50.20,Default,,0000,0000,0000,,Okay. And these are the numbers that we\Nwant to work with and computers can do
Dialogue: 0,0:06:50.20,0:06:56.51,Default,,0000,0000,0000,,that. So that's fine. And just for the\Nsake of telling you, there are also fields
Dialogue: 0,0:06:56.51,0:07:02.100,Default,,0000,0000,0000,,that have somehow P to the R elements, but\Nthey are not the same as what people are.
Dialogue: 0,0:07:02.100,0:07:06.48,Default,,0000,0000,0000,,Okay. But there is a way to construct it.\NBut that's all you need to know about. So
Dialogue: 0,0:07:06.48,0:07:09.93,Default,,0000,0000,0000,,this is really the set of numbers that\Nwe're going to work over and that that's
Dialogue: 0,0:07:09.93,0:07:15.58,Default,,0000,0000,0000,,all you need to know. Okay. So the\Ncryptographic problem that I want to focus
Dialogue: 0,0:07:15.58,0:07:20.15,Default,,0000,0000,0000,,on this talk is simple key exchange. I'm\Nnot gonna talk about signatures, I'm not
Dialogue: 0,0:07:20.15,0:07:23.64,Default,,0000,0000,0000,,going to talk about encryption, nothing.\NLet's just focus on this one simple
Dialogue: 0,0:07:23.64,0:07:29.53,Default,,0000,0000,0000,,problem of how do Alice and Bob exchange a\Nkey without anyone else somehow getting
Dialogue: 0,0:07:29.53,0:07:33.32,Default,,0000,0000,0000,,access to that key? And I mean, there are\Nsomehow classical solutions to that. I
Dialogue: 0,0:07:33.32,0:07:37.05,Default,,0000,0000,0000,,could put my key in a suitcase and I could\Nbring it to Alice or I could somehow pay
Dialogue: 0,0:07:37.05,0:07:41.38,Default,,0000,0000,0000,,someone to bring the suitcase to Alice. Or\Nmaybe people heard about the thing where I
Dialogue: 0,0:07:41.38,0:07:44.83,Default,,0000,0000,0000,,put my lock on the box and I ship it to\NAlice and she puts her lock on the box and
Dialogue: 0,0:07:44.83,0:07:49.01,Default,,0000,0000,0000,,she ships ships it back now I remove my\Nlock and I ship it to Alice again. OK, so
Dialogue: 0,0:07:49.01,0:07:53.61,Default,,0000,0000,0000,,there are countless ways, but we want to\Nsomehow do this in a nice, instantaneous
Dialogue: 0,0:07:53.61,0:07:59.98,Default,,0000,0000,0000,,kind of way using mathematics. Okay. So\Nthis simple problem is what we're going to
Dialogue: 0,0:07:59.98,0:08:05.95,Default,,0000,0000,0000,,focus on. And classically (whatever that\Nmeans for now) this has been set off by
Dialogue: 0,0:08:05.95,0:08:09.78,Default,,0000,0000,0000,,Diffie-Hellman. And this is this nice\Npaper from 1979 the title is New
Dialogue: 0,0:08:09.78,0:08:13.85,Default,,0000,0000,0000,,Directions in Cryptography. So this\Nalready tells you that something important
Dialogue: 0,0:08:13.85,0:08:20.26,Default,,0000,0000,0000,,must be going on and what you somehow\Ninvented there was a way to exchange keys
Dialogue: 0,0:08:20.26,0:08:27.18,Default,,0000,0000,0000,,between two parties using a nice, well-\Ndefined problem. Okay. And how does it
Dialogue: 0,0:08:27.18,0:08:31.54,Default,,0000,0000,0000,,work? Okay. I'm just gonna tell you how it\Nworks. So there are two parties, Alice and
Dialogue: 0,0:08:31.54,0:08:39.25,Default,,0000,0000,0000,,Bob. A and B. They agree on a safe prime\Nmodulus, N. Okay. So this is the integers
Dialogue: 0,0:08:39.25,0:08:45.03,Default,,0000,0000,0000,,mod N, which I saw, and a generator G. So\Nwhat does that mean? Basically in my set,
Dialogue: 0,0:08:45.03,0:08:50.16,Default,,0000,0000,0000,,from zero to N, I want to single out one\Nelement such that every element can be
Dialogue: 0,0:08:50.16,0:08:54.57,Default,,0000,0000,0000,,written as a power of that element. And\Nsomehow this means it generates it. Right.
Dialogue: 0,0:08:54.57,0:09:00.11,Default,,0000,0000,0000,,So every Y can be written as G to the X\Nmod N. Okay, this is my setup. And then
Dialogue: 0,0:09:00.11,0:09:06.25,Default,,0000,0000,0000,,there is Alice and Bob and they agree on\Nthese two parameters. Okay. And now how do
Dialogue: 0,0:09:06.25,0:09:12.20,Default,,0000,0000,0000,,we do the key exchange? So it's very\Nsymmetrical. So Alice chooses a random A
Dialogue: 0,0:09:12.20,0:09:17.20,Default,,0000,0000,0000,,in the set from one to N minus one. And\Nshe sends big A is G to the small a mod N
Dialogue: 0,0:09:17.20,0:09:21.59,Default,,0000,0000,0000,,to Bob. And as you might have guessed it,\Nbecause I said it's symmetrical, Bob does
Dialogue: 0,0:09:21.59,0:09:26.82,Default,,0000,0000,0000,,the same. Okay. So how does the picture\Ngo? So Alice on the left, she chooses a
Dialogue: 0,0:09:26.82,0:09:33.29,Default,,0000,0000,0000,,random small A. And she sends that big A\Nto Bob. Bob chooses a random small B. He
Dialogue: 0,0:09:33.29,0:09:38.12,Default,,0000,0000,0000,,sends the big B to Alice. And then\Nsomehow, you know, you have to combine
Dialogue: 0,0:09:38.12,0:09:45.08,Default,,0000,0000,0000,,them somehow. Right. How do you do this?\NSo this is nice to compute the shared k,
Dialogue: 0,0:09:45.08,0:09:50.55,Default,,0000,0000,0000,,the shared key. So Alice takes the B, she\Ngot from Bob and raises it to the power of
Dialogue: 0,0:09:50.55,0:09:56.38,Default,,0000,0000,0000,,her own random secret value. And Bob does\Nthe same. And magically from mathematics,
Dialogue: 0,0:09:56.38,0:10:04.27,Default,,0000,0000,0000,,they both get the same small k. And now\NI'm going to tell you why, somehow, this
Dialogue: 0,0:10:04.27,0:10:11.75,Default,,0000,0000,0000,,is hard for anyone else to get the same\Nsmall k. So now bear with me. I'm gonna
Dialogue: 0,0:10:11.75,0:10:16.12,Default,,0000,0000,0000,,write it down mathematically, first of\Nall, why not teach you a bit about that as
Dialogue: 0,0:10:16.12,0:10:21.29,Default,,0000,0000,0000,,well? So this is this diagram, this\Ncommutative diagram that somehow
Dialogue: 0,0:10:21.29,0:10:24.93,Default,,0000,0000,0000,,represents this key exchange that just\Nhappened. Okay. So Bob and Alice, they
Dialogue: 0,0:10:24.93,0:10:30.78,Default,,0000,0000,0000,,both started in the left upper corner with\Nthe G and they both end up in the lower
Dialogue: 0,0:10:30.78,0:10:35.27,Default,,0000,0000,0000,,right corner, the G the AB. So they both\Nare able to somehow compute G to the AB
Dialogue: 0,0:10:35.27,0:10:39.09,Default,,0000,0000,0000,,and no one else is. And how does that\Nwork? Well, Alice will only compute the
Dialogue: 0,0:10:39.09,0:10:43.99,Default,,0000,0000,0000,,horizontal arrows, so she only raises to\Nthe power of small A because that's her
Dialogue: 0,0:10:43.99,0:10:48.54,Default,,0000,0000,0000,,random secret that only she knows. And Bob\Nonly computes the vertical arrows, so he
Dialogue: 0,0:10:48.54,0:10:51.80,Default,,0000,0000,0000,,only raises to the power of small B,\Nbecause that's the secret to he knows and
Dialogue: 0,0:10:51.80,0:10:57.49,Default,,0000,0000,0000,,no one else does. And I mean by the\Ncommutativity and the associativity of
Dialogue: 0,0:10:57.49,0:11:02.82,Default,,0000,0000,0000,,exponentiation, they just agree on the\Nsame G to the AB which is which is cool.
Dialogue: 0,0:11:02.82,0:11:08.52,Default,,0000,0000,0000,,And somewhere in there there hides a\Nproblem that we like to call the discrete
Dialogue: 0,0:11:08.52,0:11:13.55,Default,,0000,0000,0000,,logarithm problem and it just happens for\Nintegers mod N if I choose my N
Dialogue: 0,0:11:13.55,0:11:17.41,Default,,0000,0000,0000,,appropriately, I'm not gonna tell you how,\Nbut just believe me if I choose it
Dialogue: 0,0:11:17.41,0:11:25.67,Default,,0000,0000,0000,,appropriately. If I give you Y and G, for\Nyou it's hard to find the small X. Somehow
Dialogue: 0,0:11:25.67,0:11:30.04,Default,,0000,0000,0000,,like taking a logarithm, and we call it\Nthe discrete logarithm because it's a
Dialogue: 0,0:11:30.04,0:11:33.72,Default,,0000,0000,0000,,discrete set of numbers instead of the\Ncontinuous decimal numbers, what we
Dialogue: 0,0:11:33.72,0:11:37.72,Default,,0000,0000,0000,,started with was this discrete finite set\Nof numbers and this DLP is hard. Okay.
Dialogue: 0,0:11:37.72,0:11:44.78,Default,,0000,0000,0000,,This is a hard problem for classical\Ncomputers. And the best classical generic
Dialogue: 0,0:11:44.78,0:11:49.72,Default,,0000,0000,0000,,algorithm - I'm not gonna talk about\Nsomehow algorithms that specifically
Dialogue: 0,0:11:49.72,0:11:54.89,Default,,0000,0000,0000,,target integers mod N, I'm just going to\Ntalk about generic algorithms for for this
Dialogue: 0,0:11:54.89,0:11:59.60,Default,,0000,0000,0000,,DLP problem. The best algorithm somehow\Nhas run time square root of big N the
Dialogue: 0,0:11:59.60,0:12:06.71,Default,,0000,0000,0000,,number of elements and say I chose my N\Nabout the size of 2 to the small n, or n
Dialogue: 0,0:12:06.71,0:12:13.23,Default,,0000,0000,0000,,bits. Then solving this takes exponential\Ntime in n, right, because the square root
Dialogue: 0,0:12:13.23,0:12:17.77,Default,,0000,0000,0000,,of 2 to the n is still pretty big. Okay,\Nthis is about 2 to the n half, and if I
Dialogue: 0,0:12:17.77,0:12:24.98,Default,,0000,0000,0000,,make n a thousand is still 512 bits. So\Nthis is a hard problem. But recently there
Dialogue: 0,0:12:24.98,0:12:33.54,Default,,0000,0000,0000,,has been a record for factoring and DLPing\Nover a seven hundred ninety five bit
Dialogue: 0,0:12:33.54,0:12:39.04,Default,,0000,0000,0000,,modulus and they use a bit of a better\Nalgorithm, but still, I mean it still took
Dialogue: 0,0:12:39.04,0:12:46.02,Default,,0000,0000,0000,,them a long time. Okay, so if I remember\Ncorrectly, this feed took them 4000 core
Dialogue: 0,0:12:46.02,0:12:51.12,Default,,0000,0000,0000,,years on a two point one gigahertz\Ncomputer. I mean, that's still 4000 core
Dialogue: 0,0:12:51.12,0:12:55.09,Default,,0000,0000,0000,,years. So this is a long time. Okay. But\Nas you can see, it's possible to solve
Dialogue: 0,0:12:55.09,0:13:00.41,Default,,0000,0000,0000,,this. I mean, just put enough, if I have a\Nbig enough hammer, I can solve this. Okay.
Dialogue: 0,0:13:00.41,0:13:05.40,Default,,0000,0000,0000,,But again, you can make N pretty big,\Nbigger than anything being able to solve
Dialogue: 0,0:13:05.40,0:13:10.63,Default,,0000,0000,0000,,this anymore. But. Okay, so there is a\Nquantum algorithm for this and this is
Dialogue: 0,0:13:10.63,0:13:16.28,Default,,0000,0000,0000,,this other paper from 95. Peter Shor. So\Nhe thought of this algorithm that solves
Dialogue: 0,0:13:16.28,0:13:21.93,Default,,0000,0000,0000,,the DLP in polynomial time. Okay, now\Nremember our big N we took about two to
Dialogue: 0,0:13:21.93,0:13:26.77,Default,,0000,0000,0000,,the small n. And this Shor's algorithm\Nonly takes small n to the cube? And I
Dialogue: 0,0:13:26.77,0:13:32.73,Default,,0000,0000,0000,,mean, if N is a hundred hundred cube, it's\Nnot that big. And I can make a thousand by
Dialogue: 0,0:13:32.73,0:13:37.75,Default,,0000,0000,0000,,a thousand cube is still not that big.\NOkay. So there is a good algorithm that
Dialogue: 0,0:13:37.75,0:13:41.52,Default,,0000,0000,0000,,assumes the existence of a quantum\Ncomputer. I mean as outlandish that might
Dialogue: 0,0:13:41.52,0:13:47.60,Default,,0000,0000,0000,,sound, but still this algorithm in theory\Nbreaks the DLP. Okay. So I don't know,
Dialogue: 0,0:13:47.60,0:13:52.32,Default,,0000,0000,0000,,maybe in 20 years or 30 years, 100 years.\NI don't know personally, but if there is a
Dialogue: 0,0:13:52.32,0:13:56.91,Default,,0000,0000,0000,,quantum computer eventually that somehow\Nruns this thing, okay, DLP's broken,
Dialogue: 0,0:13:56.91,0:14:05.35,Default,,0000,0000,0000,,classically. So. Well, what to do? As I\Nsaid, let's just try to come up with
Dialogue: 0,0:14:05.35,0:14:10.90,Default,,0000,0000,0000,,cryptography for which we don't know a\Nquantum algorithm. Okay. Or for which we
Dialogue: 0,0:14:10.90,0:14:15.17,Default,,0000,0000,0000,,expect there won't be a quantum algorithm\Never. There are a few candidates. Again,
Dialogue: 0,0:14:15.17,0:14:21.93,Default,,0000,0000,0000,,there's this zoo. Lattices, codes, this\Nlong word, and isogenies. Okay. Now what I
Dialogue: 0,0:14:21.93,0:14:26.32,Default,,0000,0000,0000,,want to tell you about is what is an\Nisogeny, and how do I do key exchange with
Dialogue: 0,0:14:26.32,0:14:33.97,Default,,0000,0000,0000,,an isogeny? Okay. Because I know, it's a\Nfancy word, but what does it mean? Okay.
Dialogue: 0,0:14:33.97,0:14:37.30,Default,,0000,0000,0000,,There was this other word that started\Nwith elliptic curve isogenies, so probably
Dialogue: 0,0:14:37.30,0:14:40.86,Default,,0000,0000,0000,,I should tell you about what is an\Nelliptic curve or give you a reminder if
Dialogue: 0,0:14:40.86,0:14:46.38,Default,,0000,0000,0000,,you've seen this before. So I look at this\Nequation in two variables and two
Dialogue: 0,0:14:46.38,0:14:51.53,Default,,0000,0000,0000,,constants, the variables X and Y, my\Nconstants are A and B. And the equation is
Dialogue: 0,0:14:51.53,0:14:58.16,Default,,0000,0000,0000,,Y squared is X cubed plus AX plus B. And\Nnow what I want to look at is all the
Dialogue: 0,0:14:58.16,0:15:02.92,Default,,0000,0000,0000,,solutions to this equation, all the\Npossible pairs Y and X or X and Y. And of
Dialogue: 0,0:15:02.92,0:15:06.99,Default,,0000,0000,0000,,course, they're going to look different\Nsomehow for the different possible numbers
Dialogue: 0,0:15:06.99,0:15:11.37,Default,,0000,0000,0000,,that I can plug in for X and Y. And again,\Nyou might have guessed it, first of all,
Dialogue: 0,0:15:11.37,0:15:14.76,Default,,0000,0000,0000,,we're going to look at it over the decimal\Nnumbers and then later we want to consider
Dialogue: 0,0:15:14.76,0:15:20.73,Default,,0000,0000,0000,,this again over our finite field, okay,\Nbecause we like we like this discreteness.
Dialogue: 0,0:15:20.73,0:15:25.65,Default,,0000,0000,0000,,And over R, a simple equation, I just\Nchose some values for A and B, B I set to
Dialogue: 0,0:15:25.65,0:15:30.79,Default,,0000,0000,0000,,zero, A I set to 1, uh, A I set to zero, B\NI set to one. The solution set looks like
Dialogue: 0,0:15:30.79,0:15:36.52,Default,,0000,0000,0000,,this. And actually it extends infinitely\Nfar on the right side, up and down. Okay.
Dialogue: 0,0:15:36.52,0:15:41.47,Default,,0000,0000,0000,,So this is just somehow a snapshot of what\Nthe solution set looks like. But over my
Dialogue: 0,0:15:41.47,0:15:45.54,Default,,0000,0000,0000,,finite field, and I chose one with one\Nhundred and one elements, it looks like
Dialogue: 0,0:15:45.54,0:15:50.85,Default,,0000,0000,0000,,the set of points. Okay. So elliptical\Ncurves look differently over different
Dialogue: 0,0:15:50.85,0:15:57.51,Default,,0000,0000,0000,,fields. But that's fine. That's fine.\NOkay. Now, quick reminder of why people
Dialogue: 0,0:15:57.51,0:16:01.55,Default,,0000,0000,0000,,like elliptic curves. So there is\Nsomething called the point addition law.
Dialogue: 0,0:16:01.55,0:16:05.49,Default,,0000,0000,0000,,So I can take two points on this curve and\NI can somehow add them. Okay, but this is
Dialogue: 0,0:16:05.49,0:16:10.35,Default,,0000,0000,0000,,not really addition in the sense of\Nnumbers. There is somehow a law that I have
Dialogue: 0,0:16:10.35,0:16:16.50,Default,,0000,0000,0000,,to apply. And let me quickly show off how\Nthis is done. So how do I add two points
Dialogue: 0,0:16:16.50,0:16:21.22,Default,,0000,0000,0000,,on this curve? Well, you take these two\Npoints, you put a line through it, and
Dialogue: 0,0:16:21.22,0:16:27.43,Default,,0000,0000,0000,,then there is a law that says that if I\Nput a line through two points, then it
Dialogue: 0,0:16:27.43,0:16:32.06,Default,,0000,0000,0000,,has, the line has to cut the curve from\Nthe third point. Okay. So I put the line
Dialogue: 0,0:16:32.06,0:16:36.78,Default,,0000,0000,0000,,through these two points. It cut the curve\Nin the third point all the way up on the
Dialogue: 0,0:16:36.78,0:16:41.07,Default,,0000,0000,0000,,right. You know, what I'm going to do is\NI'm going to reflect the point down on the
Dialogue: 0,0:16:41.07,0:16:46.38,Default,,0000,0000,0000,,X axis. Okay. So I draw this other line, I\Nreflect it down. And then what I define is
Dialogue: 0,0:16:46.38,0:16:56.11,Default,,0000,0000,0000,,that other, that I cut, this I define to\Nbe the sum of these two points. Okay. So.
Dialogue: 0,0:16:56.11,0:17:00.65,Default,,0000,0000,0000,,And that works. Okay. I can add points, I\Ncan subtract points. There will be the
Dialogue: 0,0:17:00.65,0:17:05.37,Default,,0000,0000,0000,,inverse. So this kind of like X like\Nintegers mod N when you only consider
Dialogue: 0,0:17:05.37,0:17:09.56,Default,,0000,0000,0000,,addition, kind of, kind of, it's not\Nreally the same, but you can also single
Dialogue: 0,0:17:09.56,0:17:16.77,Default,,0000,0000,0000,,out the special point O like beautiful O\Nwe call the origin, whatever that is. And
Dialogue: 0,0:17:16.77,0:17:20.86,Default,,0000,0000,0000,,this origin kind of acts like a zero. So\Nif I add the origin to the point where I
Dialogue: 0,0:17:20.86,0:17:25.12,Default,,0000,0000,0000,,get the point again, or if I add the point\Nand its inverse I get that point, I get
Dialogue: 0,0:17:25.12,0:17:30.63,Default,,0000,0000,0000,,zero. Okay. So there's something like a\Nzero. And you can also multiply points,
Dialogue: 0,0:17:30.63,0:17:34.81,Default,,0000,0000,0000,,right. I mean what is multiplication, it's\Njust repeated addition. So in brackets n,
Dialogue: 0,0:17:34.81,0:17:38.92,Default,,0000,0000,0000,,this is what I write for point\Nmultiplication, just add the point n times
Dialogue: 0,0:17:38.92,0:17:43.44,Default,,0000,0000,0000,,to itself. Okay. So there's nothing fancy\Ngoing on here. So you can somehow add
Dialogue: 0,0:17:43.44,0:17:49.51,Default,,0000,0000,0000,,points. You can multiply points. That's\Npretty cool. And if you look closer, you
Dialogue: 0,0:17:49.51,0:17:55.78,Default,,0000,0000,0000,,can look at the special set here that I\Ndenoted E brackets, big N. And these are
Dialogue: 0,0:17:55.78,0:18:00.60,Default,,0000,0000,0000,,all the points on the curve such that if I\Nmultiplied this point for N it gives me
Dialogue: 0,0:18:00.60,0:18:08.13,Default,,0000,0000,0000,,zero. Okay. And this set for the\Nmathematically inclined people among us I
Dialogue: 0,0:18:08.13,0:18:12.50,Default,,0000,0000,0000,,know say this is somehow the N-torsion of\Nan elliptic curve, whatever that means.
Dialogue: 0,0:18:12.50,0:18:16.37,Default,,0000,0000,0000,,But if you're interested, you can look it\Nup. And this set kind of acts like
Dialogue: 0,0:18:16.37,0:18:23.52,Default,,0000,0000,0000,,additive integers mod n - like two copies\Nof it. Okay. And now this is where the
Dialogue: 0,0:18:23.52,0:18:26.98,Default,,0000,0000,0000,,term super singular comes from. One of the\Ndefinitions. This is not the only
Dialogue: 0,0:18:26.98,0:18:30.53,Default,,0000,0000,0000,,definition, but this is one of them. If\Nyou look at the elliptic curve, not over
Dialogue: 0,0:18:30.53,0:18:36.03,Default,,0000,0000,0000,,the reals, okay, or whichever numbers, but\Nover this finite fields. And if you look
Dialogue: 0,0:18:36.03,0:18:41.98,Default,,0000,0000,0000,,at the torsion, the P-torsion, then this\Nbehaves differently for different types of
Dialogue: 0,0:18:41.98,0:18:45.28,Default,,0000,0000,0000,,curves. Okay. The P-torsion is either\Nempty, then we call the curve super
Dialogue: 0,0:18:45.28,0:18:50.40,Default,,0000,0000,0000,,singular; or it's just one copy of of\Nintegers mod P and then we call it
Dialogue: 0,0:18:50.40,0:18:55.15,Default,,0000,0000,0000,,ordinary. Okay. It's not really important\Nto know what that means. It just means
Dialogue: 0,0:18:55.15,0:18:59.98,Default,,0000,0000,0000,,that there is a distinction for curves\Nsomehow that's somehow ingrained
Dialogue: 0,0:18:59.98,0:19:07.73,Default,,0000,0000,0000,,mathematically deep down there. And\Nbecause this E N torsion is somehow two
Dialogue: 0,0:19:07.73,0:19:13.81,Default,,0000,0000,0000,,copies of of integers mod N, additive\Nintegers mod N, I can generate it by
Dialogue: 0,0:19:13.81,0:19:17.54,Default,,0000,0000,0000,,taking linear combinations of two points,\Nsay P and Q, and these are like the
Dialogue: 0,0:19:17.54,0:19:21.68,Default,,0000,0000,0000,,generators we saw earlier. Right. But\Nthese are not additive generators instead
Dialogue: 0,0:19:21.68,0:19:26.83,Default,,0000,0000,0000,,of somehow exponential generators. But it,\Neverything behaves kind of similar. And
Dialogue: 0,0:19:26.83,0:19:30.24,Default,,0000,0000,0000,,now you can really use this to do\Ncryptography already. If you wanted to
Dialogue: 0,0:19:30.24,0:19:35.90,Default,,0000,0000,0000,,write it. You can. You can somehow look at\Nthe DLP in that group, but there is the
Dialogue: 0,0:19:35.90,0:19:40.51,Default,,0000,0000,0000,,problem again that the DLP in there,\Nthere's Shor's algorithm again. Right. So
Dialogue: 0,0:19:40.51,0:19:46.97,Default,,0000,0000,0000,,even if you do cryptography in this group,\Nyou run into the same problem. OK, so we
Dialogue: 0,0:19:46.97,0:19:51.48,Default,,0000,0000,0000,,have to do a bit better. We have to search\Nfurther. And this is where isogenies come
Dialogue: 0,0:19:51.48,0:20:03.86,Default,,0000,0000,0000,,on. Come into the play. So one way you can\Nthink of an isogeny is, remember how we
Dialogue: 0,0:20:03.86,0:20:10.71,Default,,0000,0000,0000,,found integers mod N by somehow dividing\NZ by all the N multiples. And you can do
Dialogue: 0,0:20:10.71,0:20:16.92,Default,,0000,0000,0000,,something similar with an elliptic curve.\Nif you can somehow take part of this
Dialogue: 0,0:20:16.92,0:20:24.03,Default,,0000,0000,0000,,N-torsion and you can divide an elliptic\Ncurve by this. You can mod it out and it
Dialogue: 0,0:20:24.03,0:20:28.61,Default,,0000,0000,0000,,turns out this is mathematically well-\Ndefined and it gives you another elliptic
Dialogue: 0,0:20:28.61,0:20:37.56,Default,,0000,0000,0000,,curve. Okay. So I take a curve, E1, I take\Na part of my N-torsion. I divide elliptic
Dialogue: 0,0:20:37.56,0:20:42.84,Default,,0000,0000,0000,,curve E1 by G and I get another elliptic\Ncurve E2. And there's something else that
Dialogue: 0,0:20:42.84,0:20:46.50,Default,,0000,0000,0000,,comes along with this construction. And\Nthis is what we call the isogeny. This is
Dialogue: 0,0:20:46.50,0:20:53.38,Default,,0000,0000,0000,,a map. OK. Along with this construction\Ncomes a map from E1 to E2. And this map is
Dialogue: 0,0:20:53.38,0:21:00.77,Default,,0000,0000,0000,,what we call an isogeny. An isogeny is the\Nmap that takes us from one curve to
Dialogue: 0,0:21:00.77,0:21:07.14,Default,,0000,0000,0000,,another curve. And this map is kind of\Nspecial because it behaves in a nice way
Dialogue: 0,0:21:07.14,0:21:12.20,Default,,0000,0000,0000,,and it plays nicely with the structure\Nthat's already ingrained in our curve.
Dialogue: 0,0:21:12.20,0:21:17.84,Default,,0000,0000,0000,,Namely, I can either add two points on my\Nstarting curve and send it through that
Dialogue: 0,0:21:17.84,0:21:25.24,Default,,0000,0000,0000,,map to the other curve. Or it can take two\Npoints on my starting curve. I can send it
Dialogue: 0,0:21:25.24,0:21:31.60,Default,,0000,0000,0000,,through the map and edit over there and it\Ngives me the same thing. So this map
Dialogue: 0,0:21:31.60,0:21:35.54,Default,,0000,0000,0000,,behaves nicely with point addition. That's\Npretty nice, just as a side note. So this
Dialogue: 0,0:21:35.54,0:21:42.14,Default,,0000,0000,0000,,map is special. So this is just the\Nremainder of what I said: Adding points on
Dialogue: 0,0:21:42.14,0:21:47.25,Default,,0000,0000,0000,,E1 and sending the result to E2 is the\Nsame as sending points to E2 and adding
Dialogue: 0,0:21:47.25,0:21:53.89,Default,,0000,0000,0000,,them there. So this map somehow plays nicely\Nwith my laws on my elliptic curve. Now I
Dialogue: 0,0:21:53.89,0:22:01.82,Default,,0000,0000,0000,,have to make a definition: In mathematics,\Nthe kernel of a map is the set of all the
Dialogue: 0,0:22:01.82,0:22:08.24,Default,,0000,0000,0000,,inputs to the map that are sent to zero.\NAnd we saw this origin O here that acted
Dialogue: 0,0:22:08.24,0:22:12.47,Default,,0000,0000,0000,,like zero. So the kernel of my isogeny,\NI'm just going to define as all the inputs
Dialogue: 0,0:22:12.47,0:22:18.24,Default,,0000,0000,0000,,to the isogeny that are sent to the zero\Non the other curve. And in written
Dialogue: 0,0:22:18.24,0:22:25.23,Default,,0000,0000,0000,,notation, it's the set of all P in E1 such\Nthat the map of P is 0. It turns out that
Dialogue: 0,0:22:25.23,0:22:34.51,Default,,0000,0000,0000,,this kernel for my isogeny, that I started\Nout with somehow recovers this part of the
Dialogue: 0,0:22:34.51,0:22:40.56,Default,,0000,0000,0000,,end portion that I used to construct. So\Nthere's two ways now to think of an
Dialogue: 0,0:22:40.56,0:22:47.89,Default,,0000,0000,0000,,isogeny. So this is what we start with. We\Nreconsidered E1 mod G and it gave us this
Dialogue: 0,0:22:47.89,0:22:54.27,Default,,0000,0000,0000,,map from E1 to E2. But if I start with\Nthis map from E1 to E2, we also find the G
Dialogue: 0,0:22:54.27,0:22:59.32,Default,,0000,0000,0000,,again. So there are two ways to represent\Nthis map. We can think of a subgroup -
Dialogue: 0,0:22:59.32,0:23:06.63,Default,,0000,0000,0000,,this G - or we can think of the map. And\Nultimately somehow there is a correspondence
Dialogue: 0,0:23:06.63,0:23:12.00,Default,,0000,0000,0000,,between the various subgroups for\Ndifferent N and isogenies that are somehow
Dialogue: 0,0:23:12.00,0:23:15.90,Default,,0000,0000,0000,,emanating from a curve. We can think of\Nthis link or the hairs on my head, they
Dialogue: 0,0:23:15.90,0:23:20.76,Default,,0000,0000,0000,,are going out and then they're going to\Nreach other electric curves maybe. And
Dialogue: 0,0:23:20.76,0:23:27.02,Default,,0000,0000,0000,,these notions can be used interchangeably.\NSo somehow there is a correspondence. And
Dialogue: 0,0:23:27.02,0:23:32.66,Default,,0000,0000,0000,,again, I can choose different ends. So some-\Nhow from one curve, I can have many outgoing
Dialogue: 0,0:23:32.66,0:23:40.21,Default,,0000,0000,0000,,isogenies that are different in a sense. And\Nnow the thing is in practice, we actually want to
Dialogue: 0,0:23:40.21,0:23:43.90,Default,,0000,0000,0000,,compute these maps. So right now, this is\Njust general abstract nonsense. I didn't
Dialogue: 0,0:23:43.90,0:23:47.47,Default,,0000,0000,0000,,tell you anything of how to compute these\Nthings. I just told you there are some
Dialogue: 0,0:23:47.47,0:23:50.60,Default,,0000,0000,0000,,more correspondences. But I mean, what\Ndoes that even mean? Right. It's useless
Dialogue: 0,0:23:50.60,0:23:57.25,Default,,0000,0000,0000,,if I can't use it in practice. And then\Nthere is another thing: You can compute
Dialogue: 0,0:23:57.25,0:24:00.41,Default,,0000,0000,0000,,these things, there are formulas, people\Nhave worked on this. But somehow the cost
Dialogue: 0,0:24:00.41,0:24:08.00,Default,,0000,0000,0000,,grows if I enlarge N. So really, in\Npractice, for applications, I want to choose
Dialogue: 0,0:24:08.00,0:24:13.67,Default,,0000,0000,0000,,a small N. Maybe two or three - that would\Nbe pretty good. And now the thing is, it's
Dialogue: 0,0:24:13.67,0:24:19.25,Default,,0000,0000,0000,,the supersingular curves for which I can some-\Nhow control or choose the possible ends very
Dialogue: 0,0:24:19.25,0:24:27.09,Default,,0000,0000,0000,,very easily. So this is the reason why we\Nreconsider supersingular curves. Now I can
Dialogue: 0,0:24:27.09,0:24:33.70,Default,,0000,0000,0000,,choose my prime to be of this form and\Nthen magically this is going to force 2
Dialogue: 0,0:24:33.70,0:24:39.56,Default,,0000,0000,0000,,and 3 being possible. So this is the\Nreason why we choose supersingular ones.
Dialogue: 0,0:24:39.56,0:24:45.08,Default,,0000,0000,0000,,There's some theory which is not\Ninteresting for you, but it's important
Dialogue: 0,0:24:45.08,0:24:52.35,Default,,0000,0000,0000,,for implementation. And there's a way basically\Nfor us to force the curve to have those
Dialogue: 0,0:24:52.35,0:24:57.49,Default,,0000,0000,0000,,isogenies that we like. But there is\Nanother important reason and this is the
Dialogue: 0,0:24:57.49,0:25:01.45,Default,,0000,0000,0000,,reason that actually makes it\Ninteresting for cryptography. So what I
Dialogue: 0,0:25:01.45,0:25:07.92,Default,,0000,0000,0000,,can do is: I start with an arbitrary\Ncurve, and this just might not be a
Dialogue: 0,0:25:07.92,0:25:12.73,Default,,0000,0000,0000,,supersingular one, just any curve and say I\Nconsider all the outgoing two isogenies if
Dialogue: 0,0:25:12.73,0:25:19.30,Default,,0000,0000,0000,,these are possible, 4 and 2. So there's\Ngoing to be 1, 2 and 3. And then again,
Dialogue: 0,0:25:19.30,0:25:24.93,Default,,0000,0000,0000,,from E1, I can again consider all the\Noutgoing isogenies, and so on and so
Dialogue: 0,0:25:24.93,0:25:28.97,Default,,0000,0000,0000,,forth. So what's going to happen here is:\NThis is going to generate a graph, where
Dialogue: 0,0:25:28.97,0:25:36.86,Default,,0000,0000,0000,,the vertices of my graph are elliptic curves\Nand the edges are isogenies. So somehow
Dialogue: 0,0:25:36.86,0:25:44.26,Default,,0000,0000,0000,,behind the scenes there is this graph\Nhidden. Now, it turns out that if you do
Dialogue: 0,0:25:44.26,0:25:48.58,Default,,0000,0000,0000,,this for a supersingular elliptic curve -\Nand I generated this yesterday for you,
Dialogue: 0,0:25:48.58,0:25:52.97,Default,,0000,0000,0000,,so this is one possible graph - I can\Nremember which prime I took. But here you
Dialogue: 0,0:25:52.97,0:25:57.35,Default,,0000,0000,0000,,can see all the ellipses are ellipitic\Ncurves and all the edges between them are
Dialogue: 0,0:25:57.35,0:26:03.33,Default,,0000,0000,0000,,2 isogenies. So this is an example of a\Nsupersingular 2-isogeny graph - okay, this
Dialogue: 0,0:26:03.33,0:26:11.17,Default,,0000,0000,0000,,looks pretty wild. I can do the same for N\N= 3 if it's possible, or is 5 and so on
Dialogue: 0,0:26:11.17,0:26:17.02,Default,,0000,0000,0000,,and so forth. There are many many graphs\Nhidden. But why is the supersingular graph
Dialogue: 0,0:26:17.02,0:26:20.90,Default,,0000,0000,0000,,specific and important? Well, it turns out\Nthat somehow the supersingular one is
Dialogue: 0,0:26:20.90,0:26:27.44,Default,,0000,0000,0000,,connected, and it's what we call a\NRamanujan graph. I'm going to explain
Dialogue: 0,0:26:27.44,0:26:33.74,Default,,0000,0000,0000,,this in a second. And as a bonus, for\Nimplementation purposes, it turns out that
Dialogue: 0,0:26:33.74,0:26:39.56,Default,,0000,0000,0000,,you can do all your implementation in\Narithmetics in the finite field with p^2
Dialogue: 0,0:26:39.56,0:26:45.41,Default,,0000,0000,0000,,elements. This is nice. So I'm just gonna\Nsay that if you don't consider
Dialogue: 0,0:26:45.41,0:26:49.20,Default,,0000,0000,0000,,supersingular curves and you go along\Nthese graphs, then what's going to happen
Dialogue: 0,0:26:49.20,0:26:54.33,Default,,0000,0000,0000,,is that somehow this "field of\Ndefinition", what we call it, could grow
Dialogue: 0,0:26:54.33,0:26:59.32,Default,,0000,0000,0000,,for you to be able to go further, but that\Nwould suck for implementation. But
Dialogue: 0,0:26:59.32,0:27:04.28,Default,,0000,0000,0000,,supersingular ones is nice so, F_p^2 is\Nenough. So this is again, is good for
Dialogue: 0,0:27:04.28,0:27:10.30,Default,,0000,0000,0000,,implementation. So somehow magically many\Nmany things happen here that are benefiting us.
Dialogue: 0,0:27:10.30,0:27:15.46,Default,,0000,0000,0000,,And again, why is it nice that this is a\NRamanujan graph? A Ramanujan graph has
Dialogue: 0,0:27:15.46,0:27:21.09,Default,,0000,0000,0000,,certain optimal expansion properties. This\Nmeans that if I start from a random point
Dialogue: 0,0:27:21.09,0:27:28.54,Default,,0000,0000,0000,,in my fraph, and I take a random walk with some-\Nhow logarithmic steps of the total amount of
Dialogue: 0,0:27:28.54,0:27:38.13,Default,,0000,0000,0000,,vertices, then this will put me in a very\Nuniform place in that graph. And this is
Dialogue: 0,0:27:38.13,0:27:43.58,Default,,0000,0000,0000,,is good for cryptography. Because you only\Nneed to take log many steps to somehow
Dialogue: 0,0:27:43.58,0:27:50.12,Default,,0000,0000,0000,,randomize yourself in that graph. And this\Nis what this could look like. I started at
Dialogue: 0,0:27:50.12,0:27:55.67,Default,,0000,0000,0000,,that red ellipses over there. This was my\Nstarting point. And then I generated a few
Dialogue: 0,0:27:55.67,0:28:01.92,Default,,0000,0000,0000,,random walks, and the blue points are\Nwhere I got placed. This might not prove
Dialogue: 0,0:28:01.92,0:28:09.10,Default,,0000,0000,0000,,anything, but it gives you an idea of how, some-\Nhow uniformly, it places me around that graph.
Dialogue: 0,0:28:09.10,0:28:17.08,Default,,0000,0000,0000,,So, it's good for cryptography, but there\Nare other reasons, so supersingular elliptic
Dialogue: 0,0:28:17.08,0:28:22.40,Default,,0000,0000,0000,,curves somehow I can actually compute how\Nmany of these curves I will have in my
Dialogue: 0,0:28:22.40,0:28:26.54,Default,,0000,0000,0000,,graph. This is another reason to be\Nlooking at these things. Because if I
Dialogue: 0,0:28:26.54,0:28:30.74,Default,,0000,0000,0000,,don't even know how many curves are in my\Ngraph - well I can't really say anything
Dialogue: 0,0:28:30.74,0:28:35.18,Default,,0000,0000,0000,,about the security - but at least for\Nsupersingular ones, I can see they're
Dialogue: 0,0:28:35.18,0:28:42.17,Default,,0000,0000,0000,,roughly p/ 12 many. Okay, and then again,\Nif I'd choose my p about n bits, well then
Dialogue: 0,0:28:42.17,0:28:47.66,Default,,0000,0000,0000,,I really know that my graph has about 2^n\Nelements. And at least there I can see
Dialogue: 0,0:28:47.66,0:28:51.83,Default,,0000,0000,0000,,something about the cryptographic\Nstrength, right? I can make M big and then
Dialogue: 0,0:28:51.83,0:28:54.62,Default,,0000,0000,0000,,you can say: Oh yeah, you have this random\Ngraph, you take some n-length walks and
Dialogue: 0,0:28:54.62,0:28:58.67,Default,,0000,0000,0000,,n-length walks and then it places you\Nrandomly in there and the whole graph is
Dialogue: 0,0:28:58.67,0:29:04.32,Default,,0000,0000,0000,,about 2^n elements. And then I can say\Nsomething about the expected runtime of
Dialogue: 0,0:29:04.32,0:29:09.78,Default,,0000,0000,0000,,algorithms. So this is another reason why\Nwe want to consider supersingular curves:
Dialogue: 0,0:29:09.78,0:29:16.14,Default,,0000,0000,0000,,Because I can tell you how many elements\Nare in this graph. So a quick summary of
Dialogue: 0,0:29:16.14,0:29:21.49,Default,,0000,0000,0000,,what we saw, why this is nice. So what you\Nget is a compact representation of an
Dialogue: 0,0:29:21.49,0:29:27.55,Default,,0000,0000,0000,,(l+1)-regular graph. And we saw examples,\Ne.g. l = 2, l = 3. Bigger values are
Dialogue: 0,0:29:27.55,0:29:30.70,Default,,0000,0000,0000,,possible, but we don't even care about\Nthose because this is what gives us the
Dialogue: 0,0:29:30.70,0:29:38.51,Default,,0000,0000,0000,,fastest arithmetic such that we can work\Nwith F_p^2. This is nice, this keeps our
Dialogue: 0,0:29:38.51,0:29:43.76,Default,,0000,0000,0000,,implementation fast. I can tell you how\Nmany vertices are in the graph: about
Dialogue: 0,0:29:43.76,0:29:48.84,Default,,0000,0000,0000,,p/12. And again, such that the graph for\Nmixing properties that are useful for
Dialogue: 0,0:29:48.84,0:29:52.37,Default,,0000,0000,0000,,cryptographic applications. So because I\Nwant to use this ultimately for
Dialogue: 0,0:29:52.37,0:29:59.85,Default,,0000,0000,0000,,cryptography. And again, that's what we\Nsaid: If I choose an n-bit prime p, then
Dialogue: 0,0:29:59.85,0:30:07.16,Default,,0000,0000,0000,,the graph has about 2^n vertices - so\Nexponentially many vertices. And it turns
Dialogue: 0,0:30:07.16,0:30:16.24,Default,,0000,0000,0000,,out that there are some hard problems that\NI can ask you to solve in this graph that
Dialogue: 0,0:30:16.24,0:30:23.13,Default,,0000,0000,0000,,don't have good quantum algorithms. So one\Nhard problem is this: I take two super
Dialogue: 0,0:30:23.13,0:30:28.63,Default,,0000,0000,0000,,singular elliptic curves, so I just give you\Ntwo random curves in this graph and ask
Dialogue: 0,0:30:28.63,0:30:33.12,Default,,0000,0000,0000,,you to find a nice arch in the path\Nbetween those isognies, or three
Dialogue: 0,0:30:33.12,0:30:37.88,Default,,0000,0000,0000,,isogenies. And it turns out that this just\Ndoesn't have a good quantum algorithm. So
Dialogue: 0,0:30:37.88,0:30:42.75,Default,,0000,0000,0000,,classically, I mean the numbers are super\Nimportant here, but classically the
Dialogue: 0,0:30:42.75,0:30:47.70,Default,,0000,0000,0000,,complexity is p, over the fourth root of p,\Nand the best quantum algorithm is a bit
Dialogue: 0,0:30:47.70,0:30:52.68,Default,,0000,0000,0000,,better at it. I mean again, it's not super\Nimportant what's there. What's important
Dialogue: 0,0:30:52.68,0:30:58.00,Default,,0000,0000,0000,,is that there is no polynomial time\Nalgorithm compare to ideal p that we
Dialogue: 0,0:30:58.00,0:31:03.06,Default,,0000,0000,0000,,started with. So if I make this p very large\Nand your quantum computer, your
Dialogue: 0,0:31:03.06,0:31:07.91,Default,,0000,0000,0000,,hypothetical quantum computer, will\Nprobably not solve this. Okay, so that's
Dialogue: 0,0:31:07.91,0:31:14.96,Default,,0000,0000,0000,,cool. So how do we do key exchange? I\Nstart with a supersingular elliptic curve E,
Dialogue: 0,0:31:14.96,0:31:21.35,Default,,0000,0000,0000,,where I chose my prime p such that two and\Nthree isogenies are possible. And then
Dialogue: 0,0:31:21.35,0:31:26.02,Default,,0000,0000,0000,,Alice - earlier I remember she chose a\Nrandom number a - but now Alice will
Dialogue: 0,0:31:26.02,0:31:35.54,Default,,0000,0000,0000,,choose a random subgroup A, and she will\Nsend E mod A to Bob. This amounts to Alice
Dialogue: 0,0:31:35.54,0:31:40.94,Default,,0000,0000,0000,,for computing the nice isogeny. And again,\Nthis is a very symmetrical key exchange,
Dialogue: 0,0:31:40.94,0:31:45.46,Default,,0000,0000,0000,,except that now Bob won't use the same\Ngenerator but Bob will use the 3
Dialogue: 0,0:31:45.46,0:31:50.83,Default,,0000,0000,0000,,isogenies. So Bob will choose a random\Nsubgroup B, and then he will compute E mod
Dialogue: 0,0:31:50.83,0:31:58.19,Default,,0000,0000,0000,,B and send this to Alice. And this is the\Npicture: There's Alice, there's Bob. Alice
Dialogue: 0,0:31:58.19,0:32:04.52,Default,,0000,0000,0000,,chose A, Bob chooses B. Alice sends E mod\NA to Bob, Bob sends E mod B to Alice. And
Dialogue: 0,0:32:04.52,0:32:12.13,Default,,0000,0000,0000,,then how do they agree on a shared key?\NThey will just mod out by their respective
Dialogue: 0,0:32:12.13,0:32:16.42,Default,,0000,0000,0000,,subgroups again. And it turns out that the\Nelliptic curve that they find is going to
Dialogue: 0,0:32:16.42,0:32:23.09,Default,,0000,0000,0000,,be the same for both of them. Okay, so how\Ndoes that work? Again, let's return to our
Dialogue: 0,0:32:23.09,0:32:32.61,Default,,0000,0000,0000,,graph: Say Alice and Bob agree on a black\Ncurve - the black curve on the left side.
Dialogue: 0,0:32:32.61,0:32:36.93,Default,,0000,0000,0000,,And then Alice will compute these red\Nsteps, which correspond to taking a
Dialogue: 0,0:32:36.93,0:32:42.03,Default,,0000,0000,0000,,subgroup. So Alice will compute these red\Nsteps for her secret subgroup and she will
Dialogue: 0,0:32:42.03,0:32:48.67,Default,,0000,0000,0000,,end up at the red curve in the upper right\Ncorner. And Bob will do the same. But now
Dialogue: 0,0:32:48.67,0:32:53.37,Default,,0000,0000,0000,,Bob is not in the 2-graph, but in the\N3-graph - so this is the three graph. And
Dialogue: 0,0:32:53.37,0:32:57.60,Default,,0000,0000,0000,,the black curve that he started from in\Nthe 3-graph is down there. He will also
Dialogue: 0,0:32:57.60,0:33:02.04,Default,,0000,0000,0000,,select a random subgroup, compute the\Nsecret path and Bob will end up in the
Dialogue: 0,0:33:02.04,0:33:06.55,Default,,0000,0000,0000,,blue curve. Now Alice will send her red\Ncurve to Bob. And Bob, will send his blue
Dialogue: 0,0:33:06.55,0:33:12.04,Default,,0000,0000,0000,,curve to Alice. And then Alice will\Nconsider the blue curve in the 2-graph. So
Dialogue: 0,0:33:12.04,0:33:17.32,Default,,0000,0000,0000,,Alice starts from the blue curve that she\Ngot from Bob - and this is the position in
Dialogue: 0,0:33:17.32,0:33:23.26,Default,,0000,0000,0000,,the 2-graph. And again, she computes that\Nsame secret path and ends up in the green
Dialogue: 0,0:33:23.26,0:33:30.39,Default,,0000,0000,0000,,curve, which is up there. Bob got the red\Ncurve from Alice. So Bob has the red curve
Dialogue: 0,0:33:30.39,0:33:34.34,Default,,0000,0000,0000,,there. Again, he computes the path and\Nthen ends up at the green curve. And it
Dialogue: 0,0:33:34.34,0:33:38.44,Default,,0000,0000,0000,,turns out that the green curves here and\Nthere are the same. And this is going to
Dialogue: 0,0:33:38.44,0:33:45.96,Default,,0000,0000,0000,,be the shared key for them. This is SIDH.\NOkay. This is how you exchange a secret
Dialogue: 0,0:33:45.96,0:33:54.10,Default,,0000,0000,0000,,key using the supersingular isogeny graph.\NThat's the whole magic. And again, let's
Dialogue: 0,0:33:54.10,0:34:01.37,Default,,0000,0000,0000,,compare these two things a bit: the DLP-\Nbased one and the SIDH one. So we had the
Dialogue: 0,0:34:01.37,0:34:07.73,Default,,0000,0000,0000,,square, Alice and Bob started in the upper\Nleft corner and again ended up in the lower
Dialogue: 0,0:34:07.73,0:34:14.76,Default,,0000,0000,0000,,right corner. And SIDH looks very similar:\NAlice and Bob start with this common curve
Dialogue: 0,0:34:14.76,0:34:22.72,Default,,0000,0000,0000,,E in the upper left corner. Again, Alice\Ncomputes only horizontal arrows because
Dialogue: 0,0:34:22.72,0:34:27.75,Default,,0000,0000,0000,,she knows her secret group A, and Bob only\Ncomputes the vertical arrows because only
Dialogue: 0,0:34:27.75,0:34:34.49,Default,,0000,0000,0000,,he knows his secret group B. And again,\Nthey both end up in the lower right
Dialogue: 0,0:34:34.49,0:34:40.11,Default,,0000,0000,0000,,corner, where they define the shared key.\NBut now in this case, the shared key is
Dialogue: 0,0:34:40.11,0:34:44.86,Default,,0000,0000,0000,,not an element to the a^(ab), but elliptic\Ncurve. But again, there's a mathematical
Dialogue: 0,0:34:44.86,0:34:51.88,Default,,0000,0000,0000,,way to attach a unique number to it. So\Nit's a solved problem to actually make
Dialogue: 0,0:34:51.88,0:34:59.66,Default,,0000,0000,0000,,some bytes out of this. And yeah, that's\NSIDH. That's everything. This is a nice
Dialogue: 0,0:34:59.66,0:35:06.52,Default,,0000,0000,0000,,example of a post-quantum cryptography\Nscheme that we have today. And now
Dialogue: 0,0:35:06.52,0:35:13.29,Default,,0000,0000,0000,,let me finish with a quick conclusion. I\Nshowed you this "zoo": There are several
Dialogue: 0,0:35:13.29,0:35:18.84,Default,,0000,0000,0000,,candidates somehow for post-quantum\Ncryptography. And among them are some
Dialogue: 0,0:35:18.84,0:35:26.09,Default,,0000,0000,0000,,schemes based on supersingular elliptic\Ncurve isogenies, and we've seen that we
Dialogue: 0,0:35:26.09,0:35:30.46,Default,,0000,0000,0000,,know some hard problems involving these\Nisogenies that are hard for quantum
Dialogue: 0,0:35:30.46,0:35:40.51,Default,,0000,0000,0000,,computers, which makes this one possible\Nscheme for a quantum computer world. And
Dialogue: 0,0:35:40.51,0:35:44.95,Default,,0000,0000,0000,,probably I should say that we don't\Nenvision a world here where we users like
Dialogue: 0,0:35:44.95,0:35:49.96,Default,,0000,0000,0000,,me or you are in possession of quantum\Ncomputers. Probably, what we think about
Dialogue: 0,0:35:49.96,0:35:55.21,Default,,0000,0000,0000,,is that state actors are in positions of\Nquantum computers. So this is even more
Dialogue: 0,0:35:55.21,0:36:01.50,Default,,0000,0000,0000,,important for us to be looking into these\Nthings. And what we saw was to perform a
Dialogue: 0,0:36:01.50,0:36:05.29,Default,,0000,0000,0000,,Diffie-Hellman-like key exchange using\Nthese isogenies. But - this is what I
Dialogue: 0,0:36:05.29,0:36:10.41,Default,,0000,0000,0000,,didn't tell you about in his talk - there\Nare also schemes for signature-based
Dialogue: 0,0:36:10.41,0:36:15.95,Default,,0000,0000,0000,,isogenies, there is this scheme for key-\Nencapsulation-based isogenies. So
Dialogue: 0,0:36:15.95,0:36:22.68,Default,,0000,0000,0000,,there are other possible candidates for\Nother cryptographic building blocks based
Dialogue: 0,0:36:22.68,0:36:29.11,Default,,0000,0000,0000,,on isogenies and these hard problems. And\Nif you're super interested about this, you
Dialogue: 0,0:36:29.11,0:36:36.66,Default,,0000,0000,0000,,can either ask me or come to our assembly\Nand if you like reading scientific papers,
Dialogue: 0,0:36:36.66,0:36:39.90,Default,,0000,0000,0000,,papers about such isogenies and\Ncryptography in general, you can find this
Dialogue: 0,0:36:39.90,0:36:45.24,Default,,0000,0000,0000,,on the eprint archive. So this is a web\Npage where people post pre-prints about
Dialogue: 0,0:36:45.24,0:36:50.37,Default,,0000,0000,0000,,their papers and there's a huge collection\Nabout, among of them, isogeny papers. So
Dialogue: 0,0:36:50.37,0:36:58.38,Default,,0000,0000,0000,,if you're interested in this, this is the\Nplace to research. And with that, I would
Dialogue: 0,0:36:58.38,0:37:01.44,Default,,0000,0000,0000,,like to thank you all for your attention.
Dialogue: 0,0:37:01.44,0:37:14.87,Default,,0000,0000,0000,,{\i1}applause{\i0}
Dialogue: 0,0:37:14.87,0:37:22.60,Default,,0000,0000,0000,,Herald Angel: Is there any question? OK, I\Ngot the Signal Angel there, doing some
Dialogue: 0,0:37:22.60,0:37:27.64,Default,,0000,0000,0000,,Morse code?\NMicrophone 1: Yes. Can you recommend any
Dialogue: 0,0:37:27.64,0:37:33.28,Default,,0000,0000,0000,,literature for the theoretical background?\Nnaehrwert: The theoretical background?
Dialogue: 0,0:37:33.28,0:37:41.51,Default,,0000,0000,0000,,There are a few papers that are nice.\NOkay. The question again was literature
Dialogue: 0,0:37:41.51,0:37:46.05,Default,,0000,0000,0000,,about theoretical background. And yes,\Nthere are a few papers that are giving
Dialogue: 0,0:37:46.05,0:37:53.18,Default,,0000,0000,0000,,some nice, even theoretically involved\Nsummaries about the background. And your
Dialogue: 0,0:37:53.18,0:38:00.94,Default,,0000,0000,0000,,best bet is to go to eprint and you enter\N'isogenies' in the mask of search terms,
Dialogue: 0,0:38:00.94,0:38:07.40,Default,,0000,0000,0000,,or 'SIDH', and look at the papers that\Nsay, maybe, 'A Short Introduction to
Dialogue: 0,0:38:07.40,0:38:11.38,Default,,0000,0000,0000,,Isogenies' or something like that. I mean,\Nyou will find them if you search for them.
Dialogue: 0,0:38:11.38,0:38:17.50,Default,,0000,0000,0000,,I don't know them from the top of my head,\Nbut they're out there for sure. Yeah, and
Dialogue: 0,0:38:17.50,0:38:22.59,Default,,0000,0000,0000,,thanks for him - So there is a very recent\Npaper by Craig Costello, also somewhat
Dialogue: 0,0:38:22.59,0:38:26.67,Default,,0000,0000,0000,,titled 'A Short Introduction', something\Nlike that. So this is also maybe a good
Dialogue: 0,0:38:26.67,0:38:30.83,Default,,0000,0000,0000,,source for you to look at.\NHerald Angel: Um, yeah, 'Isogenies for
Dialogue: 0,0:38:30.83,0:38:32.73,Default,,0000,0000,0000,,Beginners'.\Nnaehrwert: 'Isogenies for Beginners'.
Dialogue: 0,0:38:32.73,0:38:35.79,Default,,0000,0000,0000,,Thank you.\N{\i1}audience laughing{\i0}
Dialogue: 0,0:38:35.79,0:38:44.50,Default,,0000,0000,0000,,Microphone 2: Hello. Yeah. So you've used\Nelleptic curve as an algebraic group,
Dialogue: 0,0:38:44.50,0:38:54.70,Default,,0000,0000,0000,,right, to compute these isogeny graphs.\NWhy do you use elliptic curves - what's
Dialogue: 0,0:38:54.70,0:39:02.77,Default,,0000,0000,0000,,the properties of elliptical curves as a\Ngroup? So, could you use any group to
Dialogue: 0,0:39:02.77,0:39:10.98,Default,,0000,0000,0000,,compute these graphs and could you use\Nthese as the basis for your scheme or your
Dialogue: 0,0:39:10.98,0:39:14.89,Default,,0000,0000,0000,,key exchange scheme?\Nnaehrwert: Okay, so the question was why
Dialogue: 0,0:39:14.89,0:39:21.28,Default,,0000,0000,0000,,use elliptical curves and the group\Nstructure that the impose to look at
Dialogue: 0,0:39:21.28,0:39:26.22,Default,,0000,0000,0000,,isogeny graphs involving elliptical curves\Nand whether I could use other groups. And
Dialogue: 0,0:39:26.22,0:39:34.00,Default,,0000,0000,0000,,actually, there's a two-fold answer maybe.\NSo if I go back - or actually let me go to
Dialogue: 0,0:39:34.00,0:39:40.65,Default,,0000,0000,0000,,my backup slide, which gives you SIDH in\Nits full glory - you consider some extra
Dialogue: 0,0:39:40.65,0:39:46.17,Default,,0000,0000,0000,,information being sent, namely these\Ngenerators from my group and actually the
Dialogue: 0,0:39:46.17,0:39:51.70,Default,,0000,0000,0000,,same commutative diagram for SIDH. You\Ncould, in theory, compute using another
Dialogue: 0,0:39:51.70,0:39:57.67,Default,,0000,0000,0000,,group as well, that has the proper\Nsubgroup structure, but the graph that you
Dialogue: 0,0:39:57.67,0:40:03.91,Default,,0000,0000,0000,,will find is probably not going to be\Ninteresting. I mean it's really somehow
Dialogue: 0,0:40:03.91,0:40:09.10,Default,,0000,0000,0000,,that Righello property that makes the\Ngraph interesting for cryptography. But
Dialogue: 0,0:40:09.10,0:40:15.02,Default,,0000,0000,0000,,yes, in theory, the SIDH commutative\Ndiagram you could also compute for other
Dialogue: 0,0:40:15.02,0:40:20.72,Default,,0000,0000,0000,,groups, yes.\NMicrophone 2: OK.
Dialogue: 0,0:40:20.72,0:40:28.91,Default,,0000,0000,0000,,Microphone 3: Uh... How good are classical\Nalgorithms that tried to reverse that SIDH
Dialogue: 0,0:40:28.91,0:40:37.01,Default,,0000,0000,0000,,problem, because that will be the bound\Nfor how large your keys have to be, to be
Dialogue: 0,0:40:37.01,0:40:39.93,Default,,0000,0000,0000,,secure.\Nnaehrwert: Yes. So the question was: How
Dialogue: 0,0:40:39.93,0:40:46.98,Default,,0000,0000,0000,,good are classical algorithms? And again,\NI said, I think the runtime for those is
Dialogue: 0,0:40:46.98,0:40:52.95,Default,,0000,0000,0000,,squared of p. And this tells you how big\Nyou have to choose B.
Dialogue: 0,0:40:52.95,0:40:59.16,Default,,0000,0000,0000,,Microphone 3: And how confident are you\Nthat this really is hard for quantum
Dialogue: 0,0:40:59.16,0:41:03.51,Default,,0000,0000,0000,,computers as well?\Nnaehwert: Well, how confident am I that
Dialogue: 0,0:41:03.51,0:41:07.02,Default,,0000,0000,0000,,this is really hard for quantum\Ncomputers? So first of all, cryptography
Dialogue: 0,0:41:07.02,0:41:10.74,Default,,0000,0000,0000,,is all about confidence, right? So someone\Nproposes a problem, this problem gets
Dialogue: 0,0:41:10.74,0:41:15.35,Default,,0000,0000,0000,,crypto-analyzed. And if it's not broken\Nafter 40 years, then people will say, I'm
Dialogue: 0,0:41:15.35,0:41:19.81,Default,,0000,0000,0000,,pretty, pretty confident this is good. And\Nmaybe if the NSA doesn't tell you anything
Dialogue: 0,0:41:19.81,0:41:26.20,Default,,0000,0000,0000,,about it, or maybe if they don't have, you\Nknow, anything on it, then you can also
Dialogue: 0,0:41:26.20,0:41:35.24,Default,,0000,0000,0000,,see that you're confident in it. But I\Nthink this is really a question that only
Dialogue: 0,0:41:35.24,0:41:40.98,Default,,0000,0000,0000,,time can answer, right?\NMicrophone 4: Yeah. Is it possible to
Dialogue: 0,0:41:40.98,0:41:47.32,Default,,0000,0000,0000,,prove that no polynomial-time algorithms\Nfor the isogenies problems {\b1}can{\b0} exist
Dialogue: 0,0:41:47.32,0:41:51.81,Default,,0000,0000,0000,,for a quantum computer?\Nnaehrwert: Yeah, that's a good question.
Dialogue: 0,0:41:51.81,0:41:59.61,Default,,0000,0000,0000,,How do you prove that no algorithm exists?\NThis brings us into territories, like ...
Dialogue: 0,0:41:59.61,0:42:06.38,Default,,0000,0000,0000,,Yeah. I don't know. Yeah.\NNo. Let's not do that.
Dialogue: 0,0:42:06.38,0:42:16.50,Default,,0000,0000,0000,,Microphone 1: Yeah. Good talk by the way.\NAt the last slide you say that this is hard
Dialogue: 0,0:42:16.50,0:42:20.85,Default,,0000,0000,0000,,for a quantum [computer]. But that can't\Nbe true because we don't even know if any
Dialogue: 0,0:42:20.85,0:42:25.60,Default,,0000,0000,0000,,algorithm is hard for classic computers.\NRight? So, I'm guessing you're saying that
Dialogue: 0,0:42:25.60,0:42:31.34,Default,,0000,0000,0000,,{\b1}intuitively{\b0} it feels hard, which, you\Nknow, is the same intuition I have about
Dialogue: 0,0:42:31.34,0:42:37.65,Default,,0000,0000,0000,,e.g. factoring in. So, you mention there's\Nmultiple candidates for post-quantum
Dialogue: 0,0:42:37.65,0:42:44.12,Default,,0000,0000,0000,,cryptography, and they all intuitively\Nfeel hard somehow. Do you know if this
Dialogue: 0,0:42:44.12,0:42:48.48,Default,,0000,0000,0000,,specific candidate, would this be your\Nhorse in a race? Is there anything about
Dialogue: 0,0:42:48.48,0:42:54.32,Default,,0000,0000,0000,,this specific way that you think would be\Nthe best fit for post-quantum
Dialogue: 0,0:42:54.32,0:42:59.31,Default,,0000,0000,0000,,cryptography?\Nnaehrwert: Okay. Your opinion is very
Dialogue: 0,0:42:59.31,0:43:03.41,Default,,0000,0000,0000,,valid. Of course, we don't know if it's\Nhard, right? This connects back to the
Dialogue: 0,0:43:03.41,0:43:07.40,Default,,0000,0000,0000,,other questions: How do you trust\Nsomething like that? Again, people do
Dialogue: 0,0:43:07.40,0:43:11.95,Default,,0000,0000,0000,,crypto analysis for 40 years or whatever.\NAnd then you say, oh, no one found
Dialogue: 0,0:43:11.95,0:43:16.03,Default,,0000,0000,0000,,anything - it's probably hard, right? But\Nit hasn't been an exact 40 years. You
Dialogue: 0,0:43:16.03,0:43:21.48,Default,,0000,0000,0000,,cannot say that. Indeed these things are\Nrelatively new. And personally, I'm not
Dialogue: 0,0:43:21.48,0:43:28.43,Default,,0000,0000,0000,,gonna, I don't know, believe in any of\Nthese things until some time passes. So my
Dialogue: 0,0:43:28.43,0:43:33.06,Default,,0000,0000,0000,,reason for looking into these things\Nreally is more a mathematical curiosity,
Dialogue: 0,0:43:33.06,0:43:38.50,Default,,0000,0000,0000,,because I think these things are\Nbeautiful. And the cryptography that
Dialogue: 0,0:43:38.50,0:43:43.37,Default,,0000,0000,0000,,arises from it is more of a side-effect\Nfor me personally. So I'm not going to put
Dialogue: 0,0:43:43.37,0:43:51.18,Default,,0000,0000,0000,,out any guesses on which of these things\Nis actually going to win the PQ race or
Dialogue: 0,0:43:51.18,0:43:56.14,Default,,0000,0000,0000,,whatever.\NMicrophone 2: (Yeah. I am.) You showed or
Dialogue: 0,0:43:56.14,0:44:01.66,Default,,0000,0000,0000,,said you think it's hard for the classical\Nway and for the quantum cryptography way.
Dialogue: 0,0:44:01.66,0:44:08.83,Default,,0000,0000,0000,,I think I just read a paper last year\Nabout a combined way in classical and
Dialogue: 0,0:44:08.83,0:44:14.26,Default,,0000,0000,0000,,quantum cryptography combined, which\Noutperforms either one of those ways. Do
Dialogue: 0,0:44:14.26,0:44:23.82,Default,,0000,0000,0000,,you think this could also be relevant or\Ngonna make this one way to put in
Dialogue: 0,0:44:23.82,0:44:27.60,Default,,0000,0000,0000,,computable in polynomial time?\Nnaehrwert: Are you talking about an
Dialogue: 0,0:44:27.60,0:44:32.64,Default,,0000,0000,0000,,algorithm that somehow combines a\Nclassical step and a quantum step to break
Dialogue: 0,0:44:32.64,0:44:33.90,Default,,0000,0000,0000,,this?\NMicrophone 2: Yes.
Dialogue: 0,0:44:33.90,0:44:39.39,Default,,0000,0000,0000,,naehwert: Yeah well, most algorithms that\Nwe say use a quantum computer involve a
Dialogue: 0,0:44:39.39,0:44:43.33,Default,,0000,0000,0000,,classical part anyways. If you think about\NShor's algorithm, there's a classical part
Dialogue: 0,0:44:43.33,0:44:49.60,Default,,0000,0000,0000,,and a quantum computer part. So I'm not\Nsure which algorithm you read about, but
Dialogue: 0,0:44:49.60,0:44:53.56,Default,,0000,0000,0000,,I'm sure that somehow all the quantum\Nalgorithms involve a classical part
Dialogue: 0,0:44:53.56,0:44:58.69,Default,,0000,0000,0000,,implicitly anyways.\NHerald: Signal Angel?
Dialogue: 0,0:44:58.69,0:45:03.40,Default,,0000,0000,0000,,Microphone 3: Yeah. Can you please name\Nthe mentioned contestants in the list
Dialogue: 0,0:45:03.40,0:45:10.40,Default,,0000,0000,0000,,'Challenge-based Isogenies'?\Nnaehrwert: So there is SSIKE, I believe:
Dialogue: 0,0:45:10.40,0:45:16.17,Default,,0000,0000,0000,,supersingular isogeny key encapsulation,\Nbut actually I don't really follow the
Dialogue: 0,0:45:16.17,0:45:22.08,Default,,0000,0000,0000,,NIST thingy closely, so I actually\Ncouldn't even name all the names that are
Dialogue: 0,0:45:22.08,0:45:27.44,Default,,0000,0000,0000,,involved in it, but you can look it up on the\NNIST website and I believe somewhere there
Dialogue: 0,0:45:27.44,0:45:33.19,Default,,0000,0000,0000,,is also a classification of the contenders\Ninto this view. So they will tell you
Dialogue: 0,0:45:33.19,0:45:37.18,Default,,0000,0000,0000,,which contenders are based on lattices and\Nwhich contenders are based on codes and
Dialogue: 0,0:45:37.18,0:45:41.40,Default,,0000,0000,0000,,which ones are somehow based on isogenies.\NBut off the top of my head, actually, I
Dialogue: 0,0:45:41.40,0:45:49.99,Default,,0000,0000,0000,,don't even know. Sorry.\NMicrophone 1: So if I got everything
Dialogue: 0,0:45:49.99,0:45:56.73,Default,,0000,0000,0000,,correctly, though, those isogenies are\Ngroup homomorphisms between the elliptic
Dialogue: 0,0:45:56.73,0:46:03.58,Default,,0000,0000,0000,,curves and the factor group of the\Nelliptic curve by g. And which has kernel
Dialogue: 0,0:46:03.58,0:46:05.04,Default,,0000,0000,0000,,g again.\Nnaehrwert: Yes.
Dialogue: 0,0:46:05.04,0:46:10.17,Default,,0000,0000,0000,,Microphone 1: And you said that finding\Nthe isogeny path in the graph is rather
Dialogue: 0,0:46:10.17,0:46:15.72,Default,,0000,0000,0000,,difficult. But wouldn't the real\Ndifficulty rather be finding the subgroups
Dialogue: 0,0:46:15.72,0:46:20.29,Default,,0000,0000,0000,,G - because a group homomorphism between\Nthe elliptic curve and the factor group
Dialogue: 0,0:46:20.29,0:46:23.45,Default,,0000,0000,0000,,with kernel g is simply the canonical\Nprotection.
Dialogue: 0,0:46:23.45,0:46:29.50,Default,,0000,0000,0000,,naehrtwert: Exactly. So I see you are\Nmathematically trained, which is very nice
Dialogue: 0,0:46:29.50,0:46:34.14,Default,,0000,0000,0000,,and I appreciate that, this is great and I\Nam very happy about that. And yeah, if you
Dialogue: 0,0:46:34.14,0:46:41.44,Default,,0000,0000,0000,,look at the slide actually, the secrets\Nare these alphas and betas, which somehow
Dialogue: 0,0:46:41.44,0:46:46.42,Default,,0000,0000,0000,,determine the subgroup. And yes, finding\Nthose isogeny path is equivalent to
Dialogue: 0,0:46:46.42,0:46:50.24,Default,,0000,0000,0000,,finding the alpha, somehow, that generates\Nthis group. And as you said correctly,
Dialogue: 0,0:46:50.24,0:46:56.67,Default,,0000,0000,0000,,finding the isogeny path is somehow\Nfinding this group. But it's just
Dialogue: 0,0:46:56.67,0:47:00.94,Default,,0000,0000,0000,,restating the problem. But it's still hard\Nsomehow to find this group. Yeah.
Dialogue: 0,0:47:00.94,0:47:05.43,Default,,0000,0000,0000,,Microhone 1: All right. Thanks.\Nnaehrwert: Thank you. Very cool.
Dialogue: 0,0:47:05.43,0:47:08.94,Default,,0000,0000,0000,,Microphone 2: Yeah, thank you for the\Ngreat talk. So, can you play this game a
Dialogue: 0,0:47:08.94,0:47:15.27,Default,,0000,0000,0000,,little bit further? I mean, can you choose\Nhigher-dimensional abelian varieties to
Dialogue: 0,0:47:15.27,0:47:19.44,Default,,0000,0000,0000,,make it even more secure? Or is it just\Nabsolutely inaccessible? I mean, from the
Dialogue: 0,0:47:19.44,0:47:24.16,Default,,0000,0000,0000,,computation perspective, the choice of\Nfield of definition is difficult, for
Dialogue: 0,0:47:24.16,0:47:26.43,Default,,0000,0000,0000,,example, so...\Nnaehrwert: Okay, so the question was on
Dialogue: 0,0:47:26.43,0:47:30.51,Default,,0000,0000,0000,,whether you can use higher-dimensional\Nabelian varieties and maybe for the people
Dialogue: 0,0:47:30.51,0:47:35.76,Default,,0000,0000,0000,,who don't know what that means: You can\Nattach a dimension to these things in the
Dialogue: 0,0:47:35.76,0:47:41.27,Default,,0000,0000,0000,,elliptic curves, somehow have a dimension\N1 attached to them. And the question was,
Dialogue: 0,0:47:41.27,0:47:45.72,Default,,0000,0000,0000,,can you somehow look at dimension 2,\Ndimension 3 or higher? And actually, back
Dialogue: 0,0:47:45.72,0:47:51.21,Default,,0000,0000,0000,,in the days when people were thinking\Nabout the DLP problem on the points of
Dialogue: 0,0:47:51.21,0:47:55.57,Default,,0000,0000,0000,,elliptic curves that I mentioned briefly,\Npeople had the idea of maybe using
Dialogue: 0,0:47:55.57,0:48:01.23,Default,,0000,0000,0000,,dimension 2 or dimension 3. But it turns\Nout, that the DLP problem actually, at
Dialogue: 0,0:48:01.23,0:48:06.17,Default,,0000,0000,0000,,some point, gets easier in higher\Ndimensions. So, classically if you look at
Dialogue: 0,0:48:06.17,0:48:10.25,Default,,0000,0000,0000,,the DLP, you somehow want to stay at\Ndimension 2, but now, what you can do is,
Dialogue: 0,0:48:10.25,0:48:14.57,Default,,0000,0000,0000,,you can look at isogenies between\Ndimension-2 and dimension-3 ones. And
Dialogue: 0,0:48:14.57,0:48:17.86,Default,,0000,0000,0000,,actually the problem that arises there -\Nand this makes elliptical curves very
Dialogue: 0,0:48:17.86,0:48:23.26,Default,,0000,0000,0000,,special - is that we can compute isogenies\Nrather efficiently for elliptical curves
Dialogue: 0,0:48:23.26,0:48:27.51,Default,,0000,0000,0000,,because of Velu's formulas. Okay. So\Nthis gives us a very direct means of
Dialogue: 0,0:48:27.51,0:48:32.67,Default,,0000,0000,0000,,computing D, but it actually gets hard as\Nthe dimension grows. For example, for
Dialogue: 0,0:48:32.67,0:48:40.09,Default,,0000,0000,0000,,dimension 2 already, the only isogenies\Nthat I am able to efficiently compute are
Dialogue: 0,0:48:40.09,0:48:45.89,Default,,0000,0000,0000,,2- and 3-isogenies. So there are some\Npackages out there that can compute higher
Dialogue: 0,0:48:45.89,0:48:50.85,Default,,0000,0000,0000,,ones, but only if my prime is very small\Nand for dimension 3 and higher it gets
Dialogue: 0,0:48:50.85,0:48:55.81,Default,,0000,0000,0000,,even harder. And then there is another\Nthing that comes into play. So dimension-2
Dialogue: 0,0:48:55.81,0:49:00.30,Default,,0000,0000,0000,,varieties, they all arise from what we\Ncall hyperelliptic curves. But if we look
Dialogue: 0,0:49:00.30,0:49:07.26,Default,,0000,0000,0000,,at dimension-3s and higher, then sometimes\Nyou land at a point in your graph that
Dialogue: 0,0:49:07.26,0:49:11.60,Default,,0000,0000,0000,,does not come from a hyperelliptic curve\Nanymore. So there is another complication.
Dialogue: 0,0:49:11.60,0:49:17.60,Default,,0000,0000,0000,,So I mean, I had a friend who was looking\Ninto genus-2 isogenies and it's possible
Dialogue: 0,0:49:17.60,0:49:24.26,Default,,0000,0000,0000,,to go there. But I don't know. I think\Npersonally this is more of a toy than
Dialogue: 0,0:49:24.26,0:49:31.44,Default,,0000,0000,0000,,something that's good in practice.\NMicrophone 2: Can you use this scheme to
Dialogue: 0,0:49:31.44,0:49:35.65,Default,,0000,0000,0000,,implement a fully homomorphic encryption\Nscheme? Or is it already?
Dialogue: 0,0:49:35.65,0:49:40.86,Default,,0000,0000,0000,,naehrwert: Uhhh... No. No.\N{\i1}laughing{\i0}
Dialogue: 0,0:49:40.86,0:49:45.44,Default,,0000,0000,0000,,naehrwert: Yeah, no fully homomorphic\Nencryption is somehow a pipe dream, but I
Dialogue: 0,0:49:45.44,0:49:51.03,Default,,0000,0000,0000,,mean sometimes it's possible. So the idea\Nis that you can add cipher texts and get
Dialogue: 0,0:49:51.03,0:49:55.84,Default,,0000,0000,0000,,the sum of the ciphered texts and have a\Nsecond operation, namely you should be
Dialogue: 0,0:49:55.84,0:50:00.12,Default,,0000,0000,0000,,able to multiply ciphertexts and get the\Nmultiplication of two ciphertexts. But we
Dialogue: 0,0:50:00.12,0:50:07.49,Default,,0000,0000,0000,,didn't even talk about encryption.\NMicrophone 2: Yeah. Another question: Is
Dialogue: 0,0:50:07.49,0:50:12.11,Default,,0000,0000,0000,,there any crypto primitive used in the\Nisogeny approach that cannot be Stark-
Dialogue: 0,0:50:12.11,0:50:16.02,Default,,0000,0000,0000,,reduced to finding a hidden\Nsubgroup in an abelian group?
Dialogue: 0,0:50:16.02,0:50:18.87,Default,,0000,0000,0000,,naehrwert: Could you repeat the\Nquestion, please?
Dialogue: 0,0:50:18.87,0:50:22.96,Default,,0000,0000,0000,,Microphone 2: Is there any crypto\Nprimitive used in the isogeny approach
Dialogue: 0,0:50:22.96,0:50:28.56,Default,,0000,0000,0000,,that cannot be Stark-reduced to finding a\Nhidden subgroup in an abelian group?
Dialogue: 0,0:50:28.56,0:50:36.86,Default,,0000,0000,0000,,naehrwert: Okay. I think this question\Ntries to connect back to the hidden shift
Dialogue: 0,0:50:36.86,0:50:44.11,Default,,0000,0000,0000,,problem or the hidden subgroup problem and\NBerg's algorithm. But I think I'm not able
Dialogue: 0,0:50:44.11,0:50:47.67,Default,,0000,0000,0000,,to answer that question now without\Ntalking to the person that actually asked
Dialogue: 0,0:50:47.67,0:50:55.13,Default,,0000,0000,0000,,it because it's a bit vague.\NSo I'm sorry about that.
Dialogue: 0,0:50:55.13,0:50:59.05,Default,,0000,0000,0000,,Microphone 3: How do you send an\Nelliptical over the wire?
Dialogue: 0,0:50:59.05,0:51:02.68,Default,,0000,0000,0000,,naehrwert: Yeah, maybe I should answer\Nthat actually. So we saw the
Dialogue: 0,0:51:02.68,0:51:09.00,Default,,0000,0000,0000,,parameterization of the curve that had\Nthese coefficients A and B. But what
Dialogue: 0,0:51:09.00,0:51:14.51,Default,,0000,0000,0000,,I didn't tell you is that to an elliptic\Ncurve you can actually attach what we call
Dialogue: 0,0:51:14.51,0:51:19.77,Default,,0000,0000,0000,,an invariant in mathematics and for an\Nelliptical curve, this is called a
Dialogue: 0,0:51:19.77,0:51:25.67,Default,,0000,0000,0000,,j-invariant and it's a single integer\Nwhich determines this elliptical curve
Dialogue: 0,0:51:25.67,0:51:29.60,Default,,0000,0000,0000,,uniquely. So if I want to send an\Nelliptical curve, I can simply send you
Dialogue: 0,0:51:29.60,0:51:34.60,Default,,0000,0000,0000,,its j-invariant. And if you know the field\Nof definition, you're going to be able to
Dialogue: 0,0:51:34.60,0:51:40.19,Default,,0000,0000,0000,,somehow recompute it just from the single\Nvalue. So it's actually quite a compact
Dialogue: 0,0:51:40.19,0:51:45.97,Default,,0000,0000,0000,,representation which makes\Nthis also interesting. Yeah.
Dialogue: 0,0:51:45.97,0:51:49.26,Default,,0000,0000,0000,,Herald: I guess this is all. Thank you.
Dialogue: 0,0:51:49.26,0:51:54.86,Default,,0000,0000,0000,,{\i1}applause{\i0}
Dialogue: 0,0:51:54.86,0:51:58.80,Default,,0000,0000,0000,,{\i1}postroll music{\i0}
Dialogue: 0,0:51:58.80,0:52:23.00,Default,,0000,0000,0000,,subtitles created by c3subtitles.de\Nin the year 2020. Join, and help us!