0:00:00.000,0:00:25.750 rc3 preroll music 0:00:25.750,0:00:32.969 Herald: Good afternoon everyone watching,[br]the upcoming talk is by Ruben Gonzalez and 0:00:32.969,0:00:36.750 Krijn Reijnders, they're both Ph.D.[br]students at Radboud University, and Ruben 0:00:36.750,0:00:42.160 is also a capture-the-flag player, under[br]the name "Red Rocket", or affiliated with 0:00:42.160,0:00:47.780 "Red Rocket". Their talk will me about[br]post-quantum cryptography. And we'll take 0:00:47.780,0:00:53.070 a kind of introductory dive into Kyber.[br]This talk will also be live-translated 0:00:53.070,0:00:58.980 into German, so if you don't speak German,[br]don't despair. Dieser Vortrag wird also 0:00:58.980,0:01:05.910 übersetzt simultan in Deutsch, and that's[br]also the extent of my German. Also, this 0:01:05.910,0:01:10.959 talk is prerecorded will last a bit over[br]30 minutes, but the Q&A will be live 0:01:10.959,0:01:13.349 afterwards. So enjoy. 0:01:13.349,0:01:16.700 Ruben Gonzalez: Hello, and welcome to our[br]presentation on Kyber and post-quantum 0:01:16.700,0:01:24.110 cryptography. How does it work? First, my[br]name is Ruben Gonzalez, I'm a Ph.D. 0:01:24.110,0:01:27.420 student in the Netherlands. I'm doing this[br]presentation together with my colleague 0:01:27.420,0:01:35.590 Krijn Reijnders, and we'll be teaching you[br]all about Kyber today. So, first things 0:01:35.590,0:01:40.179 first, a small disclaimer, because I don't[br]want to disappoint any people: We're doing 0:01:40.179,0:01:46.259 boomer crypto here, so we won't be talking[br]about blockchain, NFTs, shitcoins,... at 0:01:46.259,0:01:52.631 all. Instead, we're going to bore you with[br]mathematics, weird kinds of key pairs, and 0:01:52.631,0:02:01.970 U.S. government agencies. So, our talk is[br]divided into four segments. First, I'm 0:02:01.970,0:02:06.530 going to teach you a little bit about what[br]post-quantum cryptography actually is and 0:02:06.530,0:02:11.540 why you should care about it. Then we're[br]going to talk about Kyber, which is the 0:02:11.540,0:02:15.860 scheme we're going to go into detail[br]about, because it's just about to take 0:02:15.860,0:02:20.320 over the world. And then Kreijn will talk[br]to you a little bit more about the 0:02:20.320,0:02:25.560 security guarantees about how the system[br]actually works mathematically. And then 0:02:25.560,0:02:32.730 we're going to give you a brief outlook on[br]the future of crypto and where we're 0:02:32.730,0:02:44.349 headed in the field. So, post-quantum[br]crypto. A little bit of basics here: 0:02:44.349,0:02:50.390 Today, cryptography, on a high level, is[br]divided into two parts; a boring part and 0:02:50.390,0:02:56.120 an exciting part. So the boring part is[br]called symmetric crypto and symmetric 0:02:56.120,0:03:01.469 crypto does what you usually expect from[br]cryptography. So you can encrypt stuff 0:03:01.469,0:03:06.209 with it and sometimes you do[br]authentication with it. But the biggest 0:03:06.209,0:03:12.249 part is the encryption stuff. So you have[br]a secret team that nobody is allowed to 0:03:12.249,0:03:16.249 have, and if you have this secret key you[br]can encrypt things, and another person 0:03:16.249,0:03:24.300 that has the same secret you can decrypt[br]with it. So that's why it's symmetric - 0:03:24.300,0:03:29.480 you have one key for encryption and[br]decryption. And what you actually use 0:03:29.480,0:03:36.999 implementation wise, is almost exclusively[br]AES encryption encryption or hash 0:03:36.999,0:03:42.840 functions that are from the SHA family and[br]it's a symmetric world. That's a symmetric 0:03:42.840,0:03:47.590 side of things. Now you also have[br]asymmetric crypto because if you look at 0:03:47.590,0:03:54.040 symmetric crypto, you have this secret[br]key, but you don't actually have a way of 0:03:54.040,0:03:59.799 getting two parties having the same secret[br]key. And it's where asymmetric crypto 0:03:59.799,0:04:05.530 comes into play. So, you can use[br]asymmetric crypto, among other things, to 0:04:05.530,0:04:14.540 exchange this secret key. So asymmetric[br]crypto uses a key pair: a public key that 0:04:14.540,0:04:23.950 everybody can have and a secret key that [br]only the recipient can have. So. Yeah, 0:04:23.950,0:04:29.810 essentially with the public key you[br]encrypt, for example, the symmetric key, 0:04:29.810,0:04:36.530 and with the private key you decrypt, and[br]here it feels a bit more difficult. 0:04:36.530,0:04:41.840 There's not only two algorithms that are[br]being used, but there's an entire zoo of 0:04:41.840,0:04:51.180 algorithms used. So, let's look at the zoo[br]real quick. Probably some of these terms 0:04:51.180,0:04:57.449 you've already heard: Curve25519 is pretty[br]big; maybe you've used RSA before, Diffie- 0:04:57.449,0:05:04.340 Hellman, that sort of thing. So there's[br]this big zoo of different kinds of schemes 0:05:04.340,0:05:10.670 in asymmetric crypto that it can use for[br]different things. Sometimes there are 0:05:10.670,0:05:13.770 different schemes that you can use for the[br]same thing, or you can use one scheme for 0:05:13.770,0:05:19.190 different things. So it's a bit more[br]complicated to make an overview of the 0:05:19.190,0:05:26.220 algorithms. But, if you look at the zoo,[br]people seem to be happy, right? Oh, they 0:05:26.220,0:05:30.510 look around, they have a look, things seem[br]to work, it's a happy world. So why would 0:05:30.510,0:05:35.120 you want to change that? And in post-[br]quantum crypto, we actually want to change 0:05:35.120,0:05:41.699 the asymmetric crypto fundamentally. Well,[br]there's one big problem with this zoo, and 0:05:41.699,0:05:48.780 it's not in the zoo, but it's coming for[br]the zoo. So there's this guy, Peter Shore, 0:05:48.780,0:05:58.059 and he's threatening the zoo. He's about[br]to destroy it and everything in it. And 0:05:58.059,0:06:04.700 why is that? Well, we have this big zoo of[br]asymmetric crypto, right? But if you look 0:06:04.700,0:06:11.840 at the different schemes in detail, you[br]actually see that they are only based on 0:06:11.840,0:06:17.409 two mathematical problems. And that is[br]integer factorization and the discrete 0:06:17.409,0:06:22.349 logarithm. We don't have to we don't have[br]the time to go into much detail on those, 0:06:22.349,0:06:27.780 but you have to know that the entire[br]asymmetric crypto zoo is based on two 0:06:27.780,0:06:35.679 problems. And, coincidentally, Peter[br]Shore, defined an algorithm, a quantum 0:06:35.679,0:06:41.339 algorithm, that breaks those two problems[br]and all cryptography that's based on them. 0:06:41.339,0:06:50.940 So all of today's crypto is actually[br]broken if we can use Shore's algorithm. 0:06:50.940,0:06:55.880 Now Shore's algorithm is a quantum[br]algorithm. That means we need a large 0:06:55.880,0:07:02.380 enough quantum computer for it to work,[br]but once we have that, all asymmatric 0:07:02.380,0:07:10.530 crypto is destroyed. And why should you[br]care about that? Well, maybe you use one 0:07:10.530,0:07:16.669 of those things here. Well, actually you[br]do, whether you like it or not. You're 0:07:16.669,0:07:21.800 watching this stream right now via TLS.[br]Maybe you also use things like SSH or 0:07:21.800,0:07:28.580 email encryption or VPNs with IPsec or[br]WireGuard. Well, Shore's algorithm would 0:07:28.580,0:07:35.719 break all of those protocols. Everything.[br]And you should care because in the modern 0:07:35.719,0:07:41.939 information age, essentially everything is[br]digital communication. All security is 0:07:41.939,0:07:48.630 virtually based on cryptography, so, if[br]Shorezilla and breaks everything, we do 0:07:48.630,0:07:55.099 have a huge problem. So the natural[br]question that arises is: "when will we 0:07:55.099,0:08:02.610 have large quantum computers?" And the[br]answer is: "we don't know." Different 0:08:02.610,0:08:12.360 experts say different things. The opinions[br]vary from within five years to never. But 0:08:12.360,0:08:15.970 the truth is, nobody knows. We can't see[br]in the future. We don't have a magic eight 0:08:15.970,0:08:21.401 ball there. But we should definitely be[br]prepared for the large quantum computer 0:08:21.401,0:08:26.680 because we don't want all of our[br]information security to be broken when, 0:08:26.680,0:08:33.430 let's say, a large U.S. government agency[br]all of a sudden manages to build a quantum 0:08:33.430,0:08:41.880 computer. So post-quantum crypto is all[br]about designing asymmetric cryptography 0:08:41.880,0:08:48.250 that is unaffected by quantum computers.[br]Or let's say we hope they are. But we're 0:08:48.250,0:08:52.950 pretty certain they should be unaffected.[br]They're certainly unaffected by Shore's 0:08:52.950,0:08:59.230 algorithm. So now that you know a little[br]bit about what post-quantum cryptography 0:08:59.230,0:09:07.450 is about and why we need it, I want to[br]talk about Kyber. Kyber is the post- 0:09:07.450,0:09:15.700 quantum scheme that is most likely to be[br]adopted in the near future. So the 0:09:15.700,0:09:23.120 asymmetric crypto zoo is threatened -[br]Let's make a new new zoo, where people can 0:09:23.120,0:09:32.750 and people can be happy and live their[br]fulfilled lives. The standardization 0:09:32.750,0:09:38.310 organization NIST launched a call a couple[br]of years back for new cryptographic 0:09:38.310,0:09:44.820 schemes that are resilient against quantum[br]computers. And first schemes are actually 0:09:44.820,0:09:53.270 about to be standardized very soon in[br]early 2022. So, we want to look at one 0:09:53.270,0:10:00.829 scheme that is about to be standardized,[br]and it's called Kyber. Now why are looking 0:10:00.829,0:10:09.730 at exactly that scheme? Well, it's very[br]fast, and the public and private key sizes 0:10:09.730,0:10:15.340 are not too big, meaning you can actually[br]use it in real world projects, which is 0:10:15.340,0:10:21.200 not always the case for all post-quantum[br]schemes. So it is already, even though 0:10:21.200,0:10:26.170 it's not, it's standardized, it has[br]already seen some adoption in industry. 0:10:26.170,0:10:31.730 And it's a lattice-based scheme. And right[br]now it looks a little bit like lattice is 0:10:31.730,0:10:36.149 going to be the future. If you don't know[br]what a lot of space scheme is, that's 0:10:36.149,0:10:44.220 really fine; Krijn is going to tell you in[br]the end. So, that was the fun part of our 0:10:44.220,0:10:48.610 presentation, the easygoing part. Now we[br]need to roll up our sleeves, we need to 0:10:48.610,0:10:56.630 get our hands dirty and we need some[br]mathematics. And for that, I'm going to 0:10:56.630,0:11:03.850 give the mic - turn over to Krijn. (How do[br]you say that? Give it to Krijn? I don't 0:11:03.850,0:11:08.139 know.) Bye.[br]Krijn Reijnders: So, now we need maths. So 0:11:08.139,0:11:13.110 let's start. What we need in Kyber are[br]polynomials, and we need to work with 0:11:13.110,0:11:17.959 polynomials. But actually, you can think[br]of polynomials just like you do of as 0:11:17.959,0:11:23.510 numbers. What do I mean with that? I mean[br]that you can just multiply them and you 0:11:23.510,0:11:29.970 can also just add them together like you[br]do with numbers. And just as we do with 0:11:29.970,0:11:35.479 numbers in pre- quantum cryptography, when[br]they get too big, we reduced them. We do 0:11:35.479,0:11:40.970 this modulo operation. We'll do the same[br]for the coefficients in the polynomials, 0:11:40.970,0:11:45.360 but also, when the degree of a polynomial[br]gets too big, we will reduce them by 0:11:45.360,0:11:51.110 another polynomial. So we have a modulo[br]operation with polynomials, and in this 0:11:51.110,0:11:56.600 way you can do all kinds of things with[br]polynomials. And that's actually all of 0:11:56.600,0:12:01.720 the mathematics that we all need[br]fundamentally to work with Kyber. What do 0:12:01.720,0:12:06.900 I mean by that? Well, if you can do[br]multiplication and addition, then you can 0:12:06.900,0:12:11.730 also do these things like we do for[br]numbers with matrices and vectors, so we 0:12:11.730,0:12:17.399 can multiply a matrix with a vector and[br]add another vector. And this works the 0:12:17.399,0:12:21.490 same for these polynomials, so you can[br]have a matrix full of polynomials and a 0:12:21.490,0:12:25.930 vector full of polynomials, and you can[br]just multiply them together, add another 0:12:25.930,0:12:30.380 vector. It's just this basic operation of[br]multiplication and addition of 0:12:30.380,0:12:37.760 polynomials. It looks a bit more[br]complicated, but that's it. And then, 0:12:37.760,0:12:42.209 let's say we do this, we have a matrix and[br]we multiplied by a vector and we add 0:12:42.209,0:12:46.421 another small vector. Now if I give you[br]the end result of this computation, and I 0:12:46.421,0:12:51.769 give you this matrix that we started with,[br]it's actually very hard to recover the 0:12:51.769,0:12:56.140 vector that we've multiplied the matrix[br]with. And this is the fundamental problem 0:12:56.140,0:13:02.199 that we need in Kyber. And it's called[br]module-learning-with-errors. I know this 0:13:02.199,0:13:06.779 name does not make a lot of sense, but[br]apparently mathematicians thinks it does 0:13:06.779,0:13:15.110 aptly describe the problem. So this[br]matrix, we call it 'A', this secret vector 0:13:15.110,0:13:19.440 of ours, we call it 's', then we need to[br]add a small error term so that it's not 0:13:19.440,0:13:24.000 too easy to solve this problem, and then[br]we get a public value again, which we call 0:13:24.000,0:13:32.699 't'. This gets you the equation A times s[br]plus e equals t. And then the public key 0:13:32.699,0:13:38.730 pair is this matrix 'A' and this end[br]result 't', and the private key is our 0:13:38.730,0:13:45.629 secret vector, 's'. That's all that we[br]need to generate a key pair in Kyber. We 0:13:45.629,0:13:48.889 need to ensure actually that the private[br]key pair has small coefficient, and that 0:13:48.889,0:13:55.570 also makes it very compact to transmit.[br]And also, this error has small 0:13:55.570,0:14:01.570 coefficients. For the rest of the[br]presentation: These error terms, they are 0:14:01.570,0:14:05.170 necessary, but they complicate the[br]equations are a bit too, so we'll just 0:14:05.170,0:14:09.540 write them in emojis so that you know what[br]the errors are and what are the important 0:14:09.540,0:14:15.730 values, and now Ruben will explain again:[br]How can we encrypt and decrypt messages 0:14:15.730,0:14:21.680 using such a public and private key pair?[br]R.G.: OK, our Boomer is back, and he wants 0:14:21.680,0:14:28.550 to encrypt something. So, as an example,[br]he wants to encrypt the letter C. So C is 0:14:28.550,0:14:33.720 not a variable, it's literally the letter[br]"C" that he wants to encrypt. And as we 0:14:33.720,0:14:38.580 learned earlier, to encrypt something, we[br]need the public key. So we have this 0:14:38.580,0:14:48.079 public key, which is the matrix A and the[br]vector t. So first, we need to transform 0:14:48.079,0:14:52.839 the letter "C" into some form that Kyber[br]can work with because we want to encrypt 0:14:52.839,0:14:58.709 it with Kyber. So let's first break it[br]down into binary, right, in a computer, 0:14:58.709,0:15:04.790 everything is binary anyways, so let's say[br]we used to ASCII encoding. So we turn the 0:15:04.790,0:15:10.230 letter "C" into a series of ones and[br]zeros. In this case, it's one zero zero 0:15:10.230,0:15:16.610 zero zero one one. Now we have binary[br]representation, but Kyber uses those 0:15:16.610,0:15:21.550 polynomials, right? So we have to somehow[br]turn this into a polynomial, which turns 0:15:21.550,0:15:28.620 out to be quite simple. So we just do a[br]binary polynomial, so we take the ones and 0:15:28.620,0:15:34.970 zeros and use them as coefficients for a[br]polynomial. In this case, you can see the 0:15:34.970,0:15:43.089 polynomial on the slides, quite simple. So[br]one bit is one polynomial coefficient. 0:15:43.089,0:15:48.569 Since zero times something is just zero,[br]which is just leave out the zero terms and 0:15:48.569,0:15:54.050 shrink our polynomial a bit. So we now[br]have a plain text and we can use within 0:15:54.050,0:15:58.770 Kyber, right? The plaintext is a[br]polynomial "x to the power of six plus x 0:15:58.770,0:16:04.880 plus one". That's our plain text. We[br]haven't encrypted anything yet, but we 0:16:04.880,0:16:10.720 have a plain text. So now let's us Kyber[br]to encrypt the plain text polynomial. 0:16:10.720,0:16:17.480 First, we have to scale it. We have to[br]make our polynomial big. And we do that 0:16:17.480,0:16:22.760 simply by multiplying the polynomial with[br]a large factor. So here I chose 1337, it's 0:16:22.760,0:16:29.839 arbitrary, depends on the Kyber instance,[br]but we just multiply every polynomial 0:16:29.839,0:16:37.470 coefficient with the large number 1337. So[br]we have the same polynomial, but with 0:16:37.470,0:16:44.850 larger coefficients. So our scale[br]plaintext is 1337 x to the power of, and 0:16:44.850,0:16:51.890 so on and so on. So now we do the actual[br]encryption, which in Kyber, it's actually 0:16:51.890,0:16:57.730 quite simple. We just sprinkle in some[br]error terms. As Krijn mentioned earlier, 0:16:57.730,0:17:03.810 in our presentation, small error terms are[br]represented as emojis. Because they're not 0:17:03.810,0:17:09.110 that important, but you should still know[br]they're there. So our ciphertext is 0:17:09.110,0:17:16.440 actually just two values, v, which is a[br]polynomial and u, which is a vector of 0:17:16.440,0:17:24.640 polynomials. So, v is the key value from[br]the public key, multiplied and added with 0:17:24.640,0:17:35.350 error terms, and then the actual scale[br]plaintext message is added as well. u is a 0:17:35.350,0:17:40.190 matrix from the public key, multiplied[br]with an error term and an added error 0:17:40.190,0:17:46.870 term. You can see the carrot error term[br]appears in both equations. And that's it. 0:17:46.870,0:17:53.600 That's our encryption. (v,u) is the[br]encryption of our plaintext. So doing only 0:17:53.600,0:17:58.049 encryption would be kind of boring. We[br]probably also want to decrypt stuff. So, 0:17:58.049,0:18:03.950 how do we do that in Kyber? Well, we need[br]the private key, right? Public key 0:18:03.950,0:18:10.590 encrypts, private key decrypts. So we have[br]our ciphertext, those two values v and u. 0:18:10.590,0:18:17.220 And in order to decrypt, we first remove[br]the public key from it. And we do that 0:18:17.220,0:18:25.140 just by taking v minus the private key,[br]multiplied by u. And if I spell out the 0:18:25.140,0:18:34.100 equations, they become quite long. But as[br]you can see, if you think about the emojis 0:18:34.100,0:18:40.289 as error terms is that most of the public[br]key, or actually the entire public key, 0:18:40.289,0:18:49.480 kind of cancels out. So, and d, here on[br]the slide, is the end result of the 0:18:49.480,0:18:59.900 calculations of v minus private key times[br]u. And so we have our message in d, which 0:18:59.900,0:19:04.020 is the plain text, but we also have these[br]error terms laying around and the private 0:19:04.020,0:19:12.380 key. Now one core observation is[br]important. I mentioned earlier that error 0:19:12.380,0:19:19.309 terms are all small, meaning they're[br]polynomials with small coefficients. And 0:19:19.309,0:19:25.580 the private key also has polynomials with[br]small coefficients. So here on the slide, 0:19:25.580,0:19:32.140 everything on the right side is actually[br]small, but our plain text is large because 0:19:32.140,0:19:39.110 we scaled it earlier. We multiplied it[br]with a large number 1337. So simply by 0:19:39.110,0:19:46.169 kind of rounding everything, we get our[br]scaled plaintext back, because these terms 0:19:46.169,0:19:56.830 are small. So just by rounding, we get our[br]scaled plaintext back. And then we have 0:19:56.830,0:20:02.990 essentially decrypted. What we now have to[br]do is just turn it back into the original 0:20:02.990,0:20:11.590 text, so we scale down, divide every[br]coefficient by 1337. We bring back to zero 0:20:11.590,0:20:19.350 terms, so every coefficient that is not in[br]the polynomial has a zero. Yeah, every 0:20:19.350,0:20:23.450 term that is not in the polynomial has a[br]zero coefficient. So we bring back the 0:20:23.450,0:20:28.850 zeros and then from the binary polynomial,[br]we can just read out the ones and zeros 0:20:28.850,0:20:37.000 from the coefficients. We have back binary[br]code and this binary now we can decode 0:20:37.000,0:20:46.230 again using the ASCII, for example, and we[br]have our plaintext back. And that's how 0:20:46.230,0:20:54.150 Kyber decrypts. And then we can decode the[br]Kyber plaintext into your original 0:20:54.150,0:21:01.169 message, which was a "C". So how does[br]Kyber looks like for the home consumer? 0:21:01.169,0:21:06.690 Well, Kyber comes in three flavors, three[br]different security levels. There's 0:21:06.690,0:21:15.620 Kyber512 until Kyber1024. So, in[br]cryptography usually security is measured 0:21:15.620,0:21:22.700 in bits. Sometimes it's related to how[br]strong AES is. So the lowest acceptable 0:21:22.700,0:21:30.440 acceptable security level for us is 128[br]bit and the strongest security level we 0:21:30.440,0:21:38.390 use in practice is 256 bit. So Kyber512[br]has around 128 bit security and Kyber1024 0:21:38.390,0:21:48.700 as around 256 bit of security. Now that's[br]what the end user needs to know. But I 0:21:48.700,0:21:52.630 also want to show you what these[br]securities actually mean in terms of 0:21:52.630,0:21:58.240 Kyber, because Kyber instances are mainly[br]defined by three variables: n, k, and q. 0:21:58.240,0:22:04.710 And what do those mean? Well, n just means[br]the degree of the polynomials used within 0:22:04.710,0:22:14.529 Kyber. So 256 means we have exponents x to[br]the power of maximum 256. So polynomials 0:22:14.529,0:22:25.230 are quite large. 256 coefficients we can[br]store. k means the size of the vector. So 0:22:25.230,0:22:29.410 as you've seen, Kyber uses not only[br]polynomials, but also vectors of 0:22:29.410,0:22:38.350 polynomials. So essentially lists of[br]multiple polynomials. And in Kyber, the k 0:22:38.350,0:22:46.200 variable says how many polynomials are in[br]such a vector. q is the modulus for the 0:22:46.200,0:22:55.690 numbers. I mean, we have coefficients,[br]right? And how big can this coefficients get? 0:22:55.690,0:23:03.350 So the largest coefficient that is used[br]within Kyber would be 3328 because we take 0:23:03.350,0:23:10.780 it modulo 3329. So as you can see, in[br]Kyber, we don't have to deal with big 0:23:10.780,0:23:15.950 numbers, actually. We have to do with a[br]pre-quantum cryptography, we have to deal 0:23:15.950,0:23:25.480 a lot with huge numbers. Here, the numbers[br]are not that big. Also important is size 0:23:25.480,0:23:33.360 to speed tradeoffs. Now here you can see a[br]bar chart of public key, private key and 0:23:33.360,0:23:42.330 ciphertext sizes of an elliptic curve[br]scheme, Curve25519, RSA, and kyber in 0:23:42.330,0:23:47.120 smallest security level. So those three[br]security schemes are the same security 0:23:47.120,0:23:52.450 level, but as you can see, elliptic curve[br]crypto is really tiny, RSA is somewhat 0:23:52.450,0:23:58.610 bigger, an Kyber is even bigger. But if we[br]go to the highest security level, you see 0:23:58.610,0:24:09.970 that Kyber is actually very comparable to[br]RSA. However, ecc is still a lot smaller. 0:24:09.970,0:24:15.460 But you don't only care about sizes, you[br]also care about speed, you care about 0:24:15.460,0:24:24.070 speed even more. And if we compare the[br]same security level in Kyber, in elliptic 0:24:24.070,0:24:30.330 curve crypto and in RSA, we can see that[br]Kyber is on fire. Kyber is really, really 0:24:30.330,0:24:37.899 fast. So we can throw out RSA and just[br]compare elliptic curve crypto to Kyber, 0:24:37.899,0:24:44.090 and we can see Kyber is even faster than[br]elliptic crypto, which is quite impressive 0:24:44.090,0:24:49.649 because ellipctic crypto is already quite[br]fast. And, even more, we can see that the 0:24:49.649,0:24:55.730 highest security level of Kyber is faster[br]than the lowest security level of elliptic 0:24:55.730,0:25:04.800 curve crypto. So Kyber - fast as hell. I[br]know benchmarks are difficult. We have 0:25:04.800,0:25:13.490 different kinds of platforms, but as an[br]intuition: Kyber is really fast. So the 0:25:13.490,0:25:18.510 thing I want to mention is that Kyber[br]source code is available online. You can 0:25:18.510,0:25:24.700 download it from GitHub, for example, from[br]the PQClean Project, which has AVX 0:25:24.700,0:25:34.679 optimized implementations for desktop[br]CPUs, from the pqm4 project, which is the 0:25:34.679,0:25:40.160 optimized implementation for ARM-based[br]embedded processors, or there's also a 0:25:40.160,0:25:48.100 reference C implementation in the pq-[br]crystals project. And, last but not least, 0:25:48.100,0:25:52.830 the specification, the documentation, the[br]code, everything is licensed under 0:25:52.830,0:25:58.860 Creative Commons zero, meaning that it's[br]public domain. So there is zero license or 0:25:58.860,0:26:03.950 patenting issues with Kyber, it's just[br]public domain. You can clone and do 0:26:03.950,0:26:10.780 whatever you want with it. It's quite[br]nice. So that was it about Kyber, now 0:26:10.780,0:26:16.870 Krijn is going to tell you more about what[br]actually lattices are and why Kyber is 0:26:16.870,0:26:27.110 actually secure the way it is.[br]Krijn: OK, so that was Kyber. And we've 0:26:27.110,0:26:30.860 been talking a lot about polynomials, but[br]we haven't talked so much yet about 0:26:30.860,0:26:35.880 lattices. But we did say that Kyber was a[br]lattice based scheme. So what do lattices 0:26:35.880,0:26:39.539 have to do with all of this polynomial[br]stuff? And why do we think it's secure 0:26:39.539,0:26:45.419 because of this being lattice based? Well,[br]let's go back to these numbers that we 0:26:45.419,0:26:49.659 used for a second, just because they make[br]these things more understandable and 0:26:49.659,0:26:56.000 intuitive. We had this matrix[br]multiplication. We multiplied the matrix 0:26:56.000,0:27:00.170 with a vector. Now let's say we do this[br]for numbers, right? We have this matrix 0:27:00.170,0:27:05.400 13, 4, 2, 9 and we multiplied by a, b.[br]Well, actually, what you could also see 0:27:05.400,0:27:13.250 here is that you multiply the vector 13[br]over 2 a times and then add the vector 4 0:27:13.250,0:27:17.789 over 9 b times. And as you see in the[br]image, like, you can make different 0:27:17.789,0:27:22.549 combinations of that. So if you take a = 1[br]and b = 1, you get the point on the top 0:27:22.549,0:27:29.529 right corner and then you can do this for[br]a = 2 and b = 1, then 3 and 4 infinitely. 0:27:29.529,0:27:35.149 And then you would get all of these dots[br]spread out over the cartesian plane, and 0:27:35.149,0:27:39.640 it would go on infinitely in these[br]dimensions. So you would get infinite 0:27:39.640,0:27:49.740 number of points just by giving these two[br]original vectors 13, 2 and 4, 9. Now, our 0:27:49.740,0:27:54.929 secret key s was just actually then a way[br]to pick one of these points, because we 0:27:54.929,0:27:58.990 said, well, the Matrix a that we had in[br]the public key, it describes some sort of 0:27:58.990,0:28:06.309 lattice. And then the secret key s[br]described actually a specific point: a 0:28:06.309,0:28:11.240 number of times the first vector, plus a[br]number of times the second vector. Then 0:28:11.240,0:28:16.159 what does this error term do? Well, you[br]know, it shifts just a bit from this 0:28:16.159,0:28:22.600 lattice point that we were at and then we[br]get the end result t over there. And now 0:28:22.600,0:28:28.740 it's very difficult actually to get back[br]from t to this vector s. We know that it's 0:28:28.740,0:28:35.810 the closest vector to this given point t[br]in this lattice described by a. But this 0:28:35.810,0:28:40.200 problem of finding the closest vector in[br]the lattice and in a random letters is 0:28:40.200,0:28:44.840 actually very hard. And this is what we[br]call the closest vector problem, which is 0:28:44.840,0:28:51.149 a very good name because we're looking for[br]the closest vector. So for this two 0:28:51.149,0:28:56.220 dimensional example, we had the matrix e[br]and the vector t in the public key, and we 0:28:56.220,0:29:01.519 had the vector s in the private key and[br]that was hidden by this small error term. 0:29:01.519,0:29:07.850 So to recap: a gives you these initial[br]vectors, which you can use to describe the 0:29:07.850,0:29:13.909 lattice, s gives you a secret point in[br]that lattice. The error makes sure that 0:29:13.909,0:29:20.460 you're close to a lattice point, but not[br]too far away. And then we get the end 0:29:20.460,0:29:24.890 result t, which is this public point and[br]then getting back from this information of 0:29:24.890,0:29:32.230 this lattice and t to s is the closest[br]vector problem, in a nutshell. You may be 0:29:32.230,0:29:37.870 thinking now, OK, this is for numbers I[br]can see this right. It's just these dots 0:29:37.870,0:29:44.200 in this plane. For dimension two OK, I get[br]it. For Dimension three you can think of a 0:29:44.200,0:29:50.840 third dimension. Though we were talking[br]about dimension n way larger than 3 and 0:29:50.840,0:29:56.019 polynomials instead of numbers. And how do[br]we visualize this? And the truth is we 0:29:56.019,0:30:02.090 don't actually, but we do know how to[br]compute it, which was just this 0:30:02.090,0:30:06.840 multiplication and addition of[br]polynomials. So we just compute it and we 0:30:06.840,0:30:11.820 kind of think of it as a lattice[br]abstractly, but not visually. Now let's 0:30:11.820,0:30:15.840 finish with a short look at the future of[br]asymmetric crypto, and let's go back to 0:30:15.840,0:30:20.610 the post-quantum crypto zoo that we had.[br]We already took a look at Kyber, but there 0:30:20.610,0:30:25.740 was also other cryptographic primitives[br]such as Rainbow, Falcon, and SABER and 0:30:25.740,0:30:29.940 Dilithium, NTRU, McEliece. Among them,[br]there are signature schemes, but also 0:30:29.940,0:30:33.871 these key exchange mechanisms. Actually,[br]this zoo is quite different from the one 0:30:33.871,0:30:37.690 that we had pre-quantum, the one that we[br]had pre-quantum as we explained was based 0:30:37.690,0:30:42.899 on mostly integer factorization and a[br]discrete logarithm problem. But in the 0:30:42.899,0:30:48.299 post-quantum setting, we have a variety of[br]problems. We have hash based cryptography, 0:30:48.299,0:30:52.149 lattice based cryptography, code based[br]cryptography, multivariate based 0:30:52.149,0:30:54.840 cryptography, and isogeny based[br]cryptography. And these are five quite 0:30:54.840,0:30:59.750 different flavors of cryptography, with[br]also different underlying mathematical 0:30:59.750,0:31:06.220 problems. But post-quantum crypto is[br]coming. For example, Amazon has already 0:31:06.220,0:31:11.500 implemented some of the round two[br]candidates, such as Kyber in post-quantum 0:31:11.500,0:31:17.960 TLS. And also the BSI, which is the German[br]Ministry for Information Security, has put 0:31:17.960,0:31:23.389 out a proposal to integrate post-quantum[br]cryptography into Thunderbird as their 0:31:23.389,0:31:28.590 mail client. And even NIST has the[br]following quote that if you haven't 0:31:28.590,0:31:33.519 migrated to elliptic curve cryptography[br]yet, don't bother, just directly migrate 0:31:33.519,0:31:40.159 to post-quantum crypto. And that wraps up[br]our presentation on post-quantum crypto 0:31:40.159,0:31:45.220 and Kyber. If you want to do some further[br]reading, there is a link here to a blog 0:31:45.220,0:31:50.920 that goes a bit more in-depth in how Kyber[br]works and has a very small example. Just 0:31:50.920,0:31:55.340 as we've shown you in this video. Thank[br]you for your attention and we'll take some 0:31:55.340,0:31:58.200 questions now. 0:31:58.200,0:32:00.590 Question: So why should I care about this[br]now? 0:32:00.590,0:32:05.639 Ruben: Well, that's an excellent question.[br]Well, as we know from the Snowden leaks, 0:32:05.639,0:32:16.430 the NSA is currently recording a lot of[br]internet traffic that is encrypted, and 0:32:16.430,0:32:20.510 they're recording this encrypted traffic[br]in the hopes of being able to decrypt it 0:32:20.510,0:32:25.750 later. For example, using a large quantum[br]computer. So first, we have to care about 0:32:25.750,0:32:30.480 this now because our internet traffic is[br]already recorded and could be broken 0:32:30.480,0:32:36.970 later. And second, we have to care about[br]this now because transition, especially 0:32:36.970,0:32:41.309 when it comes to cryptography, is really[br]slow because standardization takes a lot 0:32:41.309,0:32:47.019 of time. Implementation takes a lot of[br]time, and adoption takes a lot of time. So 0:32:47.019,0:32:52.050 that's why we have to care now.[br]Question: But are there any downsides? 0:32:52.050,0:32:56.250 Krijn: Another very good question.[br]Actually, yeah, there are some downsides, 0:32:56.250,0:33:01.940 but they're not too big. Usually, the keys[br]are a bit larger than we are used to. In 0:33:01.940,0:33:06.690 some cases even much larger than we are[br]used to. And the speed is a bit worse than 0:33:06.690,0:33:14.769 we are used to. In some schemes, even much[br]slower than we are used to. But while this 0:33:14.769,0:33:19.570 is already being adopted, it is also still[br]a very active area of research and we are 0:33:19.570,0:33:24.970 continuously trying to make the keys[br]smaller and the schemes more efficient. In 0:33:24.970,0:33:29.600 the hopes that we in the end, get very[br]efficient schemes that will solve all of 0:33:29.600,0:33:33.380 our post-quantum problems. Why didn't you[br]let me eat the lettuce? 0:33:33.380,0:33:42.690 Ruben: It's my lettuce! Okay, now eat it[br]for the camera, you can eat one. But it's 0:33:42.690,0:33:49.980 not washed.[br]Herald: Okay, thank you. The first 0:33:49.980,0:33:54.649 question we got from the internet is: Why[br]are you using seven bit ASCII instead of 0:33:54.649,0:33:59.100 Unicode?[br]Ruben: So in that case of the letter c 0:33:59.100,0:34:05.340 that wouldn't make a difference anyways.[br]We just prefer to use ASCII because we 0:34:05.340,0:34:10.340 really, really want to piss off the[br]European people because all of these 0:34:10.340,0:34:17.940 umlauts and that kind of stuff. Of course,[br]they're unnecessary. So ASCII forever. 0:34:17.940,0:34:24.810 Herald: I'm surprised that both of us[br]Europeans as well, but let's not get to 0:34:24.810,0:34:34.460 the nationalism bit and carry on with the[br]next question, which is, by the way, how 0:34:34.460,0:34:40.390 can you compare the security levels[br]according to varying n and varying q, 0:34:40.390,0:34:45.880 respectively?[br]Ruben: Sorry, the connection was a bit 0:34:45.880,0:34:53.240 lost there. Could you repeat the question?[br]Herald: Of course, can you compare the 0:34:53.240,0:34:58.190 security levels according to varying n and[br]varying q, respectively? 0:34:58.190,0:35:06.270 Ruben: Yes, of course you can. I'm not[br]sure if I get the question. Of course, 0:35:06.270,0:35:13.360 that's how you do it, that's how you[br]compare and you can do that. I'm not sure 0:35:13.360,0:35:17.680 if the question asked me to do that right[br]now on the spot because that I couldn't 0:35:17.680,0:35:23.390 do, but I mean, it was on the slides, like[br]the security levels that are about to be 0:35:23.390,0:35:29.490 standardized, at least. But the one good[br]thing about Kyber, a very good thing that 0:35:29.490,0:35:37.050 I want to mention is that, so the[br]polynomials, the size stays the same, the 0:35:37.050,0:35:43.820 modulus q stays the same. Only the size of[br]the vectors change. So how many 0:35:43.820,0:35:48.460 polynomials you have in a vector. And that[br]makes it quite nice to write optimized 0:35:48.460,0:35:54.410 code because most parts of the code are[br]literally the same. If you look at the 0:35:54.410,0:36:00.730 implementation, the reference[br]implementation, you can see that it's 0:36:00.730,0:36:05.650 actually the same code for all the[br]security levels, just one header changes 0:36:05.650,0:36:14.940 that specifies how big the vectors are. So[br]that's quite nice. But you can yeah, you 0:36:14.940,0:36:19.820 have for RSA, you have different key[br]sizes. So yeah, it's more difficult to 0:36:19.820,0:36:25.760 optimize, but here you can just have the[br]same size as just the vector size changes, 0:36:25.760,0:36:31.590 which is nice[br]Herald: What about the potential for 0:36:31.590,0:36:37.300 hardware acceleration for Kyber? Could[br]that be possible, feasible? 0:36:37.300,0:36:42.720 Ruben: So I am not sure if I just answer[br]that or Krijn also wants to say something, 0:36:42.720,0:36:49.200 but hardware acceleration for post-quantum[br]schemes in general is, as we say, a very 0:36:49.200,0:36:55.610 active area of research. So these things[br]are very new. There were some people that 0:36:55.610,0:37:03.120 tried to use, there's a paper about it,[br]actually - you can look it up on the 0:37:03.120,0:37:06.900 internet - to use RSA bignum hardware[br]acceleration for Kyber, which is a quite 0:37:06.900,0:37:14.010 interesting idea because you work in[br]completely different things there. But 0:37:14.010,0:37:18.280 it's an open question and it's a very[br]active area of research. So if any of the 0:37:18.280,0:37:22.410 viewers are interested in that sort of[br]thing, to, I don't know, try out Kyber or 0:37:22.410,0:37:29.470 FPGAs or something. Yeah, try it out! So[br]there's a lot of potential there, but it's 0:37:29.470,0:37:35.490 also, as I said, very actively researched[br]because it's relatively new and it just 0:37:35.490,0:37:45.960 now finds adaptation in industry.[br]Herald: And there's a follow up question 0:37:45.960,0:37:50.580 that sort of mirrors it in a way because[br]that question is: T o what extent is this 0:37:50.580,0:37:56.390 feasible on embedded architectures with[br]very limited hardware to use Kyber there? 0:37:56.390,0:38:06.710 Ruben: So I've been using it on a Cortex[br]M3, which is ARM-based. So usually the 0:38:06.710,0:38:14.350 reference platform, we use the Cortex M4[br]because we want to. Like two experiments 0:38:14.350,0:38:18.880 that are reproducible, and you can buy[br]Cortex M4 boards quite cheaply from 0:38:18.880,0:38:28.590 various vendors. So it's definitely[br]possible to run Kyber on a Cortex M3. I 0:38:28.590,0:38:33.240 mean, there's also a project on GitHub.[br]It's called pqm3, that has Kyber benchmark 0:38:33.240,0:38:41.140 for various, yeah M3 boards, but that's[br]definitely possible. What I'm working on 0:38:41.140,0:38:51.520 right now is testing it on a Cortex M3 and[br]M4 for also application level, so included 0:38:51.520,0:38:59.970 it in TLS or KEMTLS. Or there's a paper[br]about WireGuard using Kyber and Dilithium 0:38:59.970,0:39:04.780 for example. That's definitely possible.[br]The question, also active area of research 0:39:04.780,0:39:10.480 is, how low can you get? Like, how much[br]can you optimize? Because there are 0:39:10.480,0:39:16.870 various tradeoffs, like do we want more[br]space for code but use less RAM and you 0:39:16.870,0:39:20.960 also always have these kinds of tradeoffs[br]in the embedded world. And that's 0:39:20.960,0:39:24.950 something I'm a little actively looking[br]into right now, actually. But it's 0:39:24.950,0:39:33.180 certainly possible to run it on embedded[br]systems. We could also go for a Cortex M0, 0:39:33.180,0:39:38.240 which is, like really, really low level,[br]but the cortex M3 is already running on 0:39:38.240,0:39:41.800 smartcards. So that's what I'm currently[br]looking at and there it's definitely 0:39:41.800,0:39:46.210 possible. But as I said, you have to look[br]into tradeoffs, see how much you want to 0:39:46.210,0:39:51.120 waste on ROM, how much you want to waste[br]on RAM and how much time do you have for 0:39:51.120,0:39:55.850 the runtime? But the benchmarks we are[br]having there, as I said. Go to Github, 0:39:55.850,0:40:01.120 pqm3, already quite good, so it's[br]definitely usable depending on your use 0:40:01.120,0:40:10.850 case. I hope that answers the question.[br]Herald: So do I. There's another question 0:40:10.850,0:40:15.970 by someone who actually has implemented[br]it. So I just briefly read the questions: 0:40:15.970,0:40:21.030 I implemented a raw learning error scheme[br]in an insecure "Hold my beer"-style. It 0:40:21.030,0:40:26.110 seems to work, but I see about 1% bit[br]errors in the decrypted text, how do real 0:40:26.110,0:40:32.520 implementation handle the expected bit[br]errors in the decryption? 0:40:32.520,0:40:41.550 Ruben: So the easy answer is rounding. So[br]you just throw away some of the lowest 0:40:41.550,0:40:47.430 bits, but that really depends on the[br]scheme. So if he has done some learning 0:40:47.430,0:40:51.740 with errors. So there are different[br]flavors of learning with errors. There's 0:40:51.740,0:40:54.390 like ring learning with errors, modulo[br]learning with errors, learning with 0:40:54.390,0:41:00.770 errors, and it depends on what he has[br]implemented. But in the end the thing that 0:41:00.770,0:41:06.140 seems to work is just throw off the least[br]significant bits, for example, depending 0:41:06.140,0:41:12.730 on how many errors you expect. I don't[br]know, Krijn do you want to add something? 0:41:12.730,0:41:16.530 Krijn: No, I think you're doing fine with[br]the question. 0:41:16.530,0:41:22.150 Ruben: If there's no question I'm going to[br]ask your questions afterwards. Very 0:41:22.150,0:41:32.000 personal ones for history. You know?[br]Herald: I shall move on to the next 0:41:32.000,0:41:36.490 question, but I think from a layman's[br]perspective, this may also relate to the 0:41:36.490,0:41:40.890 last question. The question is: Those[br]sequencing terms are set to be small 0:41:40.890,0:41:45.030 relative to the mesh's coefficients. How[br]do you make sure that those do not 0:41:45.030,0:41:47.910 compromise encryption and are chosen[br]arbitrarily? 0:41:47.910,0:41:53.800 Ruben: So again, I'm really sorry. I had a[br]couple of hiccoughs, so I didn't get the 0:41:53.800,0:42:00.960 question could you repeat it?[br]Herald: Sure. The question was: The Secret 0:42:00.960,0:42:06.880 key and error terms are set to be small[br]relative to the message coefficients. How 0:42:06.880,0:42:10.200 do you make sure that those do not[br]compromise the encryption chosen 0:42:10.200,0:42:14.330 arbitrarily?[br]Ruben: OK. I had a hiccough again, Krijn, 0:42:14.330,0:42:20.570 did you get the question? Otherwise, I'll[br]answer what I heard. I think what I think 0:42:20.570,0:42:31.590 I heard.[br]Krijn: So why are... why don't the 0:42:31.590,0:42:35.910 small... the fact that the error and the[br]private key are small, why doesn't this 0:42:35.910,0:42:42.910 compromise security? And in fact, well you[br]need the error to be quite small in order 0:42:42.910,0:42:46.660 to be able to solve this, this closest[br]vector problem that we've sketched. If the 0:42:46.660,0:42:50.640 error is too big then a different vector[br]could be the closest vector than the one 0:42:50.640,0:42:57.840 that you want. Now why the private key has[br]to be small. There are some results that 0:42:57.840,0:43:02.660 we know that this does not mean... that it[br]doesn't break the security basically of 0:43:02.660,0:43:06.900 the scheme. I don't know if , Ruben, you[br]can do a two liner on why that is. 0:43:06.900,0:43:11.750 Ruben: So I answer the question always[br]like: we bring in all those error terms. 0:43:11.750,0:43:19.610 How do we make sure that the decryption[br]isn't faulty, right? And actually, it's a 0:43:19.610,0:43:26.440 very good question, because there's a[br]provable, probably negligible probability 0:43:26.440,0:43:32.090 that there will be decryption errors.[br]However, Kyber is fast enough. We handle 0:43:32.090,0:43:39.620 them in the KEM Version of Kyber. So what[br]we have introduced here is the public key 0:43:39.620,0:43:45.300 encryption version. Standardized as the[br]KEM, which uses internally the public key 0:43:45.300,0:43:49.460 encryption version and in the KEM version,[br]you can be sure that this doesn't happen 0:43:49.460,0:43:56.250 because, yeah. To answer the question,[br]there's a tiny, tiny but negligible 0:43:56.250,0:44:00.850 probability that you have a decryption[br]error, so in that case a very good 0:44:00.850,0:44:06.500 question. But if you're really interested,[br]the blog post, I mean, you can download 0:44:06.500,0:44:14.770 the slides and there's a blog post. For[br]the talk, let's say, so you can go to the 0:44:14.770,0:44:19.770 blog post and there's the Kyber[br]specification reference. They can just 0:44:19.770,0:44:27.010 click on the specification and there you[br]can see that it's a fine tuning of 0:44:27.010,0:44:35.110 parameters to make sure that the sprinkled[br]in error terms do not invalidate the 0:44:35.110,0:44:41.900 decryption to a certain, within a certain[br]probability. And we make that probability 0:44:41.900,0:44:47.770 in Kyber so low that in reality it will[br]never happen. Like, 2 to the power of... 0:44:47.770,0:44:56.180 lets say magnitude-wise something like[br]atoms on Earth or like to give you an idea 0:44:56.180,0:45:00.900 of how big the numbers are there. So it's[br]a very, very low probability that that 0:45:00.900,0:45:10.570 will happen. But a very good question. At[br]least thats how I interpreted the 50% of 0:45:10.570,0:45:15.560 the question that I heard.[br]Herald: I am sorry that we seem to have a 0:45:15.560,0:45:21.060 technical problem.[br]Ruben: I think it's just the shitty 0:45:21.060,0:45:27.960 internet at my my parents place.[br]Herald: That could also be the case also 0:45:27.960,0:45:32.531 on my end there are troubles as well. The[br]question after that and maybe Krijn can 0:45:32.531,0:45:38.350 just start answering it. Would Kyber be[br]broken if someone found a simple solution 0:45:38.350,0:45:45.230 to the closest vector problem?[br]Krijn: Yeah, but we that's the case, 0:45:45.230,0:45:48.790 that's always the case for encryption. If[br]you managed to solve the fundamental 0:45:48.790,0:45:52.810 problem, then the encryption scheme is[br]broken. Luckily for the closest vector 0:45:52.810,0:45:57.910 problem, we have a very good, we have[br]quite some trust in this problem, so some 0:45:57.910,0:46:04.050 other of these post-quantum schemes are[br]based or more recent problems, so the 0:46:04.050,0:46:10.750 closest vector problem is a much older[br]one. So we do trust it, well I have quite 0:46:10.750,0:46:15.160 a bit of trust that it won't be easily[br]broken in the coming years. 0:46:15.160,0:46:19.570 Ruben: So the answer is it's a bit tricky[br]there, because the close vector problem is 0:46:19.570,0:46:25.050 NP hard. So we think this is like a very[br]good problem to start from. But the 0:46:25.050,0:46:31.480 question is also like how are these[br]lattices related to certain instanciations 0:46:31.480,0:46:36.450 of the closest vector problem? And are[br]these specific closest vector problems 0:46:36.450,0:46:41.940 maybe a bit simpler or something? But as[br]Krijn said we're in the closest vector 0:46:41.940,0:46:45.380 problem we trust like this is one of the[br]problems in post-quantum crypto that we're 0:46:45.380,0:46:49.960 pretty certain about. But yeah, if you[br]would solve it or if you have already 0:46:49.960,0:46:56.830 solved it, Kyber would be broken.[br]Herald: That sounds like a potential 0:46:56.830,0:47:01.490 inscription on the side of a coin. In the[br]closest vector problem we trust. And 0:47:01.490,0:47:05.851 talking about trust. The question after[br]this is: Would you trust this, this Kyber 0:47:05.851,0:47:10.820 algorithm to secure your communications[br]now? 0:47:10.820,0:47:17.220 Ruben: Should I answer or Krijn do you[br]want to, you haven't said so much? 0:47:17.220,0:47:21.360 Krijn: I would actually, yeah, I don't[br]have. So if you're skeptical about it, you 0:47:21.360,0:47:26.310 can also go to. I don't think we discussed[br]it, but you can go to hybrid modes of the 0:47:26.310,0:47:32.710 current classical, pre-qantum crypto and[br]post-quantum, if you can suffer the 0:47:32.710,0:47:37.580 drawbacks of that. But personally, yeah, I[br]guess I would. Ruben, would you? 0:47:37.580,0:47:45.060 Ruben: I would trust Kyber at this moment,[br]but there's... If you don't trust it as 0:47:45.060,0:47:51.050 Krijn said, you can go into hybrid mode,[br]so the idea, for example, for TLS is to 0:47:51.050,0:47:58.050 first do elliptic curve crypto and post-[br]quantum crypto together, sort of in a way 0:47:58.050,0:48:02.460 that the adversary, the attacker would[br]have to break both in order to compromise 0:48:02.460,0:48:09.220 the communication. So that way, you don't[br]have to fully trust Kyber yet if you want 0:48:09.220,0:48:15.260 to run the hybrid. But of course, the idea[br]is to at some point get rid of this 0:48:15.260,0:48:19.400 overhead and just run post-quantum crypto[br]without elliptic curve crypto 0:48:19.400,0:48:25.510 additionally. But yeah, I mean, I[br]personally would use it right now. But 0:48:25.510,0:48:32.940 what I also want to say is that in the[br]beginning of every krypto system, RSA, 0:48:32.940,0:48:37.400 elliptic curve doesn't matter. In the[br]beginning, everybody is quite skeptical 0:48:37.400,0:48:41.730 and nobody wants to use it yet. And that's[br]fine. Like, that's how the community 0:48:41.730,0:48:45.980 works. But over time, usually people gain[br]trust. 0:48:45.980,0:48:57.020 Herald: OK, thank you. Now we're getting[br]into speculative territory, and one of the 0:48:57.020,0:49:01.430 questions is whether you could have any[br]guesses on which of the schemes is 0:49:01.430,0:49:07.240 probably going to end up winning the NIST[br]PQC competition, post-quantum crypto 0:49:07.240,0:49:11.500 competition?[br]Ruben: So NIST specifically says it's not 0:49:11.500,0:49:23.560 a competition, very important. So Kyber is[br]one of the winners coming out of it, but 0:49:23.560,0:49:34.930 that's quite clear. And also you already[br]see adoption in the real world. We brought 0:49:34.930,0:49:42.290 two examples with Amazon and the BSI, for[br]example, that wants to include it in 0:49:42.290,0:49:49.920 Thunderbirds email encryption. So Kyber is[br]going to be one of the winners. This is 0:49:49.920,0:49:57.560 my... not only opinion, but yeah, that's[br]quite clear. And otherwise, I think 0:49:57.560,0:50:06.340 McEliece, which is a code based scheme[br]that is quite large in all measures, let's 0:50:06.340,0:50:11.640 say. But people seem to have more trust in[br]it because it has been around longer. 0:50:11.640,0:50:19.770 Yeah, so I'd say those for KEMs and[br]everybody is quite unhappy with the 0:50:19.770,0:50:27.490 signatures. So I don't think there will be[br]signatures standardized like this year or 0:50:27.490,0:50:32.910 beginning next year. But Krijn, I don't[br]know, maybe you have a guess? 0:50:32.910,0:50:38.530 Krijn: No, I'm not such a speculative[br]person, but I think Ruben's answer is 0:50:38.530,0:50:43.690 quite a good answer.[br]Ruben: Now you really have to also 0:50:43.690,0:50:49.170 speculate, I mean, come on, you can't just[br]piggyback on my answer. 0:50:49.170,0:50:52.760 Krijn: No I definitely can. It's[br]interesting to note actually that for the 0:50:52.760,0:51:01.960 signatures that there's less of a hurry,[br]so to say. It's especially this key 0:51:01.960,0:51:09.090 exchange that we wanted to make post-[br]quantum as soon as possible, maybe, or at 0:51:09.090,0:51:13.730 least one to standardize quickly and then[br]integrate into whatever building. Well, 0:51:13.730,0:51:19.830 for the signatures there a bit more time[br]so there's also more time to come up with 0:51:19.830,0:51:23.580 better solutions there or to analyze the[br]current solutions a bit more. 0:51:23.580,0:51:27.900 Ruben: Yeah, that's because I mean what we[br]mentioned is the attacker model, big 0:51:27.900,0:51:33.890 government agency, for example. And the[br]key exchange you have to fix now because 0:51:33.890,0:51:38.820 that could be later on broken and then the[br]communication can be decrypted. But 0:51:38.820,0:51:44.360 signatures like they have a small[br]lifetime, for example, and also they are 0:51:44.360,0:51:49.930 used for authentication. So you would need[br]an active adversary. And that, yeah. You 0:51:49.930,0:51:55.640 can't like record now and then do an[br]active attack in 10 years, like, that 0:51:55.640,0:51:58.990 doesn't work. So then we have some more[br]time yeah. 0:51:58.990,0:52:05.040 Herald: Well, that's not entirely true.[br]There's a lot of states using, and I'm 0:52:05.040,0:52:10.930 talking about signatures, not for the[br]ephemeral use in online usage, but the 0:52:10.930,0:52:16.030 more the use of signatures, for example,[br]document signatures. And for those an 0:52:16.030,0:52:18.180 attack would still be relevant for the[br]future. 0:52:18.180,0:52:23.590 Ruben: If they have, well, if they have a[br]long runtime, usually signatures or keys 0:52:23.590,0:52:28.790 at least, of signatures, they expire at[br]some point. But yeah, of course, if you 0:52:28.790,0:52:33.810 have, if you have signatures that do not[br]have an expiration date or something, then 0:52:33.810,0:52:37.920 they would be under threat as well.[br]Herald: In a document signing, you will 0:52:37.920,0:52:42.770 have signatures that have a very longer[br]lifetime than you will have for your 0:52:42.770,0:52:45.990 typical web transaction, for example. But[br]I'm now full dropping out of role as 0:52:45.990,0:52:49.120 herald who is a mere vessel of questions[br]from the audience. 0:52:49.120,0:52:50.590 Ruben: But of course, this is also[br]interesting for us. 0:52:50.590,0:52:57.420 Herald: And I guess with the last version,[br]at least, I think this is the last 0:52:57.420,0:53:01.020 question unless there is an additional one[br]on IRC, so people have to be quick if they 0:53:01.020,0:53:04.840 want to have additional questions. But the[br]last questions are just very practical. 0:53:04.840,0:53:11.020 And basically, do you have any ideas about[br]pitfalls when implementing Kyber already? 0:53:11.020,0:53:16.220 Do you have suggestions for making sure[br]you implement it security? Or is it simply 0:53:16.220,0:53:26.100 possible to implement it very naively?[br]Ruben: So. This is always a big fight in 0:53:26.100,0:53:31.010 the cryptography community, because[br]they're the people that say, oh, there are 0:53:31.010,0:53:36.380 a handful of chosen ones that are able to[br]implement it securely. And you should 0:53:36.380,0:53:41.770 never, ever, ever do it yourself. I'm on[br]the opposite side of that, I think people 0:53:41.770,0:53:47.590 should play around with implementation.[br]Try it out. So, Kyber is among the schemes 0:53:47.590,0:53:54.830 that it's definitely, let say easier to[br]implement in a correct way. However, it 0:53:54.830,0:54:03.650 depends where you want to use it because[br]you also have to take side channels into 0:54:03.650,0:54:08.440 consideration, especially if you work on[br]embedded platforms, like power analysis 0:54:08.440,0:54:13.930 and that kind of thing. So this is also[br]still highly investigated. And then if you 0:54:13.930,0:54:18.350 go for that kind of implementation, you[br]should have a masked implementation. So 0:54:18.350,0:54:25.210 this would be an own talk for itself. Like[br]I don't want to like now give you two 0:54:25.210,0:54:30.280 verbs what you should do and then say that[br]it's secure. I mean, it's a bit more 0:54:30.280,0:54:38.590 complicated than that. So I can't really[br]say now do this do that. I can just say on 0:54:38.590,0:54:45.170 the spectrum from easy to difficult, Kyber[br]is more on the spectrum of easier to 0:54:45.170,0:54:50.970 implement securely. But if you're[br]interested in that, look up the 0:54:50.970,0:54:55.650 implementations. There's a reference[br]implementation. There's a PQClean and 0:54:55.650,0:55:01.810 stuff. Look up the implementations online[br]and look into that and the specification 0:55:01.810,0:55:07.550 that is linked in the block post, that is[br]linked on the slides. There are also some 0:55:07.550,0:55:17.110 points that say what you maybe should,[br]where you should be careful lets say. 0:55:17.110,0:55:23.600 Herald: OK. And there was just an[br]additional question as well, and that is 0:55:23.600,0:55:28.900 what is the status of Kyber in OpenSSL and[br]GnuTLS? 0:55:28.900,0:55:42.400 Ruben: Okay, so we see adoption in crypto[br]libraries, but OpenSSL. OK, I don't want 0:55:42.400,0:55:53.610 to hate, but OpenSSL codebase is, how do I[br]say that? Look, it's a bit complex and a 0:55:53.610,0:56:04.140 bit difficult for outsiders to get what[br]OpenSSL is doing in certain corners of 0:56:04.140,0:56:11.770 their code base. But there's a project[br]called OpenOQS, no liboqs that is a fork 0:56:11.770,0:56:18.800 of OpenSSL, including post-quantum[br]schemes, but not only Kyber, but various 0:56:18.800,0:56:24.630 schemes. That's liboqs, its a OpenSSL[br]fork. Now there are other libraries, for 0:56:24.630,0:56:34.670 example, WolfSSL, which has a smaller code[br]base and they already have in their actual 0:56:34.670,0:56:40.530 release or in their main branch, let's[br]say, in git, they already have NTLS post- 0:56:40.530,0:56:46.420 quantum schemes, and Kyber is one of them.[br]They have lattice based schemes,if I 0:56:46.420,0:56:53.340 remember correctly: Kyber, Dilithium, and[br]Falcon. So they already have it included. 0:56:53.340,0:57:00.040 WolfSSL , OpenSSL as I said there is a[br]fork that are like benchmarking and 0:57:00.040,0:57:08.870 testing stuff in the hopes of later being[br]able to return it to OpenSSL. But as I 0:57:08.870,0:57:14.960 said OpenSSL is not exactly ideal for[br]experimentation, becourse the code base is 0:57:14.960,0:57:23.080 quite large and in some corners, quite[br]complex to comprehend and so on. Other 0:57:23.080,0:57:30.590 libraries are a little faster. I don't[br]know of any efforts for GnuTLS to be 0:57:30.590,0:57:35.280 honest, but I haven't looked into it yet.[br]It's possible that somebody else did 0:57:35.280,0:57:42.740 something there. I mean, I've I've worked[br]with WolfSSL before and with OpenSSL. But 0:57:42.740,0:57:53.650 GnuTLS I'm not sure. There are talks to[br]include it in GnuPG which you can use for 0:57:53.650,0:57:59.490 email encryption, and there are some[br]there's some progress there. But yeah, 0:57:59.490,0:58:07.960 GnuTLS I don't know.[br]Herald: All right, OK. This brings us to 0:58:07.960,0:58:15.920 our really final question, which is how[br]close are the current cloud quantum 0:58:15.920,0:58:24.270 offerings to be able to enable users to[br]break current public key cryptography? 0:58:24.270,0:58:31.050 Ruben: If I understand it correctly, Krijn[br]you can also say something if you want, if 0:58:31.050,0:58:37.430 I understand correctly, it's the question[br]is general. If I can use cloud computing 0:58:37.430,0:58:43.340 to break public key crypto?[br]Herald: No, the question is more specific, 0:58:43.340,0:58:48.000 there are quantum offerings by public[br]cloud providers like Amazon right now, 0:58:48.000,0:58:54.110 apparently. At least that's what I assume[br]the person who asking the question is 0:58:54.110,0:59:00.090 basing it on. And the question is, to what[br]extent are those available options usable 0:59:00.090,0:59:04.100 to break current public key cryptography[br]schemes? 0:59:04.100,0:59:08.680 Ruben: So if I understand the question[br]correctly is like, already deployed 0:59:08.680,0:59:14.840 quantum computers, are they a threat to[br]pre-quantum schemes? OK, so far, they are 0:59:14.840,0:59:23.050 not like there are quantum computers in[br]use, but they don't have nearly enough 0:59:23.050,0:59:32.930 qbits to break any real word schemes, so[br]it's also more complicated than that 0:59:32.930,0:59:37.150 because you don't only need qbits, you[br]also need quantum registers that are large 0:59:37.150,0:59:41.480 enough because you need to entangle all of[br]the qbits. I mean, there we are going to 0:59:41.480,0:59:46.110 quantum mechanics, but you need to[br]entangle the bits and all that kind of 0:59:46.110,0:59:52.000 quantum craziness. And then you also need[br]error correction that's good enough. So 0:59:52.000,1:00:00.020 there are still, there are still technical[br]like engineering problems that you need to 1:00:00.020,1:00:03.890 overcome, like in theory it's all fine and[br]stuff, but there's some engineering 1:00:03.890,1:00:08.290 efforts that you need to overcome, and the[br]currently deployed quantum computers are 1:00:08.290,1:00:16.430 not big enough to be a threat to quantum,[br]to pre-quantum schemes unless you have 1:00:16.430,1:00:23.920 some toy keysums. But for real[br]deployments, it's not a threat yet, but it 1:00:23.920,1:00:28.080 might be within the next couple of years.[br]It's really difficult to foresee the 1:00:28.080,1:00:35.000 development there and the largest quantum[br]computers are actual quantum annealers 1:00:35.000,1:00:39.210 that work differently, like quantum[br]annealing is a different thing, a 1:00:39.210,1:00:42.770 different kind of quantum computer that[br]we're not too worried about right now. 1:00:42.770,1:00:46.990 Like thats D-Wave for example. But yeah,[br]so right now, they're not a threat, but 1:00:46.990,1:00:53.400 they might be in the near future.[br]Krijn: And especially so with regards to 1:00:53.400,1:00:59.930 why you still switch to post-quantum[br]crypto, is this idea that well, 1:00:59.930,1:01:03.641 standardizing crypto and then integrating[br]crypto and all of this takes years, as we 1:01:03.641,1:01:08.290 know from that transition to elliptic[br]curve crypto. So even if this quantum 1:01:08.290,1:01:13.780 computer is 10 15 years away then still[br]this whole transition thing will take so 1:01:13.780,1:01:20.480 long that by the end of it, how long will[br]your original data have been safe for? 1:01:20.480,1:01:25.900 It's anybody's guess.[br]Ruben: Yeah. I mean, you have to see 1:01:25.900,1:01:30.420 asymmetric crypto is everywhere. Like, for[br]example, also kind of example maybe in my 1:01:30.420,1:01:34.730 passport, like my travel document. And[br]there are documents, for example, out 1:01:34.730,1:01:40.560 there that are valid for 10 years like, I[br]think, a proper passport and all that kind 1:01:40.560,1:01:44.610 of stuff. And of course, it really takes[br]long also with these kinds of things, like 1:01:44.610,1:01:50.670 documents like that are issued by[br]governments. It just takes time, it takes 1:01:50.670,1:01:57.460 a lot of time.[br]Herald: OK, thank you very much. I should 1:01:57.460,1:02:01.700 also note that from the signal angel,[br]there have been several very enthusiastic 1:02:01.700,1:02:06.200 responses from the audience and not so[br]much questions about your talk, that's 1:02:06.200,1:02:09.720 also very interesting. So thank you so[br]much for doing this, and maybe see you 1:02:09.720,1:02:11.720 around.[br]Krijn: Thank you. 1:02:11.720,1:02:16.530 Ruben: Bye bye! 1:02:16.530,1:02:37.320 rc3 postroll music 1:02:37.320,1:02:41.000 Subtitles created by c3subtitles.de[br]in the year 2021. Join, and help us!