[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:18.58,Default,,0000,0000,0000,,{\i1}35C3 preroll music{\i0}
Dialogue: 0,0:00:18.58,0:00:25.62,Default,,0000,0000,0000,,Herald: The next talk is called "The year\Nin post-quantum crypto" by Tanja Lange,
Dialogue: 0,0:00:25.62,0:00:32.44,Default,,0000,0000,0000,,she's researching in Eindhoven, and Daniel\NBernstein, researching at the University
Dialogue: 0,0:00:32.44,0:00:39.25,Default,,0000,0000,0000,,of Chicago. They both had the first ever\Nconference on post-quantum cryptography in
Dialogue: 0,0:00:39.25,0:00:46.74,Default,,0000,0000,0000,,2006 and they both contribute to libsalt\Ncrypto library. Their talk is going to be
Dialogue: 0,0:00:46.74,0:00:52.83,Default,,0000,0000,0000,,a summary of the NIST post-quantum crypto\Ncompetition and they're gonna provide an
Dialogue: 0,0:00:52.83,0:00:58.85,Default,,0000,0000,0000,,overview of problems of post-quantum\Ncryptography and hopefully show us how to
Dialogue: 0,0:00:58.85,0:01:03.29,Default,,0000,0000,0000,,integrate post-quantum crypto in existing\Nsoftware. Please welcome them with a huge
Dialogue: 0,0:01:03.29,0:01:04.71,Default,,0000,0000,0000,,round of applause.
Dialogue: 0,0:01:04.71,0:01:15.73,Default,,0000,0000,0000,,{\i1}applause{\i0}
Dialogue: 0,0:01:15.73,0:01:19.83,Default,,0000,0000,0000,,Tanja Lange: All right, well, thank you.\NFirst of all, this title word post-quantum
Dialogue: 0,0:01:19.83,0:01:24.89,Default,,0000,0000,0000,,cryptography, what it means, we're talking\Nabout cryptography where we're designing
Dialogue: 0,0:01:24.89,0:01:29.79,Default,,0000,0000,0000,,the systems under the assumption that our\Nattacker - not the user, just the attacker
Dialogue: 0,0:01:29.79,0:01:34.52,Default,,0000,0000,0000,,- has a large quantum computer. Also to\Nremind you from three years ago, when we
Dialogue: 0,0:01:34.52,0:01:42.32,Default,,0000,0000,0000,,showed you the attacker, we're talking\Nabout attackers. All right. So, we're
Dialogue: 0,0:01:42.32,0:01:48.05,Default,,0000,0000,0000,,seeing like over the last few years 2015,\Nsay middle August, there was a big
Dialogue: 0,0:01:48.05,0:01:51.32,Default,,0000,0000,0000,,announcement by the NSA saying "Oh yeah,\Nacutally the world should care about post-
Dialogue: 0,0:01:51.32,0:01:55.50,Default,,0000,0000,0000,,quantum cryptography. We need more\Nresearch." They finally wake up to it and
Dialogue: 0,0:01:55.50,0:01:59.23,Default,,0000,0000,0000,,actually they had a nice roll-out effect,\Nthat pretty much every agency - just
Dialogue: 0,0:01:59.23,0:02:03.92,Default,,0000,0000,0000,,highlighting three of them here, so U.K.,\Nthe Netherlands and the NSA themselves -
Dialogue: 0,0:02:03.92,0:02:08.53,Default,,0000,0000,0000,,made some statements about the urgency of\Nrolling out post-quantum, that normal
Dialogue: 0,0:02:08.53,0:02:11.84,Default,,0000,0000,0000,,cryptography that we're currently using,\Nso elliptic curves and RSA and Diffie-
Dialogue: 0,0:02:11.84,0:02:16.16,Default,,0000,0000,0000,,Hellman and finite fields, will be broken\Nas soon as a quantum computer, and the
Dialogue: 0,0:02:16.16,0:02:19.23,Default,,0000,0000,0000,,NIST, which is the National Institute for\NStandards and Technology, so it's an
Dialogue: 0,0:02:19.23,0:02:25.14,Default,,0000,0000,0000,,institute in the U.S., which is working on\Nstandards said, ok, we're gonna call for a
Dialogue: 0,0:02:25.14,0:02:30.79,Default,,0000,0000,0000,,standardization project for post-quatum\Ncryptography. So yes, it's a U.S.
Dialogue: 0,0:02:30.79,0:02:36.03,Default,,0000,0000,0000,,institution, but it has in cryptography a\Nmostly good history. They have been
Dialogue: 0,0:02:36.03,0:02:39.31,Default,,0000,0000,0000,,running competitions which gave us AES.\NThey've been running competitions which
Dialogue: 0,0:02:39.31,0:02:44.14,Default,,0000,0000,0000,,gave us the SHA3. And they also, without a\Ncompetition, gave us Dual_EC.
Dialogue: 0,0:02:44.14,0:02:48.33,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NTL: So, competitions with NIST, good
Dialogue: 0,0:02:48.33,0:02:54.22,Default,,0000,0000,0000,,thing, everything else, well, judge for\Nyourself. This sounds like a great story.
Dialogue: 0,0:02:54.22,0:02:58.10,Default,,0000,0000,0000,,It's also a little bit disappointing when\Nyou look at where it started. So back in
Dialogue: 0,0:02:58.10,0:03:01.86,Default,,0000,0000,0000,,2003, Dan here coined the term post-\Nquantum cryptography and then they've been
Dialogue: 0,0:03:01.86,0:03:06.21,Default,,0000,0000,0000,,running around for 10 years going like\N"The end is nigh, please invest in post-
Dialogue: 0,0:03:06.21,0:03:11.30,Default,,0000,0000,0000,,quantum cryptography, do something", just\Nthat 10 years later the NSA said "Oh my
Dialogue: 0,0:03:11.30,0:03:15.29,Default,,0000,0000,0000,,God, we have to do something, quatum\Ncomputers are comming". So it's a little
Dialogue: 0,0:03:15.29,0:03:18.29,Default,,0000,0000,0000,,bit. Yeah, I told you so. Not a great\Nstory, but.
Dialogue: 0,0:03:18.29,0:03:22.25,Default,,0000,0000,0000,,Daniel J. Bernstein: All right so what\Nhappened with this competition. Well after
Dialogue: 0,0:03:22.25,0:03:27.10,Default,,0000,0000,0000,,NIST said "Hey everybody, send us some\Nproposals for post-quantum crypto to
Dialogue: 0,0:03:27.10,0:03:31.83,Default,,0000,0000,0000,,standardize", a lot of people did. So,\Nthey said actually more than 80
Dialogue: 0,0:03:31.83,0:03:35.56,Default,,0000,0000,0000,,submissions came in and some of them were\Nincomplete, like one of the requirements
Dialogue: 0,0:03:35.56,0:03:39.24,Default,,0000,0000,0000,,was include software, and whatever\Nreasons, they said some of the submissions
Dialogue: 0,0:03:39.24,0:03:42.88,Default,,0000,0000,0000,,are not complete, but they posted 69\Ncomplete submissions, the submission teams
Dialogue: 0,0:03:42.88,0:03:47.89,Default,,0000,0000,0000,,include 260 people from around the world,\Nall sorts of academia, industry, maybe
Dialogue: 0,0:03:47.89,0:03:52.01,Default,,0000,0000,0000,,even some government people. There's lots\Nand lots of names and we're not gonna go
Dialogue: 0,0:03:52.01,0:03:55.53,Default,,0000,0000,0000,,through, like, what all these things are,\Nbut we are going to say something...
Dialogue: 0,0:03:55.53,0:03:58.69,Default,,0000,0000,0000,,TL: Oh we have 60 minutes.\NDJB: Oh that's true. So BIG QUAKE: This is
Dialogue: 0,0:03:58.69,0:04:01.56,Default,,0000,0000,0000,,a code based system...\N{\i1}laughter{\i0}
Dialogue: 0,0:04:01.56,0:04:05.97,Default,,0000,0000,0000,,No, we're gonna give you some idea of,\Nlike, what the big picture is of how well
Dialogue: 0,0:04:05.97,0:04:11.63,Default,,0000,0000,0000,,these things have held up. So, these were\Nall posted by NIST on the 21st of December
Dialogue: 0,0:04:11.63,0:04:17.91,Default,,0000,0000,0000,,last year, and some of you who saw our\NLatticeHacks talk last year remember that
Dialogue: 0,0:04:17.91,0:04:21.84,Default,,0000,0000,0000,,this list, already there was some damage\Nto it by the time of our talk on the 28th
Dialogue: 0,0:04:21.84,0:04:26.69,Default,,0000,0000,0000,,of December 2017. By the end of the year,\Nthere were eight submissions that had
Dialogue: 0,0:04:26.69,0:04:30.88,Default,,0000,0000,0000,,attacks, at different levels of severity.\NI should explain the color coding here.
Dialogue: 0,0:04:30.88,0:04:36.62,Default,,0000,0000,0000,,The stuff that's in brown is less security\Nthan claimed, which could be for instance
Dialogue: 0,0:04:36.62,0:04:41.06,Default,,0000,0000,0000,,they claimed something was, it would take\N2 to the 128 operations to break and
Dialogue: 0,0:04:41.06,0:04:46.52,Default,,0000,0000,0000,,somebody says "no, it's 2 to the 100 or 2\Nto the 80". Does that really matter? Or
Dialogue: 0,0:04:46.52,0:04:49.33,Default,,0000,0000,0000,,maybe a different direction is somebody\Nsays: "this is a system where you can
Dialogue: 0,0:04:49.33,0:04:54.20,Default,,0000,0000,0000,,reuse the key any number of times", which\Nwe expect for for normal crypto systems
Dialogue: 0,0:04:54.20,0:04:57.42,Default,,0000,0000,0000,,that you can publish your key and people\Ncan keep sending you messages or you can
Dialogue: 0,0:04:57.42,0:05:01.25,Default,,0000,0000,0000,,sign many times under some keys, but\Nsometimes people claimed they had that
Dialogue: 0,0:05:01.25,0:05:06.41,Default,,0000,0000,0000,,feature and they turned out to be wrong;\Nthose were attackable, like HILA5 in this
Dialogue: 0,0:05:06.41,0:05:10.53,Default,,0000,0000,0000,,list, which is not necessarily kicking\Nthem out of the competition, because NIST
Dialogue: 0,0:05:10.53,0:05:15.47,Default,,0000,0000,0000,,said, you can have a system with one-time\Nkeys that can be useful for some
Dialogue: 0,0:05:15.47,0:05:18.79,Default,,0000,0000,0000,,applications. The things in red are,\Neverything that they proposed, all the
Dialogue: 0,0:05:18.79,0:05:24.04,Default,,0000,0000,0000,,concrete parameters are broken. The\Nunderlines are those where there's attacks
Dialogue: 0,0:05:24.04,0:05:28.06,Default,,0000,0000,0000,,scripts, Python scripts, stage scripts,\Nwhatever it takes to demonstrate that,
Dialogue: 0,0:05:28.06,0:05:33.00,Default,,0000,0000,0000,,yeah, look, here's here's your secret key,\Nor decrypting something. So that was the
Dialogue: 0,0:05:33.00,0:05:38.60,Default,,0000,0000,0000,,end of 2017. How about now. Well, OK,\Nlet's extrapolate, three days from now.
Dialogue: 0,0:05:38.60,0:05:44.51,Default,,0000,0000,0000,,Probably the situation is at least the\Nfollowing. At least by twenty eighth of
Dialogue: 0,0:05:44.51,0:05:52.47,Default,,0000,0000,0000,,December 2018, 22 submissions have\Nattacks. So it's about a third of those 69
Dialogue: 0,0:05:52.47,0:05:58.37,Default,,0000,0000,0000,,submissions, and you can see more, well,\Nmost, well, 13 of those, out of the 22,
Dialogue: 0,0:05:58.37,0:06:03.10,Default,,0000,0000,0000,,are red, mostly with underlines. I think\Nsome of this is from us, a lot from other
Dialogue: 0,0:06:03.10,0:06:07.51,Default,,0000,0000,0000,,people. And I think we did well early on\Nestablishing that people should put out
Dialogue: 0,0:06:07.51,0:06:11.24,Default,,0000,0000,0000,,scripts to demonstrate that ,yeah, you\Nreally can break these things. So again
Dialogue: 0,0:06:11.24,0:06:15.60,Default,,0000,0000,0000,,the underlines are demonstrated attacks;\Nsome of the submitters have withdrawn the
Dialogue: 0,0:06:15.60,0:06:21.12,Default,,0000,0000,0000,,broken submissions; some of them have not.\NTL: All right, so when you look at this,
Dialogue: 0,0:06:21.12,0:06:27.02,Default,,0000,0000,0000,,we're not going to go through explaining\Nthose, but let me categorize these. So
Dialogue: 0,0:06:27.02,0:06:30.31,Default,,0000,0000,0000,,when we look at the ones which are not\Ncompletely smashed and broken, we can put
Dialogue: 0,0:06:30.31,0:06:33.90,Default,,0000,0000,0000,,them into boxes, we can say "hey, what is\Nthe underlying mathematical problem",
Dialogue: 0,0:06:33.90,0:06:38.77,Default,,0000,0000,0000,,"what do we hope is something the attacker\Nhas to do in order to break the
Dialogue: 0,0:06:38.77,0:06:42.92,Default,,0000,0000,0000,,cryptosystem". And then there is one\Ncategory of using error-correcting codes,
Dialogue: 0,0:06:42.92,0:06:48.05,Default,,0000,0000,0000,,which is then used for building an\Nencryption system or a signature scheme,
Dialogue: 0,0:06:48.05,0:06:51.76,Default,,0000,0000,0000,,hash functions, you can only build\Nsignature schemes from, isogeny-based
Dialogue: 0,0:06:51.76,0:06:55.38,Default,,0000,0000,0000,,crypto, for the competition we're only\Nseeing an encryption system, and honestly
Dialogue: 0,0:06:55.38,0:07:00.46,Default,,0000,0000,0000,,all the signatures we have seen so far are\Npretty inefficient. Lattices we see for
Dialogue: 0,0:07:00.46,0:07:04.79,Default,,0000,0000,0000,,both, that is something we talked about\Nlast year, so if you want to get a full-
Dialogue: 0,0:07:04.79,0:07:08.68,Default,,0000,0000,0000,,blown lattice explanation, go for last\Nyear's talk. And then finally, there's
Dialogue: 0,0:07:08.68,0:07:13.82,Default,,0000,0000,0000,,something using systems in many variables,\Nmany equations, and we get signatures and
Dialogue: 0,0:07:13.82,0:07:19.05,Default,,0000,0000,0000,,encryption from that. So that's one way of\Nsaying "Well, these are good things for
Dialogue: 0,0:07:19.05,0:07:23.34,Default,,0000,0000,0000,,post-quantum". It does not mean that\Neverything which isn't in these boxes is
Dialogue: 0,0:07:23.34,0:07:28.29,Default,,0000,0000,0000,,secure. You can still design a system,\Nwhich somehow relates to this math
Dialogue: 0,0:07:28.29,0:07:32.81,Default,,0000,0000,0000,,problem, but the attacker can do a way\Naround. Some of those systems, RaCoSS I'll
Dialogue: 0,0:07:32.81,0:07:37.89,Default,,0000,0000,0000,,get back to later, is a code-based system\N- code-based is on the list, first one up
Dialogue: 0,0:07:37.89,0:07:42.15,Default,,0000,0000,0000,,there - so should be totally secure, and\Nyet it's one of the red underlined
Dialogue: 0,0:07:42.15,0:07:47.60,Default,,0000,0000,0000,,systems. So just being in one of the\Ncategories does not mean it's secure, but
Dialogue: 0,0:07:47.60,0:07:52.97,Default,,0000,0000,0000,,it's at least some hopeful and helpful\Nthing to box things. There are other ways
Dialogue: 0,0:07:52.97,0:07:56.78,Default,,0000,0000,0000,,of describing why this is the situation we\Nhave now.
Dialogue: 0,0:07:56.78,0:08:00.45,Default,,0000,0000,0000,,DJB: As an example of this kind of\Ncategorization, sometimes people might
Dialogue: 0,0:08:00.45,0:08:05.43,Default,,0000,0000,0000,,say: "Oh, lattice-based cryptography is is\Nthe safe thing to do. All of that red was
Dialogue: 0,0:08:05.43,0:08:09.42,Default,,0000,0000,0000,,people who were not using lattice-based-\Ncryptography and everything lattice-based
Dialogue: 0,0:08:09.42,0:08:13.73,Default,,0000,0000,0000,,is good, everything else is scary". But if\Nyou look at the lattice-based systems,
Dialogue: 0,0:08:13.73,0:08:18.86,Default,,0000,0000,0000,,it's not all black. There's some red stuff\Nhere. Compact LWE. That one is broken,
Dialogue: 0,0:08:18.86,0:08:21.50,Default,,0000,0000,0000,,with a script, we're quite sure it's\Nbroken. There's some others with some
Dialogue: 0,0:08:21.50,0:08:25.22,Default,,0000,0000,0000,,damage, DRS, HILA5. So it's not that the\Nlattice-based submissions have held up
Dialogue: 0,0:08:25.22,0:08:30.40,Default,,0000,0000,0000,,perfectly and also it's not just that\Nthese are isolated mistakes that people
Dialogue: 0,0:08:30.40,0:08:34.79,Default,,0000,0000,0000,,have made. There's ongoing research which\Nis making better and better lattice
Dialogue: 0,0:08:34.79,0:08:39.34,Default,,0000,0000,0000,,attacks. For instance, some papers from\Nlast month and this month from the three
Dialogue: 0,0:08:39.34,0:08:44.78,Default,,0000,0000,0000,,authors listed there are talking about\Nlattice-based systems being broken by
Dialogue: 0,0:08:44.78,0:08:49.80,Default,,0000,0000,0000,,decryption failures. Now this phenomenon,\Nmost of the lattice submissions have
Dialogue: 0,0:08:49.80,0:08:57.40,Default,,0000,0000,0000,,occasional decryption failures. Once every\N2 to the 64 ciphertexts maybe, you won't
Dialogue: 0,0:08:57.40,0:09:01.63,Default,,0000,0000,0000,,be able to decrypt. Which might sound like\N"oh, it's no big deal, it's, maybe
Dialogue: 0,0:09:01.63,0:09:05.38,Default,,0000,0000,0000,,occasionally you might have some user has\Nthat happen and they'll just, the browser
Dialogue: 0,0:09:05.38,0:09:10.78,Default,,0000,0000,0000,,will reconnect, whatever it takes, it's\Nnot a significant failure rate". Except
Dialogue: 0,0:09:10.78,0:09:15.66,Default,,0000,0000,0000,,that those failures, if the attacker is\Ntrying to decrypt a particular cipher text
Dialogue: 0,0:09:15.66,0:09:20.12,Default,,0000,0000,0000,,or maybe attack or figure out somebody's\Nsecret key, they can usually get that
Dialogue: 0,0:09:20.12,0:09:24.80,Default,,0000,0000,0000,,information out of watching the pattern of\Ndecryption failures, if decryption
Dialogue: 0,0:09:24.80,0:09:29.17,Default,,0000,0000,0000,,failures happen often enough. And these\Npapers are saying, for two different
Dialogue: 0,0:09:29.17,0:09:33.41,Default,,0000,0000,0000,,reasons, decryption failures are actually\Nhappening more often, maybe much more
Dialogue: 0,0:09:33.41,0:09:37.39,Default,,0000,0000,0000,,often than people claim. So that's kind of\Nscary.
Dialogue: 0,0:09:37.39,0:09:42.62,Default,,0000,0000,0000,,TL: All right. One explanation, which I of\Ncourse like very much. I've been running a
Dialogue: 0,0:09:42.62,0:09:49.17,Default,,0000,0000,0000,,European protocol, PQCRYPTO, and just use\Neverything in our portfolio. It's good
Dialogue: 0,0:09:49.17,0:09:53.25,Default,,0000,0000,0000,,right? Actually, it's looking better than\Nthe arguments saying: "I'll use everything
Dialogue: 0,0:09:53.25,0:09:56.49,Default,,0000,0000,0000,,lattice-based. We have one which is\Nslightly scratched, but everything else is
Dialogue: 0,0:09:56.49,0:10:00.58,Default,,0000,0000,0000,,good. Right. Yay."\NDJB: Except, well, there's another
Dialogue: 0,0:10:00.58,0:10:06.35,Default,,0000,0000,0000,,explanation than just, well, whoever these\NPQCRYPTO project people are, obviously the
Dialogue: 0,0:10:06.35,0:10:10.99,Default,,0000,0000,0000,,right people, putting together a great\Nportfolio. There's another possibility.
Dialogue: 0,0:10:10.99,0:10:15.16,Default,,0000,0000,0000,,Not saying this is right, but you could\Nimagine the cryptanalysts who are deciding
Dialogue: 0,0:10:15.16,0:10:20.88,Default,,0000,0000,0000,,what to do out of that huge pile of 69\Nsubmissions. Maybe they thought the people
Dialogue: 0,0:10:20.88,0:10:25.43,Default,,0000,0000,0000,,who were in this project doing this stuff\Nfor some number of years are maybe not the
Dialogue: 0,0:10:25.43,0:10:30.36,Default,,0000,0000,0000,,top targets. Maybe you should look at the\Nother 49 submissions. Maybe you should
Dialogue: 0,0:10:30.36,0:10:34.08,Default,,0000,0000,0000,,look at the submissions with the\Nspecification written in Microsoft Word.
Dialogue: 0,0:10:34.08,0:10:38.54,Default,,0000,0000,0000,,Probably more likely to be broken. Maybe\Nthere's other ways that you can decide how
Dialogue: 0,0:10:38.54,0:10:41.78,Default,,0000,0000,0000,,to - no offence to Microsoft people -\NTL: It worked.
Dialogue: 0,0:10:41.78,0:10:48.72,Default,,0000,0000,0000,,DJB: yeah, that did work coincidentally.\NYeah. So, the thing to keep in mind is
Dialogue: 0,0:10:48.72,0:10:53.21,Default,,0000,0000,0000,,that there's a huge pile of submissions,\Nmore than a million words in these 69
Dialogue: 0,0:10:53.21,0:10:57.93,Default,,0000,0000,0000,,submission documents, and this is like, a\Nword in English is usually a kind of
Dialogue: 0,0:10:57.93,0:11:01.66,Default,,0000,0000,0000,,imprecise thing, reviewing that, this is I\Nwould say more effort than reviewing a
Dialogue: 0,0:11:01.66,0:11:06.53,Default,,0000,0000,0000,,million lines of code. This is a lot of\Nstuff, lot of junk to go through. There's
Dialogue: 0,0:11:06.53,0:11:10.98,Default,,0000,0000,0000,,a real flood, there's too much for us to\Nall the people who care about attacking
Dialogue: 0,0:11:10.98,0:11:14.71,Default,,0000,0000,0000,,systems to, to actually go through\Neverything. So people are making a
Dialogue: 0,0:11:14.71,0:11:17.52,Default,,0000,0000,0000,,selecttion, and maybe they just haven't\Nbothered looking at these PQCRYPTO
Dialogue: 0,0:11:17.52,0:11:22.07,Default,,0000,0000,0000,,submissions. So, if you want to actually\Nhave security review, it's really
Dialogue: 0,0:11:22.07,0:11:26.02,Default,,0000,0000,0000,,important to keep this denial of service\Neffect in mind, that the flood of
Dialogue: 0,0:11:26.02,0:11:30.57,Default,,0000,0000,0000,,submissions has to be small enough that it\Ncan be handled by the number of people who
Dialogue: 0,0:11:30.57,0:11:33.47,Default,,0000,0000,0000,,are looking at these submissions and\Nevaluating the security.
Dialogue: 0,0:11:33.47,0:11:37.20,Default,,0000,0000,0000,,TL: So, call for help, please join, please\Nbreak. Don't break ours.
Dialogue: 0,0:11:37.20,0:11:42.25,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NTL: Now, one thing which in this audience
Dialogue: 0,0:11:42.25,0:11:46.12,Default,,0000,0000,0000,,is a little funny, but in an normal\Nacademic conference where you talk to like
Dialogue: 0,0:11:46.12,0:11:50.73,Default,,0000,0000,0000,,40 or 100 people, we like, we actually\Nhave a lot of people now being interested
Dialogue: 0,0:11:50.73,0:11:54.42,Default,,0000,0000,0000,,in post-quantum cryptography. This was\Nthis year's conference on this, when Dan
Dialogue: 0,0:11:54.42,0:11:58.94,Default,,0000,0000,0000,,and I started this in 2006, we were\Nlooking at an audience of 40. This is 350
Dialogue: 0,0:11:58.94,0:12:04.46,Default,,0000,0000,0000,,people. Well, they would probably fit in\Nhere, but, well - for academics, this is
Dialogue: 0,0:12:04.46,0:12:08.01,Default,,0000,0000,0000,,big. There's a huge interest right now.\NThis was the combined conference together
Dialogue: 0,0:12:08.01,0:12:14.54,Default,,0000,0000,0000,,with a NIST workshop. And so people are\Nlooking. So that's the good news. There's
Dialogue: 0,0:12:14.54,0:12:17.62,Default,,0000,0000,0000,,more denial of service going on, I\Nmentioned RaCoSS already as one which is
Dialogue: 0,0:12:17.62,0:12:22.40,Default,,0000,0000,0000,,broken, but not withdrawn. Broken actually\Nthree different ways, where our last
Dialogue: 0,0:12:22.40,0:12:26.26,Default,,0000,0000,0000,,message to them was basically "abandon all\Nhope, this is not gonna work", but they
Dialogue: 0,0:12:26.26,0:12:31.06,Default,,0000,0000,0000,,keep on hoping. If I zoom in there, they\Nhave, they are on the way to publishing
Dialogue: 0,0:12:31.06,0:12:34.90,Default,,0000,0000,0000,,new parameters.\N{\i1}laughter{\i0}
Dialogue: 0,0:12:34.90,0:12:40.15,Default,,0000,0000,0000,,TL: When he was reading it out, actually\Nat the conference, he was saying "the keys
Dialogue: 0,0:12:40.15,0:12:46.21,Default,,0000,0000,0000,,and signature size may be several dozens\Nof terabytes". Well, there is some effect
Dialogue: 0,0:12:46.21,0:12:49.06,Default,,0000,0000,0000,,that we're most likely not going to break\Nit so easily, because when you're trying
Dialogue: 0,0:12:49.06,0:12:53.41,Default,,0000,0000,0000,,to download several terabytes of data, it\Nmight not reconnect.
Dialogue: 0,0:12:53.41,0:12:59.08,Default,,0000,0000,0000,,DJB: So, NIST is certainly aware of the\Nfact that there's just this denial of
Dialogue: 0,0:12:59.08,0:13:03.80,Default,,0000,0000,0000,,service on security analysis. And one of\Nthe ways that they tried to simplify the
Dialogue: 0,0:13:03.80,0:13:09.12,Default,,0000,0000,0000,,picture is, said, after their conference\Nthey put out this call saying, "all right,
Dialogue: 0,0:13:09.12,0:13:13.62,Default,,0000,0000,0000,,if you have similar submissions, see if\Nyou can merge them". And then hopefully
Dialogue: 0,0:13:13.62,0:13:16.76,Default,,0000,0000,0000,,you get something which is, you know,\Ngoing to be a combined submission that's
Dialogue: 0,0:13:16.76,0:13:20.93,Default,,0000,0000,0000,,easier for us to analyze than these two\Nseparate submissions in the first place.
Dialogue: 0,0:13:20.93,0:13:25.17,Default,,0000,0000,0000,,And they said this is an interesting\Nlittle guarantee. They said "NIST will
Dialogue: 0,0:13:25.17,0:13:29.77,Default,,0000,0000,0000,,accept a merged submission to the second\Nround if either of the submissions being
Dialogue: 0,0:13:29.77,0:13:34.21,Default,,0000,0000,0000,,merged would have been accepted". So you\Ncan imagine kind of attacking this if
Dialogue: 0,0:13:34.21,0:13:38.82,Default,,0000,0000,0000,,there's a strong submission and you have a\Nweak submission, like the strong one, they
Dialogue: 0,0:13:38.82,0:13:42.64,Default,,0000,0000,0000,,surely have to accept that, and then you\Nmerge your weak submission into the strong
Dialogue: 0,0:13:42.64,0:13:46.55,Default,,0000,0000,0000,,one if you can somehow convince the other\Nteam to do that, then your weak submission
Dialogue: 0,0:13:46.55,0:13:50.45,Default,,0000,0000,0000,,is also going to get into the the second\Nround, but NIST said "well, you should
Dialogue: 0,0:13:50.45,0:13:54.86,Default,,0000,0000,0000,,only merge submissions that are similar\Nand the merged submissions should be like
Dialogue: 0,0:13:54.86,0:13:59.80,Default,,0000,0000,0000,,a combination of the two original\Nsubmissions". So that sounds kind of
Dialogue: 0,0:13:59.80,0:14:04.09,Default,,0000,0000,0000,,reasonable, an example, while the first\Nannouncement of a merger - I don't think
Dialogue: 0,0:14:04.09,0:14:09.75,Default,,0000,0000,0000,,NIST said that you have to publicly\Nannounce - but HILA5 merged with Round2,
Dialogue: 0,0:14:09.75,0:14:15.02,Default,,0000,0000,0000,,and of course this was after the HILA5\Nattack and part of the merger was fixing
Dialogue: 0,0:14:15.02,0:14:20.50,Default,,0000,0000,0000,,the issue in that attack, and they formed\NRound5 and they said "Round5, this result
Dialogue: 0,0:14:20.50,0:14:25.22,Default,,0000,0000,0000,,of the merge, is a leading lattice-based\Ncandidate in terms of security, bandwidth
Dialogue: 0,0:14:25.22,0:14:30.51,Default,,0000,0000,0000,,and CPU performance". So, three weeks\Nlater, the security turned out to be kind
Dialogue: 0,0:14:30.51,0:14:35.73,Default,,0000,0000,0000,,of a problem. Mike Hamburg said that here\Nis a very strong reason to believe that
Dialogue: 0,0:14:35.73,0:14:43.32,Default,,0000,0000,0000,,decryption failures are much much more\Nlikely than what they claimed, and as a
Dialogue: 0,0:14:43.32,0:14:49.23,Default,,0000,0000,0000,,result of that, and they they accepted the\Nargument and said yeah, oops. As a result
Dialogue: 0,0:14:49.23,0:14:51.39,Default,,0000,0000,0000,,of that, like I mentioned before,\Ndecryption failures are something that
Dialogue: 0,0:14:51.39,0:14:57.08,Default,,0000,0000,0000,,attackers can use to break security. And\Nit's not that that a full attack was
Dialogue: 0,0:14:57.08,0:15:01.96,Default,,0000,0000,0000,,implemented, but it's pretty clear that\Nthe attack would work, and this is also an
Dialogue: 0,0:15:01.96,0:15:06.02,Default,,0000,0000,0000,,interesting attack because the mergers\Nwere supposed to be just taking, like take
Dialogue: 0,0:15:06.02,0:15:09.97,Default,,0000,0000,0000,,the best features of your two submissions,\Nthat you're merging. But this was a
Dialogue: 0,0:15:09.97,0:15:14.11,Default,,0000,0000,0000,,mistake. The vulnerability that Hamburg\Nexploited was a mistake that was not in
Dialogue: 0,0:15:14.11,0:15:19.10,Default,,0000,0000,0000,,either of the submissions that were being\Nput together. So there's some process of
Dialogue: 0,0:15:19.10,0:15:23.89,Default,,0000,0000,0000,,break and fix and merge, making more\Nmistakes, which get broken and then fixed
Dialogue: 0,0:15:23.89,0:15:28.49,Default,,0000,0000,0000,,and, well, what was the fix. They said,\N"oh, here's a proposed fix". They're
Dialogue: 0,0:15:28.49,0:15:32.02,Default,,0000,0000,0000,,"looking at the security proof\Nadjustments", there will be a Round5 real
Dialogue: 0,0:15:32.02,0:15:35.95,Default,,0000,0000,0000,,proposal, their actual merge will be in\Nthe future. I think now they have Round5a,
Dialogue: 0,0:15:35.95,0:15:42.80,Default,,0000,0000,0000,,Round5b and Round5c, where A is broken, B\Nis questionable, C is still not defined.
Dialogue: 0,0:15:42.80,0:15:48.99,Default,,0000,0000,0000,,What does a security proof, what does a\Nsecurity proof mean, if you have a
Dialogue: 0,0:15:48.99,0:15:52.78,Default,,0000,0000,0000,,security proof previously that they were\Nadjusting, and the security proof is for
Dialogue: 0,0:15:52.78,0:15:58.25,Default,,0000,0000,0000,,something that is not actually secure.\NVery strange. More merger announcements,
Dialogue: 0,0:15:58.25,0:16:01.69,Default,,0000,0000,0000,,post-quantum RSA encryption and post-\Nquantum RSA signatures merged to form
Dialogue: 0,0:16:01.69,0:16:05.83,Default,,0000,0000,0000,,post-quantum RSA, saying that that "is a\Nleading candidate in terms of depth of
Dialogue: 0,0:16:05.83,0:16:10.66,Default,,0000,0000,0000,,security analysis, amount of network\Ntraffic, and flexibility". For people not
Dialogue: 0,0:16:10.66,0:16:17.10,Default,,0000,0000,0000,,familiar with post-quantum RSA, this means\Nusing RSA with gigabyte or terabyte keys,
Dialogue: 0,0:16:17.10,0:16:20.11,Default,,0000,0000,0000,,which is leading in the amount of network\Ntraffic.
Dialogue: 0,0:16:20.11,0:16:21.63,Default,,0000,0000,0000,,{\i1}laughter{\i0}\N{\i1}applause{\i0}
Dialogue: 0,0:16:21.63,0:16:27.60,Default,,0000,0000,0000,,DJB: We want the internet to have as much\Ncryptography as possible.
Dialogue: 0,0:16:27.60,0:16:32.39,Default,,0000,0000,0000,,TL: Use more bandwidth.\NDJB: Yeah. Remember, you have, if you're
Dialogue: 0,0:16:32.39,0:16:38.62,Default,,0000,0000,0000,,measuring the amount of encrypted data on\Nyour network, this increases that. More
Dialogue: 0,0:16:38.62,0:16:42.04,Default,,0000,0000,0000,,mergers, more mergers, more mergers. Some\Nof these are kind of gluing submissions
Dialogue: 0,0:16:42.04,0:16:47.21,Default,,0000,0000,0000,,together in a way that does not simplify\Nthe, the security analysis. But this last
Dialogue: 0,0:16:47.21,0:16:50.84,Default,,0000,0000,0000,,one is a good example, I would say, of a\Nmerge entry. NTRU-HRSS and NTRUEncrypt,
Dialogue: 0,0:16:50.84,0:16:55.02,Default,,0000,0000,0000,,two of the NTRU-based submissions, they\Nactually put some thought into what they
Dialogue: 0,0:16:55.02,0:16:59.47,Default,,0000,0000,0000,,wanted to keep and what they wanted to\Nthrow away. And so analyzing the merge is
Dialogue: 0,0:16:59.47,0:17:06.52,Default,,0000,0000,0000,,easier than analyzing the, both of the\Ninitial submissions. After the November
Dialogue: 0,0:17:06.52,0:17:11.63,Default,,0000,0000,0000,,deadline for mergers, NIST said they will\Nannounce the second round candidates.
Dialogue: 0,0:17:11.63,0:17:16.54,Default,,0000,0000,0000,,Maybe it'll be, probably less than 30,\Nsome hints it'll be 25 or even 20,
Dialogue: 0,0:17:16.54,0:17:20.23,Default,,0000,0000,0000,,candidates, and maybe that's starting to\Nget down to a small enough flood that we
Dialogue: 0,0:17:20.23,0:17:25.40,Default,,0000,0000,0000,,can start seriously analyzing what's left.\NThey're going to announce that, I think on
Dialogue: 0,0:17:25.40,0:17:29.46,Default,,0000,0000,0000,,exactly January 10th they're scheduled to\Ndo that, and then a week after this
Dialogue: 0,0:17:29.46,0:17:33.54,Default,,0000,0000,0000,,announcement they said, "Well, the\Ngovernment might be shutting down, and in
Dialogue: 0,0:17:33.54,0:17:37.77,Default,,0000,0000,0000,,that case we're not allowed to do any\Nwork, so we're going to be completely
Dialogue: 0,0:17:37.77,0:17:42.61,Default,,0000,0000,0000,,silent in case of a shutdown". It's\Nimportant in the U.S. government, during
Dialogue: 0,0:17:42.61,0:17:48.39,Default,,0000,0000,0000,,shutdown there's a definition of essential\Npersonnel, like NSA, and non-essential
Dialogue: 0,0:17:48.39,0:17:51.26,Default,,0000,0000,0000,,personnel, like people protecting us\Nagainst NSA.
Dialogue: 0,0:17:51.26,0:17:54.10,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NDJB: - and only the essential personnel
Dialogue: 0,0:17:54.10,0:17:58.79,Default,,0000,0000,0000,,are allowed to do work. You know what else\Nis not allowed to do work? The backend
Dialogue: 0,0:17:58.79,0:18:06.96,Default,,0000,0000,0000,,database for NIST's web pages, which might\Nsound a little bit weird, although maybe
Dialogue: 0,0:18:06.96,0:18:11.85,Default,,0000,0000,0000,,they're paying Oracle for the backend\Ndatabase, and they have to turn off the
Dialogue: 0,0:18:11.85,0:18:16.29,Default,,0000,0000,0000,,payments to Oracle. I don't know what's\Ngoing on here, but if you look for the
Dialogue: 0,0:18:16.29,0:18:21.75,Default,,0000,0000,0000,,competition information, you can't find it\Non their web pages anymore. We're not
Dialogue: 0,0:18:21.75,0:18:25.11,Default,,0000,0000,0000,,quite sure how long this shutdown is going\Nto last. Of course, there are some people
Dialogue: 0,0:18:25.11,0:18:31.99,Default,,0000,0000,0000,,who say that this is not a problem,\Nbecause we can figure out without this
Dialogue: 0,0:18:31.99,0:18:35.76,Default,,0000,0000,0000,,competition how to protect ourselves\Nagainst quantum computers.
Dialogue: 0,0:18:35.76,0:18:38.100,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NTL: All right, now that we have aliens
Dialogue: 0,0:18:38.100,0:18:44.31,Default,,0000,0000,0000,,already, are quantum computers actually\Ncoming? Big question, we don't know. What
Dialogue: 0,0:18:44.31,0:18:48.90,Default,,0000,0000,0000,,we can monitor is progress in quantum\Ncomputing and just middle December, there
Dialogue: 0,0:18:48.90,0:18:54.11,Default,,0000,0000,0000,,was a news item from IonQ, which is a\Nsmall startup company, announcing their
Dialogue: 0,0:18:54.11,0:19:00.96,Default,,0000,0000,0000,,largest ever quantum computer based on ion\Ntraps. All the other quantum computers
Dialogue: 0,0:19:00.96,0:19:04.93,Default,,0000,0000,0000,,we've seen so far, which are of this size,\Nlike 40 to 70, they were using
Dialogue: 0,0:19:04.93,0:19:09.77,Default,,0000,0000,0000,,superconducting qubits. So, it is again a\Nrace between different technologies, but
Dialogue: 0,0:19:09.77,0:19:14.34,Default,,0000,0000,0000,,both of them are advancing, and there are\Nsome more which are growing. So, it looks
Dialogue: 0,0:19:14.34,0:19:18.12,Default,,0000,0000,0000,,like it's coming. Whenever I see that\Npicture like this, I'm reminded of a nice
Dialogue: 0,0:19:18.12,0:19:23.75,Default,,0000,0000,0000,,joke from a colleague of mine, Steven\NGalbraith.
Dialogue: 0,0:19:23.75,0:19:31.37,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NTL: Can you distinguish? Yep. So, with all
Dialogue: 0,0:19:31.37,0:19:34.59,Default,,0000,0000,0000,,these news coming up, the National Academy\Nof Sciences in the US has been
Dialogue: 0,0:19:34.59,0:19:38.06,Default,,0000,0000,0000,,interviewing people for the last about\Nyear and a half. So they got people in
Dialogue: 0,0:19:38.06,0:19:41.79,Default,,0000,0000,0000,,physics and engineering, building quantum\Ncomputers, people doing quantum
Dialogue: 0,0:19:41.79,0:19:45.88,Default,,0000,0000,0000,,algorithms, people doing quantum error-\Ncorrecting codes, and putting all of this
Dialogue: 0,0:19:45.88,0:19:51.18,Default,,0000,0000,0000,,together into a report, which just came\Nout, where they look into, well, what is
Dialogue: 0,0:19:51.18,0:19:56.11,Default,,0000,0000,0000,,the progress and what are the prospects.\NSo the first part of key findings, the
Dialogue: 0,0:19:56.11,0:20:01.76,Default,,0000,0000,0000,,first one is the good news, saying don't\Npanic. We do not expect that anything is
Dialogue: 0,0:20:01.76,0:20:07.94,Default,,0000,0000,0000,,going to happen in the next 10 years which\Nwill threaten RSA 2048 or similar, where I
Dialogue: 0,0:20:07.94,0:20:12.91,Default,,0000,0000,0000,,assume what they mean, well, elliptic\Ncurves, discrete logs on finite fields. So
Dialogue: 0,0:20:12.91,0:20:16.91,Default,,0000,0000,0000,,that's the good news. But they wouldn't\Nhave just one key finding, it actually
Dialogue: 0,0:20:16.91,0:20:24.02,Default,,0000,0000,0000,,goes on, two three, ten, by the time they\Nreach 10, I think this is panic. So that
Dialogue: 0,0:20:24.02,0:20:27.71,Default,,0000,0000,0000,,they say is, well, it takes forever to\Nroll out these things. The hazard of such
Dialogue: 0,0:20:27.71,0:20:34.60,Default,,0000,0000,0000,,a machine is high enough. And then, "the\Ndeployment of post-quantum cryptography is
Dialogue: 0,0:20:34.60,0:20:39.02,Default,,0000,0000,0000,,critical for minimizing the chances of a\Npotential security and privacy disaster".
Dialogue: 0,0:20:39.02,0:20:43.30,Default,,0000,0000,0000,,These are strong words from the National\NAcademy of Sciences.
Dialogue: 0,0:20:43.30,0:20:49.05,Default,,0000,0000,0000,,DJB: So, OK, can we deploy post-quantum\Ncryptography? Is it deployable? Well, some
Dialogue: 0,0:20:49.05,0:20:55.07,Default,,0000,0000,0000,,people would say we've already deployed\Nit, but maybe that doesn't include the
Dialogue: 0,0:20:55.07,0:20:59.46,Default,,0000,0000,0000,,NIST submissions, so let's look at the\Ndeployability of the NIST submissions. The
Dialogue: 0,0:20:59.46,0:21:04.22,Default,,0000,0000,0000,,main thing that matters for deployment in\Nmost applications, the main problem for
Dialogue: 0,0:21:04.22,0:21:09.99,Default,,0000,0000,0000,,post quantum cryptography, is the sizes.\NSo, here's a picture of the night sky over
Dialogue: 0,0:21:09.99,0:21:16.10,Default,,0000,0000,0000,,Leipzig. No, this is a picture of, on the\Nhorizontal axis is the size of your public
Dialogue: 0,0:21:16.10,0:21:20.14,Default,,0000,0000,0000,,key for a bunch of signature systems, not\Nall of the signature systems, for instance
Dialogue: 0,0:21:20.14,0:21:24.90,Default,,0000,0000,0000,,WalnutDSA, which is broken with a script\Nin the first five versions -
Dialogue: 0,0:21:24.90,0:21:28.10,Default,,0000,0000,0000,,TL: Post-quantum RSA is missing.\NDJB: Yeah, post-quantum RSA is also
Dialogue: 0,0:21:28.10,0:21:30.10,Default,,0000,0000,0000,,omitted from this, sorry.\NTL: It's kind of, of
Dialogue: 0,0:21:30.10,0:21:36.23,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NDJB: Yeah, that would be like, I'm one of
Dialogue: 0,0:21:36.23,0:21:38.35,Default,,0000,0000,0000,,the designers of post-quantum RSA by the\Nway.
Dialogue: 0,0:21:38.35,0:21:40.77,Default,,0000,0000,0000,,TL: I'm not.\NDJB: It's the future of cryptography.
Dialogue: 0,0:21:40.77,0:21:47.19,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NDJB: That was good. Yeah. So what you can
Dialogue: 0,0:21:47.19,0:21:51.45,Default,,0000,0000,0000,,see here is, for example this "gui"\Nsubmission, this has, you can get your
Dialogue: 0,0:21:51.45,0:21:56.73,Default,,0000,0000,0000,,your verticals, the signature size down to\Njust 32 bytes or 35 bytes, something like
Dialogue: 0,0:21:56.73,0:22:02.79,Default,,0000,0000,0000,,that, but you need something like 400,000\Nbytes in your public key. And then there's
Dialogue: 0,0:22:02.79,0:22:06.83,Default,,0000,0000,0000,,three different dots for gui. Those are\Nthree different security levels, and maybe
Dialogue: 0,0:22:06.83,0:22:10.26,Default,,0000,0000,0000,,all the different submissions here are\Nmaybe not exactly comparable on the
Dialogue: 0,0:22:10.26,0:22:13.63,Default,,0000,0000,0000,,security levels. It should be a three\Ndimensional graph, if we measure
Dialogue: 0,0:22:13.63,0:22:17.35,Default,,0000,0000,0000,,everything properly by exactly how secure\Nit is, which of course we're not quite
Dialogue: 0,0:22:17.35,0:22:21.75,Default,,0000,0000,0000,,sure about until there's been enough\Nsecurity analysis. You can see, various
Dialogue: 0,0:22:21.75,0:22:26.01,Default,,0000,0000,0000,,different trade-offs are possible, none of\Nwhich are down where we want to be with
Dialogue: 0,0:22:26.01,0:22:29.86,Default,,0000,0000,0000,,things like under 100 bytes for your\Npublic key and under 100 bytes for your
Dialogue: 0,0:22:29.86,0:22:33.89,Default,,0000,0000,0000,,signature, which is what we're used to\Nright now. That's what ecliptic curve
Dialogue: 0,0:22:33.89,0:22:39.06,Default,,0000,0000,0000,,crypto gives us, is signature sizes and\Npublic sizes, which are both below 100
Dialogue: 0,0:22:39.06,0:22:42.56,Default,,0000,0000,0000,,bytes. And that's something you can fit\Ninto your applications much more easily
Dialogue: 0,0:22:42.56,0:22:49.56,Default,,0000,0000,0000,,than, say, 100,000 byte public keys or\N10,000 byte signatures. There's various
Dialogue: 0,0:22:49.56,0:22:52.43,Default,,0000,0000,0000,,different trade-offs, and maybe your\Napplication can handle some of that, but
Dialogue: 0,0:22:52.43,0:22:57.31,Default,,0000,0000,0000,,there's nothing that's just really small,\Nwhich is what we're used to right now.
Dialogue: 0,0:22:57.31,0:23:02.49,Default,,0000,0000,0000,,Another more complicated graph. This is\Nfor encryption and showing more
Dialogue: 0,0:23:02.49,0:23:06.87,Default,,0000,0000,0000,,candidates. Well, there are more\Nencryption submissions. This is still not
Dialogue: 0,0:23:06.87,0:23:10.89,Default,,0000,0000,0000,,all of the encryption submissions, but a\Nrepresentative sample. And you can see
Dialogue: 0,0:23:10.89,0:23:18.22,Default,,0000,0000,0000,,that, well, there's still no really great\Nsizes here. The best in terms of sizes is
Dialogue: 0,0:23:18.22,0:23:24.21,Default,,0000,0000,0000,,"sike", supersingular isogeny keyexchange,\Nwhich is something like 400, little less
Dialogue: 0,0:23:24.21,0:23:28.02,Default,,0000,0000,0000,,than 400 bytes for the public key and for\Nthe cipher text, and then it starts
Dialogue: 0,0:23:28.02,0:23:32.31,Default,,0000,0000,0000,,getting bigger from there. And you get, on\Nthis graph you get things up to megabyte
Dialogue: 0,0:23:32.31,0:23:37.59,Default,,0000,0000,0000,,or bigger. You can get a little below\N300-400 bytes, you can get down to 100 or
Dialogue: 0,0:23:37.59,0:23:42.56,Default,,0000,0000,0000,,so bytes for the cipher text, as long as\Nyou are willing to accept a public key
Dialogue: 0,0:23:42.56,0:23:47.46,Default,,0000,0000,0000,,that's much, much bigger, with some of\Nthese code-based systems. And then just to
Dialogue: 0,0:23:47.46,0:23:50.89,Default,,0000,0000,0000,,zoom in on some of the smaller ones, you\Ncan start seeing where some different
Dialogue: 0,0:23:50.89,0:23:57.08,Default,,0000,0000,0000,,candidates are. This is everything which\Nis public key and cipher text below 1280
Dialogue: 0,0:23:57.08,0:24:02.81,Default,,0000,0000,0000,,bytes. And again, you see "sike" down\Nthere, a little below 400 bytes, and then
Dialogue: 0,0:24:02.81,0:24:07.29,Default,,0000,0000,0000,,some other possibilities. But well, what\Nare the security levels of these things?
Dialogue: 0,0:24:07.29,0:24:10.42,Default,,0000,0000,0000,,Could all of these be broken? There's not\Nactually that many of them, how many of
Dialogue: 0,0:24:10.42,0:24:14.34,Default,,0000,0000,0000,,these have actually been studied? It's\Nkind of scary. And again, much bigger
Dialogue: 0,0:24:14.34,0:24:19.90,Default,,0000,0000,0000,,sizes than we're used to in cryptography.\NTL: So, yes, size does matter.
Dialogue: 0,0:24:19.90,0:24:24.22,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NTL: So, Google and Cloudflare this year in
Dialogue: 0,0:24:24.22,0:24:27.73,Default,,0000,0000,0000,,April were saying, well, we don't really\Nknow what the outcome of this competition
Dialogue: 0,0:24:27.73,0:24:33.05,Default,,0000,0000,0000,,is going to be, but we have some\Ncategories of different crypto systems,
Dialogue: 0,0:24:33.05,0:24:38.08,Default,,0000,0000,0000,,and let's just send dummy packets of data\Nof respective sizes, and see what happens
Dialogue: 0,0:24:38.08,0:24:40.100,Default,,0000,0000,0000,,when we do this on the Internet. Now this\Nis Google and Cloudflare, so they they
Dialogue: 0,0:24:40.100,0:24:44.73,Default,,0000,0000,0000,,were doing this on the Chrome browser for\Nconnections that go through Cloudflare, so
Dialogue: 0,0:24:44.73,0:24:49.88,Default,,0000,0000,0000,,they could actually see from where it\Ncame, where it ended, whether it came
Dialogue: 0,0:24:49.88,0:24:54.46,Default,,0000,0000,0000,,back, whether it dropped. Dan mentioned\N"sike", so this is the one category of
Dialogue: 0,0:24:54.46,0:24:59.23,Default,,0000,0000,0000,,supersingular isogenies, those are just\N400 bytes. And that was pretty much fine,
Dialogue: 0,0:24:59.23,0:25:03.13,Default,,0000,0000,0000,,so when you look at the first column, you\Nhave a small latency increase. You also
Dialogue: 0,0:25:03.13,0:25:12.53,Default,,0000,0000,0000,,see the inaccuracy, that's a -0.2. So, the\Nnumbers are mostly correct. Then there is,
Dialogue: 0,0:25:12.53,0:25:15.39,Default,,0000,0000,0000,,in the lattices, this was the zoom-in what\NDan was showing, those are mostly
Dialogue: 0,0:25:15.39,0:25:19.32,Default,,0000,0000,0000,,something that could take a, we have\Nstructured lattices, those are around the
Dialogue: 0,0:25:19.32,0:25:27.16,Default,,0000,0000,0000,,MTU, so 1,100 something bytes. And that\Nwas, mostly worked, some small increases,
Dialogue: 0,0:25:27.16,0:25:30.84,Default,,0000,0000,0000,,but under 20 percent, so this is also\Nsomething we feel like, yes, you could
Dialogue: 0,0:25:30.84,0:25:35.100,Default,,0000,0000,0000,,actually deploy this on the Internet. Then\Na different category still within lattices
Dialogue: 0,0:25:35.100,0:25:40.65,Default,,0000,0000,0000,,are unstructured lattices. Those would\Ncome with 10 kilobytes of data for the
Dialogue: 0,0:25:40.65,0:25:46.45,Default,,0000,0000,0000,,public key. And there they just noticed\Nthat too many pages, including, like, top
Dialogue: 0,0:25:46.45,0:25:52.98,Default,,0000,0000,0000,,pages on Alexa 500, such as LinkedIn, were\Njust dropping. They tried, funny enough,
Dialogue: 0,0:25:52.98,0:25:59.09,Default,,0000,0000,0000,,9999, where fewer pages was dropping, so\N10K was worse than 9999, but even then
Dialogue: 0,0:25:59.09,0:26:03.36,Default,,0000,0000,0000,,LinkedIn was still dropping. And so they\Ndecreased it to a third, as basically a
Dialogue: 0,0:26:03.36,0:26:09.96,Default,,0000,0000,0000,,placeholder, measured with these 3300\Nbytes, and then scaled up by a factor of
Dialogue: 0,0:26:09.96,0:26:18.15,Default,,0000,0000,0000,,three. Now, those increases in the latency\Nis what they said, well, this is not
Dialogue: 0,0:26:18.15,0:26:20.83,Default,,0000,0000,0000,,acceptable. So then for the next\Nexperiments, they were only looking at
Dialogue: 0,0:26:20.83,0:26:27.41,Default,,0000,0000,0000,,isogenies and structured lattices.\NIsogenies are also special, not just being
Dialogue: 0,0:26:27.41,0:26:31.87,Default,,0000,0000,0000,,the smallest, but also being the slowest.\NWell okay, not absolutely the slowest, but
Dialogue: 0,0:26:31.87,0:26:38.66,Default,,0000,0000,0000,,it's the only system where the speed is\Nmuch more an issue than the size. And so
Dialogue: 0,0:26:38.66,0:26:41.22,Default,,0000,0000,0000,,despite Google having quite a few\Ncomputers, they were saying we can't
Dialogue: 0,0:26:41.22,0:26:45.89,Default,,0000,0000,0000,,actually use isogenies for the speed\Nreasons. Size would be awesome, but speed,
Dialogue: 0,0:26:45.89,0:26:52.24,Default,,0000,0000,0000,,not so sure. It's also a relatively recent\Nsystem, it's just in 2012. So maybe also
Dialogue: 0,0:26:52.24,0:26:56.29,Default,,0000,0000,0000,,it's a security question. So just now in\NDecember, they announced that they're
Dialogue: 0,0:26:56.29,0:26:59.79,Default,,0000,0000,0000,,actually building a new experiment, they\Nannounced which candidate they have
Dialogue: 0,0:26:59.79,0:27:02.90,Default,,0000,0000,0000,,chosen, NTRU-HRSS, which Dan just\Nmentioned was also one of the recent
Dialogue: 0,0:27:02.90,0:27:07.39,Default,,0000,0000,0000,,mergers. And so this is one of the\Nstructured lattices systems, designers are
Dialogue: 0,0:27:07.39,0:27:13.61,Default,,0000,0000,0000,,Andreas Hulsing, Joost Rijneveld, Peter\NSchwab and John Schanck. Great score for
Dialogue: 0,0:27:13.61,0:27:20.89,Default,,0000,0000,0000,,Eindhoven team, current professor, former\Nstudent, and then some collaborators. And
Dialogue: 0,0:27:20.89,0:27:25.38,Default,,0000,0000,0000,,so they're now building a system which is\Na combined elliptic curve, so that's the
Dialogue: 0,0:27:25.38,0:27:29.39,Default,,0000,0000,0000,,combined EC, that's combined elliptic\Ncurves and post-quantum. This is the
Dialogue: 0,0:27:29.39,0:27:33.67,Default,,0000,0000,0000,,second round running, and so this would\Ncome to some Internet browser near you
Dialogue: 0,0:27:33.67,0:27:39.34,Default,,0000,0000,0000,,soon. Another nice result, I mean this is\Nnot the only thing up there. The IETF this
Dialogue: 0,0:27:39.34,0:27:43.93,Default,,0000,0000,0000,,year finished standardizing XMSS, which is\Na hash based signature system. It's been
Dialogue: 0,0:27:43.93,0:27:46.43,Default,,0000,0000,0000,,in the making, down there you see the\Ntimeline, it's been in the making for
Dialogue: 0,0:27:46.43,0:27:51.10,Default,,0000,0000,0000,,three years. It's not really fast, but\Nit's also the first of its kind. This was
Dialogue: 0,0:27:51.10,0:27:55.92,Default,,0000,0000,0000,,the first time that IETF has published a\Npost-quantum RFC, request for comments,
Dialogue: 0,0:27:55.92,0:27:59.41,Default,,0000,0000,0000,,but that's basically their standards. And\Nso there's a lot of boilerplate text,
Dialogue: 0,0:27:59.41,0:28:03.28,Default,,0000,0000,0000,,which was developed in this thing, in the\Nprocess of making the standard, which is
Dialogue: 0,0:28:03.28,0:28:08.08,Default,,0000,0000,0000,,dealing with, yeah, post-quantum, quantum\Nattacks and so on, how you should handle
Dialogue: 0,0:28:08.08,0:28:13.21,Default,,0000,0000,0000,,it. XMSS is interesting. It's not one of\Nthe NIST submissions, because it doesn't
Dialogue: 0,0:28:13.21,0:28:16.70,Default,,0000,0000,0000,,satisfy the normal thing that you learn in\Nprimary school, what a signature should be
Dialogue: 0,0:28:16.70,0:28:22.83,Default,,0000,0000,0000,,doing. Signature you expect to have a\Npublic key. You use it to sign something,
Dialogue: 0,0:28:22.83,0:28:29.38,Default,,0000,0000,0000,,and then you have a signature. XMSS, you\Nhave a public key, you have a state. You
Dialogue: 0,0:28:29.38,0:28:33.69,Default,,0000,0000,0000,,get a message, you sign it, and you update\Nyour state. And if you ever forget to
Dialogue: 0,0:28:33.69,0:28:39.60,Default,,0000,0000,0000,,update your state, you will lose security.\NSo it's something which is not as cool as
Dialogue: 0,0:28:39.60,0:28:43.03,Default,,0000,0000,0000,,a normal signature scheme, but there are\Nalso many applications where you actually
Dialogue: 0,0:28:43.03,0:28:46.69,Default,,0000,0000,0000,,know how many signatures you've made. I\Nmean, if you're doing operating system
Dialogue: 0,0:28:46.69,0:28:52.29,Default,,0000,0000,0000,,updates, you better know how often you got\Nyour key out of the drawer and used it. So
Dialogue: 0,0:28:52.29,0:28:56.23,Default,,0000,0000,0000,,it is not impossible to use, but it might\Nnot be exactly what you want for your web
Dialogue: 0,0:28:56.23,0:28:59.70,Default,,0000,0000,0000,,applications.\NDJB: Good thing about XMSS is still, if
Dialogue: 0,0:28:59.70,0:29:04.20,Default,,0000,0000,0000,,you can count, then the size is much\Nsmaller than the signature systems that we
Dialogue: 0,0:29:04.20,0:29:09.55,Default,,0000,0000,0000,,were looking at before. Another size\Nadvantage, size advance is something
Dialogue: 0,0:29:09.55,0:29:13.24,Default,,0000,0000,0000,,called Glowstick. I should explain the\Nname. This is starting from a lattice
Dialogue: 0,0:29:13.24,0:29:18.78,Default,,0000,0000,0000,,submission called Saber, which is one of\Nthe unbroken ones, and Saber has a big
Dialogue: 0,0:29:18.78,0:29:23.40,Default,,0000,0000,0000,,version called FireSaber, high security\Nlevel, scaled up. It also has a small
Dialogue: 0,0:29:23.40,0:29:28.51,Default,,0000,0000,0000,,version called LightSaber.\N{\i1}laughter and groans{\i0}
Dialogue: 0,0:29:28.51,0:29:35.03,Default,,0000,0000,0000,,DJB: And this Glowstick is the even\Nsmaller version. It's like, let's scale it
Dialogue: 0,0:29:35.03,0:29:39.95,Default,,0000,0000,0000,,down as far as we can get that it's not\Nquite broken, and there's various
Dialogue: 0,0:29:39.95,0:29:45.30,Default,,0000,0000,0000,,technical details and it hasn't been\Nbroken in the months since it's been
Dialogue: 0,0:29:45.30,0:29:49.67,Default,,0000,0000,0000,,proposed, the six months or so, and it is\Ninteresting. I mean, it is something which
Dialogue: 0,0:29:49.67,0:29:54.04,Default,,0000,0000,0000,,is a good challenge. It's nice to have\Nthese scaled down problems, so we can try
Dialogue: 0,0:29:54.04,0:29:57.58,Default,,0000,0000,0000,,different ways of attacking these things\Nand people who like breaking stuff, it's
Dialogue: 0,0:29:57.58,0:30:01.34,Default,,0000,0000,0000,,good to have the simpler systems to\Npractice doing attacks, and that gives you
Dialogue: 0,0:30:01.34,0:30:04.08,Default,,0000,0000,0000,,some insight into what could work against\Nthe larger systems.
Dialogue: 0,0:30:04.08,0:30:09.78,Default,,0000,0000,0000,,TL: All right. So, since we're coming to\Nfunny names... Oh, no, since we're coming
Dialogue: 0,0:30:09.78,0:30:16.01,Default,,0000,0000,0000,,to sizes, why do we still care about big\Nsizes? I mean, people are scaling things
Dialogue: 0,0:30:16.01,0:30:19.76,Default,,0000,0000,0000,,down. Google says, oh, we don't like big\Nsizes. So why do people say post-quantum
Dialogue: 0,0:30:19.76,0:30:24.53,Default,,0000,0000,0000,,systems are bigger and we still care about\Nit? So one of the reasons is, well,
Dialogue: 0,0:30:24.53,0:30:28.78,Default,,0000,0000,0000,,highlighting McEliece here, which is our\Nsubmission in this competition, these have
Dialogue: 0,0:30:28.78,0:30:34.51,Default,,0000,0000,0000,,had a lot of analysis. So classic McEliece\Nis based on a system from 1978, basically
Dialogue: 0,0:30:34.51,0:30:39.52,Default,,0000,0000,0000,,unchanged except for some changes where we\Ncan really prove this is the same as that.
Dialogue: 0,0:30:39.52,0:30:43.66,Default,,0000,0000,0000,,It has one of the shorter ciphertext, just\N200 bytes, so that's actually kind of
Dialogue: 0,0:30:43.66,0:30:50.90,Default,,0000,0000,0000,,tolerable on the Internet, but a megabyte\Nof key. Key generation is also pretty
Dialogue: 0,0:30:50.90,0:30:55.61,Default,,0000,0000,0000,,slow, but then the, well, it's nowadays\Ncalled encapsulation, decapsulation
Dialogue: 0,0:30:55.61,0:30:59.29,Default,,0000,0000,0000,,because all you want is your AES key, you\Ndon't want to actually encrypt the
Dialogue: 0,0:30:59.29,0:31:04.96,Default,,0000,0000,0000,,message, but basic thing of encryption and\Ndecryption of that. So, nice system, very
Dialogue: 0,0:31:04.96,0:31:11.61,Default,,0000,0000,0000,,good history in security, pretty fast,\Npretty small, except for the public keys.
Dialogue: 0,0:31:11.61,0:31:18.91,Default,,0000,0000,0000,,It's like, "Grandma, why do you have so\Nbig keys?". Why are these keys so big? So
Dialogue: 0,0:31:18.91,0:31:21.63,Default,,0000,0000,0000,,one thing is, it's like a two dimensional\Nkey. We have this big matrix there, what
Dialogue: 0,0:31:21.63,0:31:28.36,Default,,0000,0000,0000,,you see on the left is an identity matrix.\NThis thing has about 7000 columns. It's
Dialogue: 0,0:31:28.36,0:31:33.48,Default,,0000,0000,0000,,like pretty long. It's only for, the\Nheight is n-k, which is just like thousand
Dialogue: 0,0:31:33.48,0:31:40.31,Default,,0000,0000,0000,,five hundred, so it's really long and\Nstretched. And so all of this part on your
Dialogue: 0,0:31:40.31,0:31:46.70,Default,,0000,0000,0000,,right-hand side, that part is random and\Nyou have to send that. You can of course,
Dialogue: 0,0:31:46.70,0:31:49.92,Default,,0000,0000,0000,,everybody remembers what an identity\Nmatrix looks like. You can forget about
Dialogue: 0,0:31:49.92,0:31:55.37,Default,,0000,0000,0000,,this one, but this one you have to send,\Nbecause the encryption works by the sender
Dialogue: 0,0:31:55.37,0:32:01.05,Default,,0000,0000,0000,,thinking, which of those around 7000\Ncolumn he wants to pick, and then just
Dialogue: 0,0:32:01.05,0:32:06.02,Default,,0000,0000,0000,,XORing them up, and for doing that, well,\Nyou need to have this big matrix.
Dialogue: 0,0:32:06.02,0:32:13.76,Default,,0000,0000,0000,,And if you calculate, well, 1547 times 5413 ,\Nthat's the part of the right matrix,
Dialogue: 0,0:32:13.76,0:32:19.10,Default,,0000,0000,0000,,you're getting to this one megabyte size.\NNow what are the issues with having big keys?
Dialogue: 0,0:32:19.10,0:32:24.91,Default,,0000,0000,0000,,It's bandwidth, but honestly, when\Nyou download, a picture it's also a megabyte.
Dialogue: 0,0:32:24.91,0:32:28.97,Default,,0000,0000,0000,,So, it might not be so bad. I mean, if\Nyou're on the German trains then you will
Dialogue: 0,0:32:28.97,0:32:31.19,Default,,0000,0000,0000,,hate it, but -\N{\i1}laughter{\i0}
Dialogue: 0,0:32:31.19,0:32:37.49,Default,,0000,0000,0000,,TL: - normally, elsewhere in the world or\Non your mobile, it's fine. Google was
Dialogue: 0,0:32:37.49,0:32:44.16,Default,,0000,0000,0000,,saying, we actually excluded some systems,\Nso they didn't experiment with classic
Dialogue: 0,0:32:44.16,0:32:48.92,Default,,0000,0000,0000,,McEliece, largest they looked at was\N10,000 kilobytes, and even then some dropped,
Dialogue: 0,0:32:48.92,0:32:53.51,Default,,0000,0000,0000,,and they said, well, some are too\Nlarge to be viable within TLS.
Dialogue: 0,0:32:53.51,0:32:59.51,Default,,0000,0000,0000,,So they just said, well, we don't do this. But\Nthen again, you have a secure system.
Dialogue: 0,0:32:59.51,0:33:04.30,Default,,0000,0000,0000,,You can just also design a secure protocol to\Ngo with it. We don't need to stick with TLS.
Dialogue: 0,0:33:04.30,0:33:09.25,Default,,0000,0000,0000,,But there is a real problem with\Nhaving a megabyte of key, because if your
Dialogue: 0,0:33:09.25,0:33:15.08,Default,,0000,0000,0000,,protocol assumes that the client generates\Nthis one megabyte and then just throws it
Dialogue: 0,0:33:15.08,0:33:19.74,Default,,0000,0000,0000,,at the server, and the server has to\Naccept one megabyte from every single
Dialogue: 0,0:33:19.74,0:33:24.45,Default,,0000,0000,0000,,client that is throwing a megabyte at it,\Nand then has to do something with it,
Dialogue: 0,0:33:24.45,0:33:28.42,Default,,0000,0000,0000,,well, this is really an invitation for a\Ndenial of service attack, because you're
Dialogue: 0,0:33:28.42,0:33:32.81,Default,,0000,0000,0000,,allocating memory on the server for doing\Nthese operations. The operations are pretty fast,
Dialogue: 0,0:33:32.81,0:33:39.68,Default,,0000,0000,0000,,it's just XORing 0s and 1s, but you have\Nto allocate 1 megabyte for each client.
Dialogue: 0,0:33:39.68,0:33:43.16,Default,,0000,0000,0000,,And so this is a problem, no matter what\Nthe protocol we designed,
Dialogue: 0,0:33:43.16,0:33:47.94,Default,,0000,0000,0000,,we have to deal with the possibility of\Ndenial of service attacks, or avoid them.
Dialogue: 0,0:33:47.94,0:33:53.26,Default,,0000,0000,0000,,So, can servers avoid\Nstoring these big keys? You want to XOR
Dialogue: 0,0:33:53.26,0:33:58.26,Default,,0000,0000,0000,,these columns, so one of the first\Nlimitation on small devices was saying,
Dialogue: 0,0:33:58.26,0:34:05.19,Default,,0000,0000,0000,,well, "I'm a very small device, but I can\Npick those positions and then, outside
Dialogue: 0,0:34:05.19,0:34:11.49,Default,,0000,0000,0000,,world, please be nice to me and spoon feed\Nme one column at a time". So the small
Dialogue: 0,0:34:11.49,0:34:18.33,Default,,0000,0000,0000,,device memorizes 1500 bits, not so big,\Nand then gets the next column.
Dialogue: 0,0:34:18.33,0:34:22.86,Default,,0000,0000,0000,,If it was selected, it XORs it in, if it wasn't\Nselected, well, it keeps the intermediate
Dialogue: 0,0:34:22.86,0:34:29.47,Default,,0000,0000,0000,,state. So this works. And at the end, you\Noutput the normal ciphertext. But what we
Dialogue: 0,0:34:29.47,0:34:33.90,Default,,0000,0000,0000,,have here is, we're operating in a\Nfriendly environment where we do not
Dialogue: 0,0:34:33.90,0:34:39.11,Default,,0000,0000,0000,,expect this outside world to do something\Nnasty to us, and also we have some memory.
Dialogue: 0,0:34:39.11,0:34:45.83,Default,,0000,0000,0000,,Now if we put this on the real Internet\Nand we don't want to have any state, so we
Dialogue: 0,0:34:45.83,0:34:49.26,Default,,0000,0000,0000,,cannot memorize these 1500, because, well,\Nwe don't know when the next column is
Dialogue: 0,0:34:49.26,0:34:56.04,Default,,0000,0000,0000,,going to come, so we output and send this\Nback to this client. That's not gonna work.
Dialogue: 0,0:34:56.04,0:35:03.12,Default,,0000,0000,0000,,When you tell the client, "Oh, this\Nis my current result", then the server
Dialogue: 0,0:35:03.12,0:35:07.87,Default,,0000,0000,0000,,gets the next column, maybe XORs it in,\Nmaybe not, sends it back to the client,
Dialogue: 0,0:35:07.87,0:35:11.98,Default,,0000,0000,0000,,anybody who is watching this traffic could\Nsee whether there was a change or there
Dialogue: 0,0:35:11.98,0:35:16.83,Default,,0000,0000,0000,,was no change. So this is not a way of\Ndealing with it. So what Dan and I have
Dialogue: 0,0:35:16.83,0:35:20.90,Default,,0000,0000,0000,,been busy with, and, well, I put 2018 with\Na question mark, we still have like three
Dialogue: 0,0:35:20.90,0:35:26.64,Default,,0000,0000,0000,,days, right? So we're working on this\Nsystem called McTiny, tiny because it's
Dialogue: 0,0:35:26.64,0:35:32.92,Default,,0000,0000,0000,,made for tiny web servers, where we assume\Nthat this web server is not allocating
Dialogue: 0,0:35:32.92,0:35:38.59,Default,,0000,0000,0000,,any per-client storage, any per-client state.\NAnd so, we again work with spoon feeding
Dialogue: 0,0:35:38.59,0:35:43.08,Default,,0000,0000,0000,,things, but we're making sure that\Neverything that the server gets and sends
Dialogue: 0,0:35:43.08,0:35:48.74,Default,,0000,0000,0000,,out is encrypted, is authenticated, there\Nis some stuff to avoid replay attacks, so
Dialogue: 0,0:35:48.74,0:35:53.79,Default,,0000,0000,0000,,that somebody can't just say, "oh, what if\NI change the column here or there". So all
Dialogue: 0,0:35:53.79,0:35:59.43,Default,,0000,0000,0000,,these things are encrypted, and what we do\Nis we use properties of doing these sums
Dialogue: 0,0:35:59.43,0:36:05.77,Default,,0000,0000,0000,,and pieces by chunking up this big matrix\Ninto chewable pieces that are small enough
Dialogue: 0,0:36:05.77,0:36:11.30,Default,,0000,0000,0000,,to fit in one MTU and still have some\Nspace for some cookies. So this is similar
Dialogue: 0,0:36:11.30,0:36:16.65,Default,,0000,0000,0000,,to normal uses of cookies, this is a\Ncookie, encrypted to the server, send to
Dialogue: 0,0:36:16.65,0:36:21.40,Default,,0000,0000,0000,,a client, you handle the storage,\Nand then client sends the next piece,
Dialogue: 0,0:36:21.40,0:36:26.78,Default,,0000,0000,0000,,sends the old cookie. Now, the cookie is\Nencrypted, but the way that the key is
Dialogue: 0,0:36:26.78,0:36:31.90,Default,,0000,0000,0000,,handled is the same for all clients. So\Nthere is no per-client storage of any
Dialogue: 0,0:36:31.90,0:36:36.02,Default,,0000,0000,0000,,keys. It's a symmetric key, it's pretty\Nsmall. So that's the one thing that the
Dialogue: 0,0:36:36.02,0:36:40.39,Default,,0000,0000,0000,,server remembers, and then it gets a\Npacket, it from this cookie part recovers
Dialogue: 0,0:36:40.39,0:36:44.55,Default,,0000,0000,0000,,all the, like, which columns to pick,\Nwhat's the intermediate result, and then
Dialogue: 0,0:36:44.55,0:36:50.47,Default,,0000,0000,0000,,does some computation, sends it back. So,\Nthe result of this is that we need several
Dialogue: 0,0:36:50.47,0:36:55.09,Default,,0000,0000,0000,,round trips, but there's absolutely no\Nper-client state on the server.
Dialogue: 0,0:36:55.09,0:37:00.85,Default,,0000,0000,0000,,DJB: Of course you could say, well, there\Nwere still all that bandwidth, and what if
Dialogue: 0,0:37:00.85,0:37:06.17,Default,,0000,0000,0000,,you do have bandwidth problems, but some\Npeople say that we're familiar with
Dialogue: 0,0:37:06.17,0:37:11.86,Default,,0000,0000,0000,,sending a lot of data around, so that's\Nreally not a big deal. Something else that
Dialogue: 0,0:37:11.86,0:37:15.67,Default,,0000,0000,0000,,could interfere with deployment is\Npatents. Now Tanja mentioned before that
Dialogue: 0,0:37:15.67,0:37:20.25,Default,,0000,0000,0000,,classic McEliece does not have patents,\Nbut what if somebody says, "I just don't
Dialogue: 0,0:37:20.25,0:37:23.24,Default,,0000,0000,0000,,want to handle the megabyte", or for\Nwhatever reason people want something
Dialogue: 0,0:37:23.24,0:37:28.75,Default,,0000,0000,0000,,smaller or there are signature questions.\NWell, we have a lot of information about
Dialogue: 0,0:37:28.75,0:37:33.37,Default,,0000,0000,0000,,some systems which are patented. The 18\Nsystems shown here, because NIST had as
Dialogue: 0,0:37:33.37,0:37:37.77,Default,,0000,0000,0000,,one of the rules for the competition that\Nyou had to deliver statements to them,
Dialogue: 0,0:37:37.77,0:37:42.60,Default,,0000,0000,0000,,signed by every member of the submission\Nteam, saying either "we do not have
Dialogue: 0,0:37:42.60,0:37:46.97,Default,,0000,0000,0000,,patents, patent applications on our\Nsubmission", or, "here's the patents,
Dialogue: 0,0:37:46.97,0:37:50.49,Default,,0000,0000,0000,,patent applications, here's their\Nnumbers". And so, OK, as a result of that
Dialogue: 0,0:37:50.49,0:37:53.55,Default,,0000,0000,0000,,and NIST, after checking they had a\Ncomplete pile of statements, put them
Dialogue: 0,0:37:53.55,0:37:57.51,Default,,0000,0000,0000,,online, so now we know that these are\Nexactly the 18 submissions where the
Dialogue: 0,0:37:57.51,0:38:02.11,Default,,0000,0000,0000,,submission teams claim patents on their\Nsubmissions, including for example Compact
Dialogue: 0,0:38:02.11,0:38:08.25,Default,,0000,0000,0000,,LWE and DME and WalnutDSA, which are\Nrapidly broken by scripts that are online.
Dialogue: 0,0:38:08.25,0:38:11.99,Default,,0000,0000,0000,,And RLCE-KEM, that one has half of the\Nparameters are broken, there's another
Dialogue: 0,0:38:11.99,0:38:16.10,Default,,0000,0000,0000,,half which are not broken. It's not that\Nthe patented submissions are somehow
Dialogue: 0,0:38:16.10,0:38:19.71,Default,,0000,0000,0000,,better than the rest of the submissions,\Nbut well, for some reason people think
Dialogue: 0,0:38:19.71,0:38:23.98,Default,,0000,0000,0000,,they can make money off of patents, and\Nmaybe they're not actually so wrong,
Dialogue: 0,0:38:23.98,0:38:28.43,Default,,0000,0000,0000,,because you can't just throw away these 18\Nsubmissions and say "that's the end of it".
Dialogue: 0,0:38:28.43,0:38:37.62,Default,,0000,0000,0000,,The problem is that there's some\Npatents which cover more submissions. Now,
Dialogue: 0,0:38:37.62,0:38:45.49,Default,,0000,0000,0000,,NIST does not require these submitters to\Nsay that, "here's which patents are, which
Dialogue: 0,0:38:45.49,0:38:50.84,Default,,0000,0000,0000,,submissions are covered by my patent". The\Nsubmitters are only required to say
Dialogue: 0,0:38:50.84,0:38:54.98,Default,,0000,0000,0000,,something about their own submissions, and\Nalso NIST has no way to say anything about
Dialogue: 0,0:38:54.98,0:38:58.78,Default,,0000,0000,0000,,whatever random patent trolls that are out\Nthere, that have not submitted anything.
Dialogue: 0,0:38:58.78,0:39:03.12,Default,,0000,0000,0000,,They can't impose any rules on that. I\Nmean, of course you can try doing patent
Dialogue: 0,0:39:03.12,0:39:07.43,Default,,0000,0000,0000,,searches, but you won't necessarily find\Nthings, for instance this patent. Nobody
Dialogue: 0,0:39:07.43,0:39:14.69,Default,,0000,0000,0000,,noticed until it was revealed in, well, by\Na member of some submission team, this
Dialogue: 0,0:39:14.69,0:39:19.78,Default,,0000,0000,0000,,patent was issued in 2015, at the top\Nthere, which might make you think, "oh, if
Dialogue: 0,0:39:19.78,0:39:23.37,Default,,0000,0000,0000,,something was published before 2015, it\Nwould be okay", and some submissions were
Dialogue: 0,0:39:23.37,0:39:28.37,Default,,0000,0000,0000,,published earlier. But what's important is\Nthe date down at the bottom here, which is
Dialogue: 0,0:39:28.37,0:39:33.66,Default,,0000,0000,0000,,the priority date of February 18th 2010.\NIf you look on Google Patents, one good
Dialogue: 0,0:39:33.66,0:39:38.00,Default,,0000,0000,0000,,thing is they put the priority date pretty\Nfar up, where you can easily see it. What
Dialogue: 0,0:39:38.00,0:39:43.14,Default,,0000,0000,0000,,this means is that, in order to be prior\Nart for this patent, well, you have to
Dialogue: 0,0:39:43.14,0:39:46.54,Default,,0000,0000,0000,,check what exactly they filed in 2010.\NThey might have made later changes,
Dialogue: 0,0:39:46.54,0:39:51.17,Default,,0000,0000,0000,,but the 2010 thing, assuming that has all \Nthe same stuff as the patent, which it's
Dialogue: 0,0:39:51.17,0:39:57.44,Default,,0000,0000,0000,,possible to find out, this, anything that\Nwas published after 2010 is not prior art
Dialogue: 0,0:39:57.44,0:40:02.11,Default,,0000,0000,0000,,for this. Now what's really scary about\Nthis patent, and I hope that really soon
Dialogue: 0,0:40:02.11,0:40:06.01,Default,,0000,0000,0000,,I'm gonna have analysis online of which\Nsubmissions are covered by which patents
Dialogue: 0,0:40:06.01,0:40:10.31,Default,,0000,0000,0000,,of all the patents I've seen. This one is\Nby far the scariest, because this one
Dialogue: 0,0:40:10.31,0:40:15.45,Default,,0000,0000,0000,,covers a whole bunch of submissions. This\None covers basically every submission
Dialogue: 0,0:40:15.45,0:40:21.44,Default,,0000,0000,0000,,which is using what's called the LPR\Ncryptosystem, a ring-LWE-lattice-based
Dialogue: 0,0:40:21.44,0:40:25.71,Default,,0000,0000,0000,,crypto system. This is a very popular type\Nof lattice-based crypto system, which was
Dialogue: 0,0:40:25.71,0:40:35.88,Default,,0000,0000,0000,,published by L, P, and R, Lyubashevsky,\NPeikert, and Regev, in May 2010, which is
Dialogue: 0,0:40:35.88,0:40:43.93,Default,,0000,0000,0000,,after this patent application was filed.\NNow, there was a talk in April which had
Dialogue: 0,0:40:43.93,0:40:48.64,Default,,0000,0000,0000,,the same stuff from LPR, and it seems like\Nthere might even have been a talk in
Dialogue: 0,0:40:48.64,0:40:54.43,Default,,0000,0000,0000,,January from LPR, but they didn't put the\Nslides online, and then, well, it starts
Dialogue: 0,0:40:54.43,0:40:57.100,Default,,0000,0000,0000,,getting into interesting questions of\Npatent law. This looks like a very
Dialogue: 0,0:40:57.100,0:41:01.84,Default,,0000,0000,0000,,strong patent, covering a whole lot of\Nsubmissions, and there's more cases,
Dialogue: 0,0:41:01.84,0:41:05.97,Default,,0000,0000,0000,,there's a whole company called ISARA that\Nis specializing in planting landmines,
Dialogue: 0,0:41:05.97,0:41:10.24,Default,,0000,0000,0000,,patent landmines, around things that other\Npeople are doing, sometimes on things that
Dialogue: 0,0:41:10.24,0:41:14.27,Default,,0000,0000,0000,,other people have already published, and\Nthen you get a court fight about it. This
Dialogue: 0,0:41:14.27,0:41:17.92,Default,,0000,0000,0000,,is gonna be a problem; it's something we\Nreally have to watch out for, is what is
Dialogue: 0,0:41:17.92,0:41:24.25,Default,,0000,0000,0000,,patented, and again, I hope to be sometime\Nsoon done with some patent analysis.
Dialogue: 0,0:41:24.25,0:41:28.62,Default,,0000,0000,0000,,Of course, some people would say that we\Ndon't have to worry about patents as long
Dialogue: 0,0:41:28.62,0:41:32.34,Default,,0000,0000,0000,,as we find something that we can deploy,\Nthat somebody tries deploying it
Dialogue: 0,0:41:32.34,0:41:36.07,Default,,0000,0000,0000,,and they don't get sued.\NTL: Not sure that's going to be deployed
Dialogue: 0,0:41:36.07,0:41:44.94,Default,,0000,0000,0000,,anytime soon. I mean, 95 out of 3000, {\i1}Laughter{\i0}\Nokay. All right. Funny names, I said.
Dialogue: 0,0:41:44.94,0:41:55.17,Default,,0000,0000,0000,,So what do you see here? Can anybody read\Nphonetics? Yeah? "si-said". Okay, so,
Dialogue: 0,0:41:55.17,0:42:02.04,Default,,0000,0000,0000,,seaside. Now, CSIDH is what you really\Nalways wanted. CSIDH is an efficient post-
Dialogue: 0,0:42:02.04,0:42:06.35,Default,,0000,0000,0000,,quantum commutative group action. Did you\Nknow that you wanted a commutative group
Dialogue: 0,0:42:06.35,0:42:14.12,Default,,0000,0000,0000,,action? Actually, you did. So, what all\Npeople ask me is, like, "I'm using Diffie-
Dialogue: 0,0:42:14.12,0:42:18.61,Default,,0000,0000,0000,,Hellman these days. What can you give me\Nin the post-quantum world?". And then it
Dialogue: 0,0:42:18.61,0:42:25.44,Default,,0000,0000,0000,,depends a lot on how you define Diffie-\NHellman. Some features that we come to use
Dialogue: 0,0:42:25.44,0:42:30.54,Default,,0000,0000,0000,,from Diffie-Hellman are that, well, you\Npublish a public key, I publish a public key,
Dialogue: 0,0:42:30.54,0:42:37.43,Default,,0000,0000,0000,,other people publish public keys, and\Nwe can reuse them. Kind of nice. Also, we
Dialogue: 0,0:42:37.43,0:42:40.85,Default,,0000,0000,0000,,don't have to talk to each other. We can\Njust look up the other public key on the
Dialogue: 0,0:42:40.85,0:42:45.83,Default,,0000,0000,0000,,phone book, have a shared key, and start\Nusing that one. And if I send you
Dialogue: 0,0:42:45.83,0:42:51.34,Default,,0000,0000,0000,,something encrypted with our shared public\Nkeys, like, combined thing of this, then
Dialogue: 0,0:42:51.34,0:42:55.92,Default,,0000,0000,0000,,you will be able to decrypt this. There\Nare some nice other features; you can
Dialogue: 0,0:42:55.92,0:43:00.98,Default,,0000,0000,0000,,blind things, you can like take your g to\Nthe a and then multiply, compute in the
Dialogue: 0,0:43:00.98,0:43:06.30,Default,,0000,0000,0000,,exponent times r, so put some blinding\Nfactors there, and there is no difference
Dialogue: 0,0:43:06.30,0:43:11.58,Default,,0000,0000,0000,,whether I'm the initiator or I am the\Nresponder in this. We don't have this
Dialogue: 0,0:43:11.58,0:43:15.04,Default,,0000,0000,0000,,anywhere else in post quantum\Ncryptography. All the systems that you see
Dialogue: 0,0:43:15.04,0:43:19.57,Default,,0000,0000,0000,,for NIST submissions make a difference\Nbetween are you the sender, are you the
Dialogue: 0,0:43:19.57,0:43:25.62,Default,,0000,0000,0000,,responder. So this is the first efficient\Npost-quantum, well, Diffie-Hellman-like
Dialogue: 0,0:43:25.62,0:43:32.27,Default,,0000,0000,0000,,thing, which, well, by fancy math called\Ncommutative group action. So, if you are a
Dialogue: 0,0:43:32.27,0:43:35.34,Default,,0000,0000,0000,,user, you don't want to know all the\Ndetails. I'm not going to give an entire
Dialogue: 0,0:43:35.34,0:43:40.61,Default,,0000,0000,0000,,talk about this, unless, maybe next year.\NWhat you see exposed to you is just one
Dialogue: 0,0:43:40.61,0:43:44.41,Default,,0000,0000,0000,,single finite field element. So there is\Nsome fixed prime, that all the people in
Dialogue: 0,0:43:44.41,0:43:48.30,Default,,0000,0000,0000,,the system know, and then everybody's\Npublic key is just one single field
Dialogue: 0,0:43:48.30,0:43:55.14,Default,,0000,0000,0000,,element. So Alice computes her field\Nelement, Bob computes his field element,
Dialogue: 0,0:43:55.14,0:43:59.34,Default,,0000,0000,0000,,they post these somewhere, and then\Nsometime later, years later, maybe if
Dialogue: 0,0:43:59.34,0:44:03.94,Default,,0000,0000,0000,,quantum computers are built, they find\Neach other, they compute their shared
Dialogue: 0,0:44:03.94,0:44:08.99,Default,,0000,0000,0000,,public key, they combine the shared, the\Npublic keys into their shared secret key,
Dialogue: 0,0:44:08.99,0:44:13.63,Default,,0000,0000,0000,,sorry, and then they have the shared\Nsecret. Now, a little bit of the math
Dialogue: 0,0:44:13.63,0:44:18.48,Default,,0000,0000,0000,,behind this, A actually appears in some\Nform there, so this is one of the
Dialogue: 0,0:44:18.48,0:44:20.72,Default,,0000,0000,0000,,elliptic curves that we've been talking \Nabout in, gosh,
Dialogue: 0,0:44:20.72,0:44:25.28,Default,,0000,0000,0000,,when was this, 2013 or so. No, 14 at least.\NDJB: 14.
Dialogue: 0,0:44:25.28,0:44:34.13,Default,,0000,0000,0000,,TL: So there's EA: y^2 = x^3, and then A,\Nthis public key A, x^2 + x, and that what
Dialogue: 0,0:44:34.13,0:44:41.41,Default,,0000,0000,0000,,the computation is to go from one key to\Nanother key is using an isogeny, same
Dialogue: 0,0:44:41.41,0:44:45.17,Default,,0000,0000,0000,,isogeny kind of thing that you heard in\Nsike before, it's a math object that just
Dialogue: 0,0:44:45.17,0:44:50.04,Default,,0000,0000,0000,,means you move from one elliptic curve to\Nanother elliptic curve. If somebody tells
Dialogue: 0,0:44:50.04,0:44:54.76,Default,,0000,0000,0000,,you to implement this, what you need to\Nget doing is, well, take this prime p,
Dialogue: 0,0:44:54.76,0:45:01.06,Default,,0000,0000,0000,,compute modulo p for addition,\Nmultiplications and divisions, out of
Dialogue: 0,0:45:01.06,0:45:06.76,Default,,0000,0000,0000,,those you for instance build the curve\Noperations, and then some more operations
Dialogue: 0,0:45:06.76,0:45:10.96,Default,,0000,0000,0000,,which computes an isogeny, but all of\Nthose are just combined from those things.
Dialogue: 0,0:45:10.96,0:45:15.87,Default,,0000,0000,0000,,So there's nothing particularly scary\Nbehind it, except for, well, we came up
Dialogue: 0,0:45:15.87,0:45:24.90,Default,,0000,0000,0000,,with this thing in January 2018 at this\Nlovely beach. Was great there, but please
Dialogue: 0,0:45:24.90,0:45:29.32,Default,,0000,0000,0000,,don't use it yet. Experiment with it all\Nyou want, but this has not had enough
Dialogue: 0,0:45:29.32,0:45:34.89,Default,,0000,0000,0000,,analysis. But another reason why you might\Nwant this is security, key sizes and so on.
Dialogue: 0,0:45:34.89,0:45:41.75,Default,,0000,0000,0000,,So, what are we looking at? First of\Nall, how many keys are there? So how big
Dialogue: 0,0:45:41.75,0:45:49.36,Default,,0000,0000,0000,,do we have to look at this p? When you\Nhave fixed your prime p, say n bits, then
Dialogue: 0,0:45:49.36,0:45:55.82,Default,,0000,0000,0000,,there are square root of p, so 2 to the n\Nover 2, many such curves. So these are the
Dialogue: 0,0:45:55.82,0:46:00.79,Default,,0000,0000,0000,,numbers of public keys. And then, similar\Nto how the elliptic curve discrete log,
Dialogue: 0,0:46:00.79,0:46:05.54,Default,,0000,0000,0000,,kind of meet-in-the-middle attacks, work,\Nso basically smart bruce force search, you
Dialogue: 0,0:46:05.54,0:46:11.14,Default,,0000,0000,0000,,get a square root of the number of keys as\Nyour security. So if you have square root
Dialogue: 0,0:46:11.14,0:46:17.94,Default,,0000,0000,0000,,of p many keys, it takes your fourth root\Nof p time to find out what Alice's key is.
Dialogue: 0,0:46:17.94,0:46:23.22,Default,,0000,0000,0000,,So if you want 128 bit security, you have\Nto choose your prime p four times as many
Dialogue: 0,0:46:23.22,0:46:30.57,Default,,0000,0000,0000,,bits, so a 512 bit prime. But this is a\Ntalk on post-quantum cryptography.
Dialogue: 0,0:46:30.57,0:46:36.31,Default,,0000,0000,0000,,So where do we stand there? Elliptic curves\Nwould be totally broken. Nice enough for
Dialogue: 0,0:46:36.31,0:46:40.55,Default,,0000,0000,0000,,isogenies, we don't have any complete\Nbreak. There are some sub-exponential
Dialogue: 0,0:46:40.55,0:46:46.49,Default,,0000,0000,0000,,attacks, so doesn't have full exponential\Nsecurity as we maybe would like to have,
Dialogue: 0,0:46:46.49,0:46:49.83,Default,,0000,0000,0000,,on the other hand, with RSA and finite\Nfield Diffie-Hellman, we have been dealing
Dialogue: 0,0:46:49.83,0:46:53.50,Default,,0000,0000,0000,,with the growth of keys, with sub-\Nexponentil attacks, so this is something
Dialogue: 0,0:46:53.50,0:46:57.91,Default,,0000,0000,0000,,we're familiar with. It doesn't kill\Nthings, but you look at the literature,
Dialogue: 0,0:46:57.91,0:47:01.47,Default,,0000,0000,0000,,it's mostly asymptotics, so we and also\Nsome others have been looking into
Dialogue: 0,0:47:01.47,0:47:06.10,Default,,0000,0000,0000,,details. I think our analysis, which we\Nhave at quantum.isogeny.org, is the most
Dialogue: 0,0:47:06.10,0:47:11.05,Default,,0000,0000,0000,,detailed one, looking into, like, what\Nactual security you get against somebody
Dialogue: 0,0:47:11.05,0:47:16.36,Default,,0000,0000,0000,,with a really really big quantum computer.\NNow with elliptic curves, you'll hopefully
Dialogue: 0,0:47:16.36,0:47:20.05,Default,,0000,0000,0000,,have also learned that you must always\Nvalidate, you need to get a point,
Dialogue: 0,0:47:20.05,0:47:23.42,Default,,0000,0000,0000,,somebody says "oh, this is my public key",\Nthe first thing you do is check, is this
Dialogue: 0,0:47:23.42,0:47:29.04,Default,,0000,0000,0000,,thing on the curve, does it have the right\Norder? Same thing for isogeny-based
Dialogue: 0,0:47:29.04,0:47:32.83,Default,,0000,0000,0000,,crypto, for CSIDH you have a very quick\Ncheck, you check that this curve has the
Dialogue: 0,0:47:32.83,0:47:35.80,Default,,0000,0000,0000,,number of points, you know what it is, you\Ndon't even need to do full point counting,
Dialogue: 0,0:47:35.80,0:47:42.15,Default,,0000,0000,0000,,you just take a point, do some scalar\Nmultiplications, and you check it. This is
Dialogue: 0,0:47:42.15,0:47:46.67,Default,,0000,0000,0000,,another thing that we've gotten totally\Nused to doing. This is another thing that
Dialogue: 0,0:47:46.67,0:47:51.09,Default,,0000,0000,0000,,is really really really hard for most\Npost-quantum systems. Most post-quantum
Dialogue: 0,0:47:51.09,0:47:55.84,Default,,0000,0000,0000,,systems you add another proof to it, so\Ntypically when you encrypt to somebody's
Dialogue: 0,0:47:55.84,0:47:59.97,Default,,0000,0000,0000,,key and you're sending something which\Nlooks like a key, you reveal all the
Dialogue: 0,0:47:59.97,0:48:05.23,Default,,0000,0000,0000,,secrets in there, that's why you can't\Nreuse it, or you have to do a big zero
Dialogue: 0,0:48:05.23,0:48:09.76,Default,,0000,0000,0000,,knowledge proof to prove that you actually\Ngenerated this thing properly. With CSIDH,
Dialogue: 0,0:48:09.76,0:48:15.68,Default,,0000,0000,0000,,it's just there. All you need to do is\Ncheck if it's a valid curve, and you're done.
Dialogue: 0,0:48:15.68,0:48:21.52,Default,,0000,0000,0000,,Size it's also pretty neat. So, 32\Nbytes for the secret key, 64 bytes.
Dialogue: 0,0:48:21.52,0:48:26.14,Default,,0000,0000,0000,,So just twice as large as normal elliptic\Ncurves, that is really like bottom-left
Dialogue: 0,0:48:26.14,0:48:32.20,Default,,0000,0000,0000,,corner of Dan's graph where there was\Nnothing, so CSIDH does fill a big gap, a
Dialogue: 0,0:48:32.20,0:48:38.21,Default,,0000,0000,0000,,big gap, but a small key, there with\Nsomething, which pre-quantum has at least
Dialogue: 0,0:48:38.21,0:48:43.42,Default,,0000,0000,0000,,128 bit security and post-quantum, so what\NNIST was asking for is comparisons with
Dialogue: 0,0:48:43.42,0:48:48.57,Default,,0000,0000,0000,,AES-128 and then you look at, like, how\Nbig are the sizes, how big are the quantum
Dialogue: 0,0:48:48.57,0:48:52.80,Default,,0000,0000,0000,,computers and so on. And we think that\NCSIDH-512, to the best of our knowledge,
Dialogue: 0,0:48:52.80,0:48:57.99,Default,,0000,0000,0000,,based on the latest analysis, will be as\Nsecure as that. There is some code written
Dialogue: 0,0:48:57.99,0:49:09.04,Default,,0000,0000,0000,,by Lorenz, somewhere? Ah, Lorenz. Yay.\NThis is on Skylake. Your mileage may vary.
Dialogue: 0,0:49:09.04,0:49:14.55,Default,,0000,0000,0000,,This is a, it's not a super-quick hack,\Nbut it's not deployment code. So this is
Dialogue: 0,0:49:14.55,0:49:17.35,Default,,0000,0000,0000,,not yet constant time, there are some\Nothers who've been working on constant
Dialogue: 0,0:49:17.35,0:49:23.77,Default,,0000,0000,0000,,time, it makes it about three times\Nslower. It is similar to sike in that it's
Dialogue: 0,0:49:23.77,0:49:28.99,Default,,0000,0000,0000,,really nice small keys, but somewhat slow.\NOn the other hand, this is still very new,
Dialogue: 0,0:49:28.99,0:49:32.33,Default,,0000,0000,0000,,it's just from January. So we're still\Nfiguring out ways to make it faster,
Dialogue: 0,0:49:32.33,0:49:36.18,Default,,0000,0000,0000,,whereas, well, sike has been doing a lot\Nof work getting to the speed that they
Dialogue: 0,0:49:36.18,0:49:39.94,Default,,0000,0000,0000,,have now. So there's hope that this will\Nget faster, and there's some hope it will
Dialogue: 0,0:49:39.94,0:49:45.24,Default,,0000,0000,0000,,remain unbroken until next year, but,\Nwell, I'm not sure yet where I'd put my
Dialogue: 0,0:49:45.24,0:49:48.74,Default,,0000,0000,0000,,money, at the, at this moment I think\Nactually CSIDH has a better chance than
Dialogue: 0,0:49:48.74,0:49:53.69,Default,,0000,0000,0000,,sike of surviving, but who knows. Don't\Nuse it for anything yet.
Dialogue: 0,0:49:53.69,0:49:56.84,Default,,0000,0000,0000,,DJB: Speaking of broke, there's a lot of\Npeople who are investing
Dialogue: 0,0:49:56.84,0:50:00.82,Default,,0000,0000,0000,,in crypto currencies, -\N{\i1}laughter{\i0}
Dialogue: 0,0:50:00.82,0:50:06.36,Default,,0000,0000,0000,,DJB: - and I think, I think it's Nick\NMathewson's fault, this whole quantum-
Dialogue: 0,0:50:06.36,0:50:10.38,Default,,0000,0000,0000,,cyber blockchain idea, if you know\Nsomething earlier than 2016, well anyway,
Dialogue: 0,0:50:10.38,0:50:14.20,Default,,0000,0000,0000,,there's variations of it since then, like\Nquantum AI blockchain, apparently you can
Dialogue: 0,0:50:14.20,0:50:20.06,Default,,0000,0000,0000,,buy the t-shirt. We have about 10 minutes\Nleft, so I'd like to finish things off
Dialogue: 0,0:50:20.06,0:50:25.95,Default,,0000,0000,0000,,with some comments on software. Now this\Nis looking back at 40 years of public key
Dialogue: 0,0:50:25.95,0:50:32.09,Default,,0000,0000,0000,,cryptography, well RSA was from '77 or so,\Nthe McEliece cryptosystem from '78, and
Dialogue: 0,0:50:32.09,0:50:37.56,Default,,0000,0000,0000,,then, well, here's some, some schematics\Nof what the software quality has been in
Dialogue: 0,0:50:37.56,0:50:42.05,Default,,0000,0000,0000,,cryptography, on a scale of "good", "bad",\N"terrible", and "horrifying". 1978, I
Dialogue: 0,0:50:42.05,0:50:46.28,Default,,0000,0000,0000,,don't actually know, I haven't seen\Nsoftware from back then. By 1988, it was
Dialogue: 0,0:50:46.28,0:50:51.23,Default,,0000,0000,0000,,clear that the software quality was\Nhorrifying. By 1998, it had moved up to
Dialogue: 0,0:50:51.23,0:50:56.10,Default,,0000,0000,0000,,terrible. By 2008, it moved up to bad. And\Nby 2018, it has jumped back down to
Dialogue: 0,0:50:56.10,0:51:05.50,Default,,0000,0000,0000,,horrifying.\N{\i1}laughter and applause{\i0}
Dialogue: 0,0:51:05.50,0:51:09.51,Default,,0000,0000,0000,,DJB: And of course a major contributor to\Nthis is all of these NIST submissions,
Dialogue: 0,0:51:09.51,0:51:14.59,Default,,0000,0000,0000,,which have code written by mathematicians,\Nwho barely can implement anything and
Dialogue: 0,0:51:14.59,0:51:18.33,Default,,0000,0000,0000,,certainly don't have good code quality.\NThere's occasional submission teams that
Dialogue: 0,0:51:18.33,0:51:23.08,Default,,0000,0000,0000,,have people who can write code, but in\Ngeneral, if you, well, for a good time,
Dialogue: 0,0:51:23.08,0:51:24.65,Default,,0000,0000,0000,,pick up a random -\NTL: McEliece is fine!
Dialogue: 0,0:51:24.65,0:51:28.14,Default,,0000,0000,0000,,DJB: Yeah, the classic McEliece code is\Nfine. There's other submissions where the
Dialogue: 0,0:51:28.14,0:51:34.01,Default,,0000,0000,0000,,code is is fine, but if you just take a\Nrandom submission and look at the code,
Dialogue: 0,0:51:34.01,0:51:42.77,Default,,0000,0000,0000,,it's, well, interesting. If you would like\Nto find out where the software is and
Dialogue: 0,0:51:42.77,0:51:45.18,Default,,0000,0000,0000,,download it.\N{\i1}laughter{\i0}
Dialogue: 0,0:51:45.18,0:51:50.34,Default,,0000,0000,0000,,DJB: Yeah, NIST doesn't work very well. I\Ndid look, archive.org has, like, you
Dialogue: 0,0:51:50.34,0:51:55.59,Default,,0000,0000,0000,,search for "NIST round one" on DuckDuckGo,\Nand the top link is to the NIST page, and
Dialogue: 0,0:51:55.59,0:52:00.20,Default,,0000,0000,0000,,then you take the URL for that, put it\Ninto archive.org, and I tried a few of the
Dialogue: 0,0:52:00.20,0:52:04.03,Default,,0000,0000,0000,,submissions and the zip files that NIST\Nprepared with the specifications and the
Dialogue: 0,0:52:04.03,0:52:07.92,Default,,0000,0000,0000,,code, those are available from\Narchive.org. I guess they got most or all
Dialogue: 0,0:52:07.92,0:52:12.36,Default,,0000,0000,0000,,of them. You can also look for more than\Nhalf the submissions, there are upstream
Dialogue: 0,0:52:12.36,0:52:17.57,Default,,0000,0000,0000,,websites with newer code. NIST has not\Nupdated the code, but lots of submissions,
Dialogue: 0,0:52:17.57,0:52:22.99,Default,,0000,0000,0000,,the submission teams have, lots of the\Nfastest code, and even some faster while
Dialogue: 0,0:52:22.99,0:52:27.21,Default,,0000,0000,0000,,improved code, is available in our\NSUPERCOP benchmarking framework, so this
Dialogue: 0,0:52:27.21,0:52:30.51,Default,,0000,0000,0000,,is the system for unified performance\Nevaluation related to cryptographic
Dialogue: 0,0:52:30.51,0:52:39.36,Default,,0000,0000,0000,,operations and primitives, bench.cr.yp.to,\Nand this one has, well, 170 primitives
Dialogue: 0,0:52:39.36,0:52:45.75,Default,,0000,0000,0000,,from 40 of the 69 submissions. Might have\Naccidentally left out all of the patented
Dialogue: 0,0:52:45.75,0:52:50.80,Default,,0000,0000,0000,,submissions, well, the SUPERCOP policy is\Nanybody who sends us code to put in, we'll
Dialogue: 0,0:52:50.80,0:52:54.73,Default,,0000,0000,0000,,benchmark it, it doesn't have to be\Nunpatented, it doesn't have to be secure,
Dialogue: 0,0:52:54.73,0:53:00.35,Default,,0000,0000,0000,,we benchmark MD5, we benchmark RSA-512.\NBut anyways, there's 40 submissions where
Dialogue: 0,0:53:00.35,0:53:04.51,Default,,0000,0000,0000,,code is in there, from other people or\Nfrom me painfully going through getting
Dialogue: 0,0:53:04.51,0:53:10.83,Default,,0000,0000,0000,,code to actually work. The primitives are,\Nfor instance, RSA-512, and RSA-1024, and
Dialogue: 0,0:53:10.83,0:53:14.80,Default,,0000,0000,0000,,RSA-2048. They're all RSA, but they're\Ndifferent primitives, or different
Dialogue: 0,0:53:14.80,0:53:19.46,Default,,0000,0000,0000,,mathematical functions with different\Nsecurity levels and, well, in these
Dialogue: 0,0:53:19.46,0:53:23.05,Default,,0000,0000,0000,,submissions, there's typically three\Ndifferent security levels, sometimes more
Dialogue: 0,0:53:23.05,0:53:26.82,Default,,0000,0000,0000,,choices, sometimes less and then a lot of\Nthe primitives have multiple
Dialogue: 0,0:53:26.82,0:53:31.17,Default,,0000,0000,0000,,implementations, like reference code and\Noptimized code for different platforms
Dialogue: 0,0:53:31.17,0:53:35.15,Default,,0000,0000,0000,,maybe. So, okay, a lot of those are\Ncollected in this benchmarking framework,
Dialogue: 0,0:53:35.15,0:53:39.94,Default,,0000,0000,0000,,all with the same API. libpqcrypto, I\Nthink I might have a few minutes to say a
Dialogue: 0,0:53:39.94,0:53:44.78,Default,,0000,0000,0000,,little more about this, libpqcrypto is\Nfocusing on having an API which is
Dialogue: 0,0:53:44.78,0:53:49.74,Default,,0000,0000,0000,,suitable for cryptographic deployment in\Nthe future. If you imagine that the
Dialogue: 0,0:53:49.74,0:53:54.58,Default,,0000,0000,0000,,implementation quality of the underlying\Ncrypto is dramatically improved, at least
Dialogue: 0,0:53:54.58,0:53:59.36,Default,,0000,0000,0000,,that interface layer is supposed to be\Nsomething that you'll be able to use. Some
Dialogue: 0,0:53:59.36,0:54:04.22,Default,,0000,0000,0000,,more examples of things out there, pqm4 is\Na library optimized for small ARM
Dialogue: 0,0:54:04.22,0:54:11.03,Default,,0000,0000,0000,,microcontrollers, the ARM Cortex-M4, or\Npqhw is for FPGAs, and this last one,Open
Dialogue: 0,0:54:11.03,0:54:16.68,Default,,0000,0000,0000,,Quantum Safe, that one, they don't have as\Nmany primitives maybe as libpqcrypto or
Dialogue: 0,0:54:16.68,0:54:19.98,Default,,0000,0000,0000,,SUPERCOP, but what's cool about that\Nproject is, they've got working
Dialogue: 0,0:54:19.98,0:54:26.25,Default,,0000,0000,0000,,integrations of all of these into OpenSSL\Nand OpenSSH. So if you're in, say the TLS
Dialogue: 0,0:54:26.25,0:54:31.15,Default,,0000,0000,0000,,world, then that's clearly the way to use\Nthese post-quantum proposals, at least
Dialogue: 0,0:54:31.15,0:54:38.18,Default,,0000,0000,0000,,quite a few of them, inside TLS. Okay, let\Nme look a little bit at libpqcrypto and
Dialogue: 0,0:54:38.18,0:54:43.48,Default,,0000,0000,0000,,then we'll finish this off. There's lots\Nof cryptographic libraries which give you
Dialogue: 0,0:54:43.48,0:54:48.87,Default,,0000,0000,0000,,a nice, simple API for hash. They'll have\Nsome simple function like sha256, which
Dialogue: 0,0:54:48.87,0:54:53.50,Default,,0000,0000,0000,,takes a message, okay, in C you have to\Nsay there's a pointer to the beginning of
Dialogue: 0,0:54:53.50,0:54:58.44,Default,,0000,0000,0000,,the message plus the length of the\Nmessage, and then gives you back some hash
Dialogue: 0,0:54:58.44,0:55:03.10,Default,,0000,0000,0000,,of some 256 bit, 32 byte hash. In a higher\Nlevel language, of course, you say
Dialogue: 0,0:55:03.10,0:55:09.02,Default,,0000,0000,0000,,something like "h = sha256(m)", and m\Nknows what its length is, but in C it
Dialogue: 0,0:55:09.02,0:55:14.46,Default,,0000,0000,0000,,looks like you have h and m and the length\Nof m as arguments. Why not do this for all
Dialogue: 0,0:55:14.46,0:55:18.34,Default,,0000,0000,0000,,cryptographic functions? Somehow, it's\Nreally weird, lots of cryptographic
Dialogue: 0,0:55:18.34,0:55:22.03,Default,,0000,0000,0000,,libraries just have a nice, simple\Ninterface for hashing, and then if you
Dialogue: 0,0:55:22.03,0:55:25.71,Default,,0000,0000,0000,,want to do something like public key\Nsignatures, it's, well, okay, first we're
Dialogue: 0,0:55:25.71,0:55:30.60,Default,,0000,0000,0000,,going to find the factory, which is\Nproducing the keys, while the generator
Dialogue: 0,0:55:30.60,0:55:35.35,Default,,0000,0000,0000,,method for the key, blah blah blah, and\Nwell, you can just say, and what
Dialogue: 0,0:55:35.35,0:55:40.33,Default,,0000,0000,0000,,libpqcrypto does is, it simply says, you\Nsign something, with whichever signature
Dialogue: 0,0:55:40.33,0:55:44.61,Default,,0000,0000,0000,,scheme, you have to tell it, well, I'm\Ngoing to put the signed message somewhere,
Dialogue: 0,0:55:44.61,0:55:48.29,Default,,0000,0000,0000,,and then the length of the message is an\Noutput, the message you're signing and the
Dialogue: 0,0:55:48.29,0:55:51.96,Default,,0000,0000,0000,,length are inputs, and your secret key is\Nan input. And then it just takes
Dialogue: 0,0:55:51.96,0:55:56.01,Default,,0000,0000,0000,,everything in wire format, produces\Neverything in wire format. You don't have
Dialogue: 0,0:55:56.01,0:56:00.27,Default,,0000,0000,0000,,to have conversion functions, input/output\Nserializations etc. This is actually an
Dialogue: 0,0:56:00.27,0:56:04.95,Default,,0000,0000,0000,,API that goes back to, we've been doing\NSUPERCOP for many years, and SUPERCOP, the
Dialogue: 0,0:56:04.95,0:56:10.94,Default,,0000,0000,0000,,salt (NaCl) library, libsodium etc. are\Nall using the same API. And this is
Dialogue: 0,0:56:10.94,0:56:16.63,Default,,0000,0000,0000,,something which, actually people have\Nmeasured the impact on usability of
Dialogue: 0,0:56:16.63,0:56:20.81,Default,,0000,0000,0000,,cryptographic libraries depending on the\Ndifferent API provided by these libraries,
Dialogue: 0,0:56:20.81,0:56:24.43,Default,,0000,0000,0000,,and so we're pretty confident about\Nbenefits of having a nice, simple way to
Dialogue: 0,0:56:24.43,0:56:30.52,Default,,0000,0000,0000,,use crypto. NIST looked at this and said,\Nwell, ok, yeah. People should submit
Dialogue: 0,0:56:30.52,0:56:37.16,Default,,0000,0000,0000,,something to the post-quantum competition\Nusing this API, but they didn't have test
Dialogue: 0,0:56:37.16,0:56:42.07,Default,,0000,0000,0000,,code that people could use to make sure\Nthat they were following the
Dialogue: 0,0:56:42.07,0:56:46.36,Default,,0000,0000,0000,,rules. They didn't require that everybody\Npass any particular set of tests and they
Dialogue: 0,0:56:46.36,0:56:52.73,Default,,0000,0000,0000,,accepted submissions which didn't work,\Nfor example, in SUPERCOP. So, well, ok,
Dialogue: 0,0:56:52.73,0:56:55.82,Default,,0000,0000,0000,,that's why I had to do a bunch of work to\Nintegrate a bunch of submissions into,
Dialogue: 0,0:56:55.82,0:57:00.97,Default,,0000,0000,0000,,into SUPERCOP. But it's been sufficiently\Nclose to everybody using this that there
Dialogue: 0,0:57:00.97,0:57:05.07,Default,,0000,0000,0000,,has been a lot of code shared between\Nthese different projects, Open Quantum
Dialogue: 0,0:57:05.07,0:57:09.71,Default,,0000,0000,0000,,Safe is also starting from the same API\Nand then providing higher level
Dialogue: 0,0:57:09.71,0:57:14.78,Default,,0000,0000,0000,,integrations into OpenSSL and OpenSSH. OK.\NThere's a bunch of different signature
Dialogue: 0,0:57:14.78,0:57:19.28,Default,,0000,0000,0000,,systems and a bunch of different\Nencryption systems in libpqcrypto. Here's
Dialogue: 0,0:57:19.28,0:57:23.45,Default,,0000,0000,0000,,an example of what the higher level API\Nlooks like in Python. If you want to use
Dialogue: 0,0:57:23.45,0:57:28.03,Default,,0000,0000,0000,,libpqcrypto and sign a message, well\Nfirst somebody has to generate a public
Dialogue: 0,0:57:28.03,0:57:32.60,Default,,0000,0000,0000,,key and a secret key using the pqcrypto\Nlibrary. Signature system, here's one of
Dialogue: 0,0:57:32.60,0:57:37.63,Default,,0000,0000,0000,,the signature systems; Sphincs is a\Nstateless hash-based signature system, you
Dialogue: 0,0:57:37.63,0:57:42.83,Default,,0000,0000,0000,,don't have to record anything when you\Nsign message, and then 128 is security
Dialogue: 0,0:57:42.83,0:57:47.18,Default,,0000,0000,0000,,level 2 to the 128, using the SHA-256\Nhash, and well, you just have to know this
Dialogue: 0,0:57:47.18,0:57:52.04,Default,,0000,0000,0000,,name and then you say, give me a key pair,\Nsign a message using a secret key, open a
Dialogue: 0,0:57:52.04,0:57:57.13,Default,,0000,0000,0000,,message using a public key. Now this is\Nnot "you get a signature and then you do
Dialogue: 0,0:57:57.13,0:58:02.54,Default,,0000,0000,0000,,verify of a message and a signature". This\Nis another little API detail, designed to
Dialogue: 0,0:58:02.54,0:58:06.44,Default,,0000,0000,0000,,protect people against screwing up.\NThere's lots of applications which verify
Dialogue: 0,0:58:06.44,0:58:11.28,Default,,0000,0000,0000,,signatures, and then if the verification\Nfails, nobody's ever tested it, and the
Dialogue: 0,0:58:11.28,0:58:16.99,Default,,0000,0000,0000,,verification failure is ignored. What\Nactually works to protect application
Dialogue: 0,0:58:16.99,0:58:21.96,Default,,0000,0000,0000,,programmers is have an interface where you\Nhave a signed message as one bundle, it
Dialogue: 0,0:58:21.96,0:58:27.07,Default,,0000,0000,0000,,goes into the opening a signature, opening\Na signed message and producing a message,
Dialogue: 0,0:58:27.07,0:58:31.59,Default,,0000,0000,0000,,and the cryptographic library does not\Nproduce a message as output if the
Dialogue: 0,0:58:31.59,0:58:36.51,Default,,0000,0000,0000,,signature was invalid. So the signed\Nmessage is produced, is handled by the
Dialogue: 0,0:58:36.51,0:58:41.78,Default,,0000,0000,0000,,cryptographic library producing a message\Nif the signature is valid. Also there's an
Dialogue: 0,0:58:41.78,0:58:45.67,Default,,0000,0000,0000,,exception being raised, but even if you\Nignore the exception in Python or if
Dialogue: 0,0:58:45.67,0:58:49.51,Default,,0000,0000,0000,,you're using a lower level language\Nwithout exceptions, then you just aren't
Dialogue: 0,0:58:49.51,0:58:55.10,Default,,0000,0000,0000,,given back a message. This is what lots of\Nlittle thought that goes into the API.
Dialogue: 0,0:58:55.10,0:58:59.60,Default,,0000,0000,0000,,Maybe a bigger example in Python; this is\Na whole thing of using the library,
Dialogue: 0,0:58:59.60,0:59:05.17,Default,,0000,0000,0000,,generating a key, signing some random\Nmessage and opening the message. OK. What's
Dialogue: 0,0:59:05.17,0:59:11.28,Default,,0000,0000,0000,,going to happen in libpqcrypto coming up\Nis, first of all, one of the big problems
Dialogue: 0,0:59:11.28,0:59:16.50,Default,,0000,0000,0000,,with code quality is there's lots of\Nexposure to timing attacks. I saw a great
Dialogue: 0,0:59:16.50,0:59:20.67,Default,,0000,0000,0000,,talk earlier today about Spectre, and\Nthere's lots and lots of these attacks,
Dialogue: 0,0:59:20.67,0:59:24.70,Default,,0000,0000,0000,,and part of fixing these attacks is fixing\Nsoftware, along with we're going to have
Dialogue: 0,0:59:24.70,0:59:29.53,Default,,0000,0000,0000,,to do lots of hardware fixes. There's been\Nsome work on some implementations to fix
Dialogue: 0,0:59:29.53,0:59:35.27,Default,,0000,0000,0000,,this, but much more is required. Need a\Nlot more work on correctness. Lots and
Dialogue: 0,0:59:35.27,0:59:40.12,Default,,0000,0000,0000,,lots of the code doesn't even pass address\Nsanitizer. And this was, I don't want to
Dialogue: 0,0:59:40.12,0:59:44.97,Default,,0000,0000,0000,,tell you how much pain to get code working\Nand address sanitizer, where, I mean
Dialogue: 0,0:59:44.97,0:59:49.50,Default,,0000,0000,0000,,anybody writing code professionally is\Ngoing to be using these automatic tests as
Dialogue: 0,0:59:49.50,0:59:52.82,Default,,0000,0000,0000,,they're writing the code, and this is\Nsomething that just doesn't happen when
Dialogue: 0,0:59:52.82,0:59:58.28,Default,,0000,0000,0000,,you ask a bunch of mathematicians to write\Ncode. Formal verification. We'll do much
Dialogue: 0,0:59:58.28,1:00:02.79,Default,,0000,0000,0000,,more than testing and do much more than,\Nsay, address sanitizer does and much more
Dialogue: 0,1:00:02.79,1:00:07.43,Default,,0000,0000,0000,,than even an expert auditor will do. That\Nformal verification is going to guarantee
Dialogue: 0,1:00:07.43,1:00:11.83,Default,,0000,0000,0000,,that your code is doing what it's supposed\Nto for every possible input, which I used
Dialogue: 0,1:00:11.83,1:00:16.19,Default,,0000,0000,0000,,to be very skeptical about because it\Nseemed so painful to do for any realistic
Dialogue: 0,1:00:16.19,1:00:20.15,Default,,0000,0000,0000,,code, but I've started getting much more\Nenthusiastic about it, because the tools
Dialogue: 0,1:00:20.15,1:00:25.99,Default,,0000,0000,0000,,are getting much much better. And one\Nexample of something I did was a sorting
Dialogue: 0,1:00:25.99,1:00:30.42,Default,,0000,0000,0000,,verification, where some really fast\Nsorting code is actually completely
Dialogue: 0,1:00:30.42,1:00:34.30,Default,,0000,0000,0000,,verified to work correctly, the machine\Ncode is verified, so you compile it, even
Dialogue: 0,1:00:34.30,1:00:38.47,Default,,0000,0000,0000,,if there's compiler bugs, then the machine\Ncode is what's verified, so the
Dialogue: 0,1:00:38.47,1:00:43.11,Default,,0000,0000,0000,,verification isn't going to rely on some\Ncompiler being correct. This is using the
Dialogue: 0,1:00:43.11,1:00:46.57,Default,,0000,0000,0000,,angr toolkit, also, I don't know if\Nthere's any Trail of Bits people here,
Dialogue: 0,1:00:46.57,1:00:52.21,Default,,0000,0000,0000,,Manticore I understand has similar\Nfeatures, I used angr, but, well. There's
Dialogue: 0,1:00:52.21,1:00:55.75,Default,,0000,0000,0000,,really cool tools out there for doing\Nsymbolic execution and as part of that
Dialogue: 0,1:00:55.75,1:01:00.96,Default,,0000,0000,0000,,formal verification. Speed is important\Nand trying to get the code volume down,
Dialogue: 0,1:01:00.96,1:01:04.93,Default,,0000,0000,0000,,there's lots of duplication, we need more\Ninternal libraries to get post-quantum
Dialogue: 0,1:01:04.93,1:01:10.67,Default,,0000,0000,0000,,crypto on a smaller, easier to review code\Nbase. And finally, hopefully, at the end
Dialogue: 0,1:01:10.67,1:01:15.98,Default,,0000,0000,0000,,of all this we'll be able to throw away as\Nmany primitives as possible and focus on a
Dialogue: 0,1:01:15.98,1:01:20.18,Default,,0000,0000,0000,,small number of things, where we can say\N"We've really, seriously reviewed these.
Dialogue: 0,1:01:20.18,1:01:24.79,Default,,0000,0000,0000,,We've reviewed the designs, we've reviewed\Nthe implementations, and we're confident
Dialogue: 0,1:01:24.79,1:01:29.32,Default,,0000,0000,0000,,that these things are secure". That's it.\NThank you for your attention.
Dialogue: 0,1:01:29.32,1:01:44.68,Default,,0000,0000,0000,,{\i1}applause{\i0}
Dialogue: 0,1:01:44.68,1:01:49.37,Default,,0000,0000,0000,,Herald: Thank you Tanja & Daniel. If you would\Nlike to leave at this point, please do
Dialogue: 0,1:01:49.37,1:01:54.78,Default,,0000,0000,0000,,that very quietly, we'll have a short run\Nof Q&A. Signal angel, your first question.
Dialogue: 0,1:01:54.78,1:01:59.96,Default,,0000,0000,0000,,Microphone: [unintelligible] from older\Nsubmission in code base, are there any
Dialogue: 0,1:01:59.96,1:02:06.31,Default,,0000,0000,0000,,other ones that use smaller keys?\NTL: Use smaller keys you said?
Dialogue: 0,1:02:06.31,1:02:08.42,Default,,0000,0000,0000,,Signal angel: Yeah. From all the\Nsubmissions -
Dialogue: 0,1:02:08.42,1:02:10.77,Default,,0000,0000,0000,,TL: Yeah, so code-based cryptography,\Nthere's two submissions classic McEliece,
Dialogue: 0,1:02:10.77,1:02:14.23,Default,,0000,0000,0000,,which I highlighted because it's ours, and\Nthere's NTS-KEM [CHECK], which has these
Dialogue: 0,1:02:14.23,1:02:19.17,Default,,0000,0000,0000,,gigantic keys. Both of those are using\Ngoppa codes, which is what has received
Dialogue: 0,1:02:19.17,1:02:26.52,Default,,0000,0000,0000,,the most analysis so far, but at this\Ngigantic list of - Yep. What Dan is
Dialogue: 0,1:02:26.52,1:02:32.45,Default,,0000,0000,0000,,showing here, several of those are\Nactually code based. So, bigquake for
Dialogue: 0,1:02:32.45,1:02:36.70,Default,,0000,0000,0000,,instance, down there, is a code-based\Nsystem, then -
Dialogue: 0,1:02:36.70,1:02:39.86,Default,,0000,0000,0000,,DJB: Lake, that's, that's -\NTL: Bike is one, lake is one, down there,
Dialogue: 0,1:02:39.86,1:02:45.72,Default,,0000,0000,0000,,so lake would be fitting this by saying\Nit's very small keys and signatures and
Dialogue: 0,1:02:45.72,1:02:53.09,Default,,0000,0000,0000,,ciphertext. The downside is, it is using\Nfar less well-studied codes. So we need to
Dialogue: 0,1:02:53.09,1:02:57.65,Default,,0000,0000,0000,,see how that develops.\NHerald: Thank you. For people in the room,
Dialogue: 0,1:02:57.65,1:03:02.04,Default,,0000,0000,0000,,please try to limit your questions to a\Nsingle sentence. Microphone number 3, your
Dialogue: 0,1:03:02.04,1:03:05.83,Default,,0000,0000,0000,,question.\NMicrophone 3: OK. How exactly do you
Dialogue: 0,1:03:05.83,1:03:11.06,Default,,0000,0000,0000,,define post-quantum crypto? I mean, you\Nhave Shor's algorithm, you have the other
Dialogue: 0,1:03:11.06,1:03:17.34,Default,,0000,0000,0000,,algorithms, but do you say, OK, it's just\Nsecure against factoring, discrete
Dialogue: 0,1:03:17.34,1:03:22.31,Default,,0000,0000,0000,,logarithms, or do you also take into\Naccount optimization problems and stuff
Dialogue: 0,1:03:22.31,1:03:26.47,Default,,0000,0000,0000,,like that?\NDJB: Yeah. So, I mean the definition
Dialogue: 0,1:03:26.47,1:03:31.35,Default,,0000,0000,0000,,is, we're trying to protect against any\Nattacker who has a big quantum computer
Dialogue: 0,1:03:31.35,1:03:36.09,Default,,0000,0000,0000,,and we have a rough understanding of what\Nquantum computers can do, because they're
Dialogue: 0,1:03:36.09,1:03:41.92,Default,,0000,0000,0000,,limited by the laws of quantum physics.\NWhich tells us that, OK, if you can build
Dialogue: 0,1:03:41.92,1:03:46.45,Default,,0000,0000,0000,,a computer that supports what are called\NToffoli gates and Hadamard gates, then you
Dialogue: 0,1:03:46.45,1:03:50.98,Default,,0000,0000,0000,,can, well, it's not completely proven, but\Nit's very plausible that you can simulate
Dialogue: 0,1:03:50.98,1:03:52.79,Default,,0000,0000,0000,,the matrix at that point, a quantum\Nmatrix.
Dialogue: 0,1:03:52.79,1:03:54.64,Default,,0000,0000,0000,,Microphone 3: Yes, but that's the\Nuniversal model.
Dialogue: 0,1:03:54.64,1:03:58.45,Default,,0000,0000,0000,,DJB: Yes, you have a universal quantum\Ncomputer at that point. The problem is,
Dialogue: 0,1:03:58.45,1:04:03.13,Default,,0000,0000,0000,,how do we know, even if we say, well OK,\Nby believing that quantum physics is
Dialogue: 0,1:04:03.46,1:04:08.09,Default,,0000,0000,0000,,everything we can do in the universe, that\Ntells us we have a computation build out
Dialogue: 0,1:04:08.09,1:04:12.21,Default,,0000,0000,0000,,of Hadamards and Toffolis. That doesn't\Ntell you what kinds of algorithms you can
Dialogue: 0,1:04:12.21,1:04:16.25,Default,,0000,0000,0000,,put together. And there's this big problem\Nthat's always been a problem for
Dialogue: 0,1:04:16.25,1:04:20.62,Default,,0000,0000,0000,,cryptography, is trying to imagine what\Nall possible algorithms are, and sometimes
Dialogue: 0,1:04:20.62,1:04:24.57,Default,,0000,0000,0000,,people miss something. And so if somebody\Never tells you, "oh, the system is
Dialogue: 0,1:04:24.57,1:04:28.10,Default,,0000,0000,0000,,provably secure, there's, there can't\Npossibly be an algorithm which is faster
Dialogue: 0,1:04:28.10,1:04:32.38,Default,,0000,0000,0000,,than this to break the system", no there's\Nno guarantees, and lots of people have
Dialogue: 0,1:04:32.38,1:04:36.57,Default,,0000,0000,0000,,been overconfident and burned, because\Nthere is actually a faster algorithm.
Dialogue: 0,1:04:36.57,1:04:39.94,Default,,0000,0000,0000,,We've had a lot of work on people trying\Nto figure out good algorithms using
Dialogue: 0,1:04:39.94,1:04:44.25,Default,,0000,0000,0000,,quantum computers, for instance for the\Nsub-exponential attacks that Tanja was
Dialogue: 0,1:04:44.25,1:04:48.84,Default,,0000,0000,0000,,mentioning against CSIDH, and that's\Nsomething where, there's a long history to
Dialogue: 0,1:04:48.84,1:04:52.57,Default,,0000,0000,0000,,those attacks, starting with Cooperberg's\Nalgorithm, and this is going beyond Shor's
Dialogue: 0,1:04:52.57,1:04:56.71,Default,,0000,0000,0000,,algorithm and Grover's algorithm. And it's\Nreally important to look more at what sort
Dialogue: 0,1:04:56.71,1:05:00.44,Default,,0000,0000,0000,,of quantum algorithms could attack\Ncryptographic systems. There's been some
Dialogue: 0,1:05:00.44,1:05:02.28,Default,,0000,0000,0000,,initial work, but there definitely\Nneeds to be more.
Dialogue: 0,1:05:02.28,1:05:06.75,Default,,0000,0000,0000,,TL: I mean, our attacker is allowed to do\Nwhatever they want. That's why I'm showing
Dialogue: 0,1:05:06.75,1:05:10.22,Default,,0000,0000,0000,,this as attacker. The attacker is not\Nplaying by the rules. The only thing we
Dialogue: 0,1:05:10.22,1:05:12.12,Default,,0000,0000,0000,,know is our attacker has a quantum\Ncomputer.
Dialogue: 0,1:05:12.12,1:05:15.87,Default,,0000,0000,0000,,Microphone 3: Okay.\NHerald: Right, signal angel, your next
Dialogue: 0,1:05:15.87,1:05:18.77,Default,,0000,0000,0000,,question.\NSignal angel: Question from the Internet.
Dialogue: 0,1:05:18.77,1:05:22.66,Default,,0000,0000,0000,,Size does matter, but what about the\Nperformance of post-quantum cryptography
Dialogue: 0,1:05:22.66,1:05:28.22,Default,,0000,0000,0000,,compared to classical algorithms for\Nembedded or FPGA devices, for example of
Dialogue: 0,1:05:28.22,1:05:32.55,Default,,0000,0000,0000,,firmware signing or communication and\Nencryption?
Dialogue: 0,1:05:32.55,1:05:41.22,Default,,0000,0000,0000,,TL: OK. So on the big list, and quickly\Nfiring up. pqm4, that's using a Cortex ARM
Dialogue: 0,1:05:41.22,1:05:45.72,Default,,0000,0000,0000,,M4, so that's a rather small device. They\Ndid not implement all algorithms and for
Dialogue: 0,1:05:45.72,1:05:50.88,Default,,0000,0000,0000,,some of them they said, it is very\Ncumbersome to do with the big keys. So
Dialogue: 0,1:05:50.88,1:05:54.97,Default,,0000,0000,0000,,yes, it's more of an issue. I mean, we're\Nspoiled with elliptic curves, just having
Dialogue: 0,1:05:54.97,1:06:00.39,Default,,0000,0000,0000,,256 bits there, and all the systems are\Nlarger than that. CSIDH is the closest you
Dialogue: 0,1:06:00.39,1:06:05.45,Default,,0000,0000,0000,,get, but then it has the big computation.\NBut there is effort, and these smaller and
Dialogue: 0,1:06:05.45,1:06:10.45,Default,,0000,0000,0000,,more fitting systems have been\Nimplemented. Hopefully we'll get better.
Dialogue: 0,1:06:10.45,1:06:14.81,Default,,0000,0000,0000,,Herald: Thanks. Microphone number 4, your\Nquestion.
Dialogue: 0,1:06:14.81,1:06:20.72,Default,,0000,0000,0000,,Microphone 4: You said, when Google did\Nsome tests, that said it's just too slow,
Dialogue: 0,1:06:20.72,1:06:26.79,Default,,0000,0000,0000,,they cannot really use it. Would the\Nsolution be acceleration units, like used
Dialogue: 0,1:06:26.79,1:06:32.10,Default,,0000,0000,0000,,for AES in CPUs?\NTL: So, Google was excluding the use of
Dialogue: 0,1:06:32.10,1:06:35.77,Default,,0000,0000,0000,,the supersingular isogenies based on\Nspeed. I assume that's what you mean,
Dialogue: 0,1:06:35.77,1:06:42.26,Default,,0000,0000,0000,,rather than the big ones with bandwidth. I\Ndon't know all the details of it. My
Dialogue: 0,1:06:42.26,1:06:46.35,Default,,0000,0000,0000,,assumption is, it was factoring in also\Nthe security, like how much time have
Dialogue: 0,1:06:46.35,1:06:50.08,Default,,0000,0000,0000,,people spent on analyzing it, which made\Nthem more comfortable with the structured
Dialogue: 0,1:06:50.08,1:06:55.61,Default,,0000,0000,0000,,lattices than the supersingular isogenies.\NYou can speed things up if you have a big
Dialogue: 0,1:06:55.61,1:07:00.87,Default,,0000,0000,0000,,engine, which would be manufactured to do\Nfinite field arithmetic, but that is much,
Dialogue: 0,1:07:00.87,1:07:07.20,Default,,0000,0000,0000,,much bigger than, say, an AES engine.\NDJB: Maybe just an extra comment. I think
Dialogue: 0,1:07:07.20,1:07:11.53,Default,,0000,0000,0000,,that the choice they made of NTRU-HRSS is\Nreally an excellent choice of, it's
Dialogue: 0,1:07:11.53,1:07:16.65,Default,,0000,0000,0000,,something which is small enough to fit\Ninto most applications, I mean 1,000 bytes
Dialogue: 0,1:07:16.65,1:07:20.57,Default,,0000,0000,0000,,or so, it's much bigger than elliptic\Ncurve crypto, but compared to all the data
Dialogue: 0,1:07:20.57,1:07:24.86,Default,,0000,0000,0000,,we tend to send around, it usually fits,\Nunless you got, like, some really small
Dialogue: 0,1:07:24.86,1:07:30.90,Default,,0000,0000,0000,,communication happening, then you usually\Ncan fit a kilobyte or so, which is the
Dialogue: 0,1:07:30.90,1:07:37.02,Default,,0000,0000,0000,,NTRU-HRSS sizes. And it's something which,\Nit's got some history of study. I would be
Dialogue: 0,1:07:37.02,1:07:41.24,Default,,0000,0000,0000,,the last person to say that lattices are\Ndefinitely secure, and we actually, our
Dialogue: 0,1:07:41.24,1:07:46.48,Default,,0000,0000,0000,,NTRU Prime submission is worried about\Nways that something like NTRU-HRSS could
Dialogue: 0,1:07:46.48,1:07:52.06,Default,,0000,0000,0000,,maybe be broken, but there's no evidence\Nof any problems, and NTRU has held up for
Dialogue: 0,1:07:52.06,1:07:57.91,Default,,0000,0000,0000,,about 20 years of study without being\Nbroken. So, it's also reasonably fast, so
Dialogue: 0,1:07:57.91,1:08:01.95,Default,,0000,0000,0000,,it's a reasonable compromise between the\Ndifferent constraints of trying to have
Dialogue: 0,1:08:01.95,1:08:07.34,Default,,0000,0000,0000,,something secure and not ridiculously big,\Nand, well, if it gets broken, then
Dialogue: 0,1:08:07.34,1:08:13.57,Default,,0000,0000,0000,,we're in trouble. But hopefully it's okay.\NHerald: Thanks. Signal angel. The final
Dialogue: 0,1:08:13.57,1:08:16.71,Default,,0000,0000,0000,,question please.\NSignal angel: The final question. Can
Dialogue: 0,1:08:16.71,1:08:21.46,Default,,0000,0000,0000,,CSIDH drawn on a hardware accelerator make\Nfor regular elliptic curves, or is it is
Dialogue: 0,1:08:21.46,1:08:24.22,Default,,0000,0000,0000,,the handling of isogenies more\Nproblematic?
Dialogue: 0,1:08:24.22,1:08:29.10,Default,,0000,0000,0000,,TL: All right, so depends what your\Nhardware accelerator has. If it's like one
Dialogue: 0,1:08:29.10,1:08:33.20,Default,,0000,0000,0000,,of fairly generic elliptic curve\Narithmetics, you can probably use it.
Dialogue: 0,1:08:33.20,1:08:37.77,Default,,0000,0000,0000,,We're getting some speed from not using\Nelliptic curves in Weierstrass form, but
Dialogue: 0,1:08:37.77,1:08:42.25,Default,,0000,0000,0000,,Montgomery forms, so you probably would\Nwant to modify the accelerator they're
Dialogue: 0,1:08:42.25,1:08:47.83,Default,,0000,0000,0000,,currently using to fit this better. Also,\Nmost systems are optimized for 256 bit
Dialogue: 0,1:08:47.83,1:08:53.15,Default,,0000,0000,0000,,elliptic curves or 384, with 512 bits\Nwe're a little bit outside, but most of
Dialogue: 0,1:08:53.15,1:08:58.13,Default,,0000,0000,0000,,the operations would be looking just the\Nsame. The most time we spend on doing a
Dialogue: 0,1:08:58.13,1:09:04.14,Default,,0000,0000,0000,,big scalar multiplication, and then we\Nhave some operations in these isogenies,
Dialogue: 0,1:09:04.14,1:09:09.03,Default,,0000,0000,0000,,but they are fairly similar. If you have,\Nlike, the field arithmetic built up, you
Dialogue: 0,1:09:09.03,1:09:15.51,Default,,0000,0000,0000,,can just put these together and have an\Nisogeny computation as well. So yes, it
Dialogue: 0,1:09:15.51,1:09:18.75,Default,,0000,0000,0000,,can get faster. As I said, this is from\NJanuary, we're still working on the
Dialogue: 0,1:09:18.75,1:09:23.85,Default,,0000,0000,0000,,security analysis, so don't build any\Nhardware, at this moment, quite yet.
Dialogue: 0,1:09:23.85,1:09:26.94,Default,,0000,0000,0000,,{\i1}laughter{\i0}\NHerald: Thank you so much. Please give
Dialogue: 0,1:09:26.94,1:09:29.87,Default,,0000,0000,0000,,them a huge round of applause for the\Ntalk.
Dialogue: 0,1:09:29.87,1:09:38.07,Default,,0000,0000,0000,,{\i1}applause{\i0}
Dialogue: 0,1:09:38.07,1:09:39.72,Default,,0000,0000,0000,,{\i1}postroll music{\i0}
Dialogue: 0,1:09:39.72,1:10:01.00,Default,,0000,0000,0000,,subtitles created by c3subtitles.de\Nin the year 2020. Join, and help us!