1 00:00:00,000 --> 00:00:25,750 rc3 preroll music 2 00:00:25,750 --> 00:00:32,969 Herald: Good afternoon everyone watching, the upcoming talk is by Ruben Gonzalez and 3 00:00:32,969 --> 00:00:36,750 Krijn Reijnders, they're both Ph.D. students at Radboud University, and Ruben 4 00:00:36,750 --> 00:00:42,160 is also a capture-the-flag player, under the name "Red Rocket", or affiliated with 5 00:00:42,160 --> 00:00:47,780 "Red Rocket". Their talk will me about post-quantum cryptography. And we'll take 6 00:00:47,780 --> 00:00:53,070 a kind of introductory dive into Kyber. This talk will also be live-translated 7 00:00:53,070 --> 00:00:58,980 into German, so if you don't speak German, don't despair. Dieser Vortrag wird also 8 00:00:58,980 --> 00:01:05,910 übersetzt simultan in Deutsch, and that's also the extent of my German. Also, this 9 00:01:05,910 --> 00:01:10,959 talk is prerecorded will last a bit over 30 minutes, but the Q&A will be live 10 00:01:10,959 --> 00:01:13,349 afterwards. So enjoy. 11 00:01:13,349 --> 00:01:16,700 Ruben Gonzalez: Hello, and welcome to our presentation on Kyber and post-quantum 12 00:01:16,700 --> 00:01:24,110 cryptography. How does it work? First, my name is Ruben Gonzalez, I'm a Ph.D. 13 00:01:24,110 --> 00:01:27,420 student in the Netherlands. I'm doing this presentation together with my colleague 14 00:01:27,420 --> 00:01:35,590 Krijn Reijnders, and we'll be teaching you all about Kyber today. So, first things 15 00:01:35,590 --> 00:01:40,179 first, a small disclaimer, because I don't want to disappoint any people: We're doing 16 00:01:40,179 --> 00:01:46,259 boomer crypto here, so we won't be talking about blockchain, NFTs, shitcoins,... at 17 00:01:46,259 --> 00:01:52,631 all. Instead, we're going to bore you with mathematics, weird kinds of key pairs, and 18 00:01:52,631 --> 00:02:01,970 U.S. government agencies. So, our talk is divided into four segments. First, I'm 19 00:02:01,970 --> 00:02:06,530 going to teach you a little bit about what post-quantum cryptography actually is and 20 00:02:06,530 --> 00:02:11,540 why you should care about it. Then we're going to talk about Kyber, which is the 21 00:02:11,540 --> 00:02:15,860 scheme we're going to go into detail about, because it's just about to take 22 00:02:15,860 --> 00:02:20,320 over the world. And then Kreijn will talk to you a little bit more about the 23 00:02:20,320 --> 00:02:25,560 security guarantees about how the system actually works mathematically. And then 24 00:02:25,560 --> 00:02:32,730 we're going to give you a brief outlook on the future of crypto and where we're 25 00:02:32,730 --> 00:02:44,349 headed in the field. So, post-quantum crypto. A little bit of basics here: 26 00:02:44,349 --> 00:02:50,390 Today, cryptography, on a high level, is divided into two parts; a boring part and 27 00:02:50,390 --> 00:02:56,120 an exciting part. So the boring part is called symmetric crypto and symmetric 28 00:02:56,120 --> 00:03:01,469 crypto does what you usually expect from cryptography. So you can encrypt stuff 29 00:03:01,469 --> 00:03:06,209 with it and sometimes you do authentication with it. But the biggest 30 00:03:06,209 --> 00:03:12,249 part is the encryption stuff. So you have a secret team that nobody is allowed to 31 00:03:12,249 --> 00:03:16,249 have, and if you have this secret key you can encrypt things, and another person 32 00:03:16,249 --> 00:03:24,300 that has the same secret you can decrypt with it. So that's why it's symmetric - 33 00:03:24,300 --> 00:03:29,480 you have one key for encryption and decryption. And what you actually use 34 00:03:29,480 --> 00:03:36,999 implementation wise, is almost exclusively AES encryption encryption or hash 35 00:03:36,999 --> 00:03:42,840 functions that are from the SHA family and it's a symmetric world. That's a symmetric 36 00:03:42,840 --> 00:03:47,590 side of things. Now you also have asymmetric crypto because if you look at 37 00:03:47,590 --> 00:03:54,040 symmetric crypto, you have this secret key, but you don't actually have a way of 38 00:03:54,040 --> 00:03:59,799 getting two parties having the same secret key. And it's where asymmetric crypto 39 00:03:59,799 --> 00:04:05,530 comes into play. So, you can use asymmetric crypto, among other things, to 40 00:04:05,530 --> 00:04:14,540 exchange this secret key. So asymmetric crypto uses a key pair: a public key that 41 00:04:14,540 --> 00:04:23,950 everybody can have and a secret key that only the recipient can have. So. Yeah, 42 00:04:23,950 --> 00:04:29,810 essentially with the public key you encrypt, for example, the symmetric key, 43 00:04:29,810 --> 00:04:36,530 and with the private key you decrypt, and here it feels a bit more difficult. 44 00:04:36,530 --> 00:04:41,840 There's not only two algorithms that are being used, but there's an entire zoo of 45 00:04:41,840 --> 00:04:51,180 algorithms used. So, let's look at the zoo real quick. Probably some of these terms 46 00:04:51,180 --> 00:04:57,449 you've already heard: Curve25519 is pretty big; maybe you've used RSA before, Diffie- 47 00:04:57,449 --> 00:05:04,340 Hellman, that sort of thing. So there's this big zoo of different kinds of schemes 48 00:05:04,340 --> 00:05:10,670 in asymmetric crypto that it can use for different things. Sometimes there are 49 00:05:10,670 --> 00:05:13,770 different schemes that you can use for the same thing, or you can use one scheme for 50 00:05:13,770 --> 00:05:19,190 different things. So it's a bit more complicated to make an overview of the 51 00:05:19,190 --> 00:05:26,220 algorithms. But, if you look at the zoo, people seem to be happy, right? Oh, they 52 00:05:26,220 --> 00:05:30,510 look around, they have a look, things seem to work, it's a happy world. So why would 53 00:05:30,510 --> 00:05:35,120 you want to change that? And in post- quantum crypto, we actually want to change 54 00:05:35,120 --> 00:05:41,699 the asymmetric crypto fundamentally. Well, there's one big problem with this zoo, and 55 00:05:41,699 --> 00:05:48,780 it's not in the zoo, but it's coming for the zoo. So there's this guy, Peter Shore, 56 00:05:48,780 --> 00:05:58,059 and he's threatening the zoo. He's about to destroy it and everything in it. And 57 00:05:58,059 --> 00:06:04,700 why is that? Well, we have this big zoo of asymmetric crypto, right? But if you look 58 00:06:04,700 --> 00:06:11,840 at the different schemes in detail, you actually see that they are only based on 59 00:06:11,840 --> 00:06:17,409 two mathematical problems. And that is integer factorization and the discrete 60 00:06:17,409 --> 00:06:22,349 logarithm. We don't have to we don't have the time to go into much detail on those, 61 00:06:22,349 --> 00:06:27,780 but you have to know that the entire asymmetric crypto zoo is based on two 62 00:06:27,780 --> 00:06:35,679 problems. And, coincidentally, Peter Shore, defined an algorithm, a quantum 63 00:06:35,679 --> 00:06:41,339 algorithm, that breaks those two problems and all cryptography that's based on them. 64 00:06:41,339 --> 00:06:50,940 So all of today's crypto is actually broken if we can use Shore's algorithm. 65 00:06:50,940 --> 00:06:55,880 Now Shore's algorithm is a quantum algorithm. That means we need a large 66 00:06:55,880 --> 00:07:02,380 enough quantum computer for it to work, but once we have that, all asymmatric 67 00:07:02,380 --> 00:07:10,530 crypto is destroyed. And why should you care about that? Well, maybe you use one 68 00:07:10,530 --> 00:07:16,669 of those things here. Well, actually you do, whether you like it or not. You're 69 00:07:16,669 --> 00:07:21,800 watching this stream right now via TLS. Maybe you also use things like SSH or 70 00:07:21,800 --> 00:07:28,580 email encryption or VPNs with IPsec or WireGuard. Well, Shore's algorithm would 71 00:07:28,580 --> 00:07:35,719 break all of those protocols. Everything. And you should care because in the modern 72 00:07:35,719 --> 00:07:41,939 information age, essentially everything is digital communication. All security is 73 00:07:41,939 --> 00:07:48,630 virtually based on cryptography, so, if Shorezilla and breaks everything, we do 74 00:07:48,630 --> 00:07:55,099 have a huge problem. So the natural question that arises is: "when will we 75 00:07:55,099 --> 00:08:02,610 have large quantum computers?" And the answer is: "we don't know." Different 76 00:08:02,610 --> 00:08:12,360 experts say different things. The opinions vary from within five years to never. But 77 00:08:12,360 --> 00:08:15,970 the truth is, nobody knows. We can't see in the future. We don't have a magic eight 78 00:08:15,970 --> 00:08:21,401 ball there. But we should definitely be prepared for the large quantum computer 79 00:08:21,401 --> 00:08:26,680 because we don't want all of our information security to be broken when, 80 00:08:26,680 --> 00:08:33,430 let's say, a large U.S. government agency all of a sudden manages to build a quantum 81 00:08:33,430 --> 00:08:41,880 computer. So post-quantum crypto is all about designing asymmetric cryptography 82 00:08:41,880 --> 00:08:48,250 that is unaffected by quantum computers. Or let's say we hope they are. But we're 83 00:08:48,250 --> 00:08:52,950 pretty certain they should be unaffected. They're certainly unaffected by Shore's 84 00:08:52,950 --> 00:08:59,230 algorithm. So now that you know a little bit about what post-quantum cryptography 85 00:08:59,230 --> 00:09:07,450 is about and why we need it, I want to talk about Kyber. Kyber is the post- 86 00:09:07,450 --> 00:09:15,700 quantum scheme that is most likely to be adopted in the near future. So the 87 00:09:15,700 --> 00:09:23,120 asymmetric crypto zoo is threatened - Let's make a new new zoo, where people can 88 00:09:23,120 --> 00:09:32,750 and people can be happy and live their fulfilled lives. The standardization 89 00:09:32,750 --> 00:09:38,310 organization NIST launched a call a couple of years back for new cryptographic 90 00:09:38,310 --> 00:09:44,820 schemes that are resilient against quantum computers. And first schemes are actually 91 00:09:44,820 --> 00:09:53,270 about to be standardized very soon in early 2022. So, we want to look at one 92 00:09:53,270 --> 00:10:00,829 scheme that is about to be standardized, and it's called Kyber. Now why are looking 93 00:10:00,829 --> 00:10:09,730 at exactly that scheme? Well, it's very fast, and the public and private key sizes 94 00:10:09,730 --> 00:10:15,340 are not too big, meaning you can actually use it in real world projects, which is 95 00:10:15,340 --> 00:10:21,200 not always the case for all post-quantum schemes. So it is already, even though 96 00:10:21,200 --> 00:10:26,170 it's not, it's standardized, it has already seen some adoption in industry. 97 00:10:26,170 --> 00:10:31,730 And it's a lattice-based scheme. And right now it looks a little bit like lattice is 98 00:10:31,730 --> 00:10:36,149 going to be the future. If you don't know what a lot of space scheme is, that's 99 00:10:36,149 --> 00:10:44,220 really fine; Krijn is going to tell you in the end. So, that was the fun part of our 100 00:10:44,220 --> 00:10:48,610 presentation, the easygoing part. Now we need to roll up our sleeves, we need to 101 00:10:48,610 --> 00:10:56,630 get our hands dirty and we need some mathematics. And for that, I'm going to 102 00:10:56,630 --> 00:11:03,850 give the mic - turn over to Krijn. (How do you say that? Give it to Krijn? I don't 103 00:11:03,850 --> 00:11:08,139 know.) Bye. Krijn Reijnders: So, now we need maths. So 104 00:11:08,139 --> 00:11:13,110 let's start. What we need in Kyber are polynomials, and we need to work with 105 00:11:13,110 --> 00:11:17,959 polynomials. But actually, you can think of polynomials just like you do of as 106 00:11:17,959 --> 00:11:23,510 numbers. What do I mean with that? I mean that you can just multiply them and you 107 00:11:23,510 --> 00:11:29,970 can also just add them together like you do with numbers. And just as we do with 108 00:11:29,970 --> 00:11:35,479 numbers in pre- quantum cryptography, when they get too big, we reduced them. We do 109 00:11:35,479 --> 00:11:40,970 this modulo operation. We'll do the same for the coefficients in the polynomials, 110 00:11:40,970 --> 00:11:45,360 but also, when the degree of a polynomial gets too big, we will reduce them by 111 00:11:45,360 --> 00:11:51,110 another polynomial. So we have a modulo operation with polynomials, and in this 112 00:11:51,110 --> 00:11:56,600 way you can do all kinds of things with polynomials. And that's actually all of 113 00:11:56,600 --> 00:12:01,720 the mathematics that we all need fundamentally to work with Kyber. What do 114 00:12:01,720 --> 00:12:06,900 I mean by that? Well, if you can do multiplication and addition, then you can 115 00:12:06,900 --> 00:12:11,730 also do these things like we do for numbers with matrices and vectors, so we 116 00:12:11,730 --> 00:12:17,399 can multiply a matrix with a vector and add another vector. And this works the 117 00:12:17,399 --> 00:12:21,490 same for these polynomials, so you can have a matrix full of polynomials and a 118 00:12:21,490 --> 00:12:25,930 vector full of polynomials, and you can just multiply them together, add another 119 00:12:25,930 --> 00:12:30,380 vector. It's just this basic operation of multiplication and addition of 120 00:12:30,380 --> 00:12:37,760 polynomials. It looks a bit more complicated, but that's it. And then, 121 00:12:37,760 --> 00:12:42,209 let's say we do this, we have a matrix and we multiplied by a vector and we add 122 00:12:42,209 --> 00:12:46,421 another small vector. Now if I give you the end result of this computation, and I 123 00:12:46,421 --> 00:12:51,769 give you this matrix that we started with, it's actually very hard to recover the 124 00:12:51,769 --> 00:12:56,140 vector that we've multiplied the matrix with. And this is the fundamental problem 125 00:12:56,140 --> 00:13:02,199 that we need in Kyber. And it's called module-learning-with-errors. I know this 126 00:13:02,199 --> 00:13:06,779 name does not make a lot of sense, but apparently mathematicians thinks it does 127 00:13:06,779 --> 00:13:15,110 aptly describe the problem. So this matrix, we call it 'A', this secret vector 128 00:13:15,110 --> 00:13:19,440 of ours, we call it 's', then we need to add a small error term so that it's not 129 00:13:19,440 --> 00:13:24,000 too easy to solve this problem, and then we get a public value again, which we call 130 00:13:24,000 --> 00:13:32,699 't'. This gets you the equation A times s plus e equals t. And then the public key 131 00:13:32,699 --> 00:13:38,730 pair is this matrix 'A' and this end result 't', and the private key is our 132 00:13:38,730 --> 00:13:45,629 secret vector, 's'. That's all that we need to generate a key pair in Kyber. We 133 00:13:45,629 --> 00:13:48,889 need to ensure actually that the private key pair has small coefficient, and that 134 00:13:48,889 --> 00:13:55,570 also makes it very compact to transmit. And also, this error has small 135 00:13:55,570 --> 00:14:01,570 coefficients. For the rest of the presentation: These error terms, they are 136 00:14:01,570 --> 00:14:05,170 necessary, but they complicate the equations are a bit too, so we'll just 137 00:14:05,170 --> 00:14:09,540 write them in emojis so that you know what the errors are and what are the important 138 00:14:09,540 --> 00:14:15,730 values, and now Ruben will explain again: How can we encrypt and decrypt messages 139 00:14:15,730 --> 00:14:21,680 using such a public and private key pair? R.G.: OK, our Boomer is back, and he wants 140 00:14:21,680 --> 00:14:28,550 to encrypt something. So, as an example, he wants to encrypt the letter C. So C is 141 00:14:28,550 --> 00:14:33,720 not a variable, it's literally the letter "C" that he wants to encrypt. And as we 142 00:14:33,720 --> 00:14:38,580 learned earlier, to encrypt something, we need the public key. So we have this 143 00:14:38,580 --> 00:14:48,079 public key, which is the matrix A and the vector t. So first, we need to transform 144 00:14:48,079 --> 00:14:52,839 the letter "C" into some form that Kyber can work with because we want to encrypt 145 00:14:52,839 --> 00:14:58,709 it with Kyber. So let's first break it down into binary, right, in a computer, 146 00:14:58,709 --> 00:15:04,790 everything is binary anyways, so let's say we used to ASCII encoding. So we turn the 147 00:15:04,790 --> 00:15:10,230 letter "C" into a series of ones and zeros. In this case, it's one zero zero 148 00:15:10,230 --> 00:15:16,610 zero zero one one. Now we have binary representation, but Kyber uses those 149 00:15:16,610 --> 00:15:21,550 polynomials, right? So we have to somehow turn this into a polynomial, which turns 150 00:15:21,550 --> 00:15:28,620 out to be quite simple. So we just do a binary polynomial, so we take the ones and 151 00:15:28,620 --> 00:15:34,970 zeros and use them as coefficients for a polynomial. In this case, you can see the 152 00:15:34,970 --> 00:15:43,089 polynomial on the slides, quite simple. So one bit is one polynomial coefficient. 153 00:15:43,089 --> 00:15:48,569 Since zero times something is just zero, which is just leave out the zero terms and 154 00:15:48,569 --> 00:15:54,050 shrink our polynomial a bit. So we now have a plain text and we can use within 155 00:15:54,050 --> 00:15:58,770 Kyber, right? The plaintext is a polynomial "x to the power of six plus x 156 00:15:58,770 --> 00:16:04,880 plus one". That's our plain text. We haven't encrypted anything yet, but we 157 00:16:04,880 --> 00:16:10,720 have a plain text. So now let's us Kyber to encrypt the plain text polynomial. 158 00:16:10,720 --> 00:16:17,480 First, we have to scale it. We have to make our polynomial big. And we do that 159 00:16:17,480 --> 00:16:22,760 simply by multiplying the polynomial with a large factor. So here I chose 1337, it's 160 00:16:22,760 --> 00:16:29,839 arbitrary, depends on the Kyber instance, but we just multiply every polynomial 161 00:16:29,839 --> 00:16:37,470 coefficient with the large number 1337. So we have the same polynomial, but with 162 00:16:37,470 --> 00:16:44,850 larger coefficients. So our scale plaintext is 1337 x to the power of, and 163 00:16:44,850 --> 00:16:51,890 so on and so on. So now we do the actual encryption, which in Kyber, it's actually 164 00:16:51,890 --> 00:16:57,730 quite simple. We just sprinkle in some error terms. As Krijn mentioned earlier, 165 00:16:57,730 --> 00:17:03,810 in our presentation, small error terms are represented as emojis. Because they're not 166 00:17:03,810 --> 00:17:09,110 that important, but you should still know they're there. So our ciphertext is 167 00:17:09,110 --> 00:17:16,440 actually just two values, v, which is a polynomial and u, which is a vector of 168 00:17:16,440 --> 00:17:24,640 polynomials. So, v is the key value from the public key, multiplied and added with 169 00:17:24,640 --> 00:17:35,350 error terms, and then the actual scale plaintext message is added as well. u is a 170 00:17:35,350 --> 00:17:40,190 matrix from the public key, multiplied with an error term and an added error 171 00:17:40,190 --> 00:17:46,870 term. You can see the carrot error term appears in both equations. And that's it. 172 00:17:46,870 --> 00:17:53,600 That's our encryption. (v,u) is the encryption of our plaintext. So doing only 173 00:17:53,600 --> 00:17:58,049 encryption would be kind of boring. We probably also want to decrypt stuff. So, 174 00:17:58,049 --> 00:18:03,950 how do we do that in Kyber? Well, we need the private key, right? Public key 175 00:18:03,950 --> 00:18:10,590 encrypts, private key decrypts. So we have our ciphertext, those two values v and u. 176 00:18:10,590 --> 00:18:17,220 And in order to decrypt, we first remove the public key from it. And we do that 177 00:18:17,220 --> 00:18:25,140 just by taking v minus the private key, multiplied by u. And if I spell out the 178 00:18:25,140 --> 00:18:34,100 equations, they become quite long. But as you can see, if you think about the emojis 179 00:18:34,100 --> 00:18:40,289 as error terms is that most of the public key, or actually the entire public key, 180 00:18:40,289 --> 00:18:49,480 kind of cancels out. So, and d, here on the slide, is the end result of the 181 00:18:49,480 --> 00:18:59,900 calculations of v minus private key times u. And so we have our message in d, which 182 00:18:59,900 --> 00:19:04,020 is the plain text, but we also have these error terms laying around and the private 183 00:19:04,020 --> 00:19:12,380 key. Now one core observation is important. I mentioned earlier that error 184 00:19:12,380 --> 00:19:19,309 terms are all small, meaning they're polynomials with small coefficients. And 185 00:19:19,309 --> 00:19:25,580 the private key also has polynomials with small coefficients. So here on the slide, 186 00:19:25,580 --> 00:19:32,140 everything on the right side is actually small, but our plain text is large because 187 00:19:32,140 --> 00:19:39,110 we scaled it earlier. We multiplied it with a large number 1337. So simply by 188 00:19:39,110 --> 00:19:46,169 kind of rounding everything, we get our scaled plaintext back, because these terms 189 00:19:46,169 --> 00:19:56,830 are small. So just by rounding, we get our scaled plaintext back. And then we have 190 00:19:56,830 --> 00:20:02,990 essentially decrypted. What we now have to do is just turn it back into the original 191 00:20:02,990 --> 00:20:11,590 text, so we scale down, divide every coefficient by 1337. We bring back to zero 192 00:20:11,590 --> 00:20:19,350 terms, so every coefficient that is not in the polynomial has a zero. Yeah, every 193 00:20:19,350 --> 00:20:23,450 term that is not in the polynomial has a zero coefficient. So we bring back the 194 00:20:23,450 --> 00:20:28,850 zeros and then from the binary polynomial, we can just read out the ones and zeros 195 00:20:28,850 --> 00:20:37,000 from the coefficients. We have back binary code and this binary now we can decode 196 00:20:37,000 --> 00:20:46,230 again using the ASCII, for example, and we have our plaintext back. And that's how 197 00:20:46,230 --> 00:20:54,150 Kyber decrypts. And then we can decode the Kyber plaintext into your original 198 00:20:54,150 --> 00:21:01,169 message, which was a "C". So how does Kyber looks like for the home consumer? 199 00:21:01,169 --> 00:21:06,690 Well, Kyber comes in three flavors, three different security levels. There's 200 00:21:06,690 --> 00:21:15,620 Kyber512 until Kyber1024. So, in cryptography usually security is measured 201 00:21:15,620 --> 00:21:22,700 in bits. Sometimes it's related to how strong AES is. So the lowest acceptable 202 00:21:22,700 --> 00:21:30,440 acceptable security level for us is 128 bit and the strongest security level we 203 00:21:30,440 --> 00:21:38,390 use in practice is 256 bit. So Kyber512 has around 128 bit security and Kyber1024 204 00:21:38,390 --> 00:21:48,700 as around 256 bit of security. Now that's what the end user needs to know. But I 205 00:21:48,700 --> 00:21:52,630 also want to show you what these securities actually mean in terms of 206 00:21:52,630 --> 00:21:58,240 Kyber, because Kyber instances are mainly defined by three variables: n, k, and q. 207 00:21:58,240 --> 00:22:04,710 And what do those mean? Well, n just means the degree of the polynomials used within 208 00:22:04,710 --> 00:22:14,529 Kyber. So 256 means we have exponents x to the power of maximum 256. So polynomials 209 00:22:14,529 --> 00:22:25,230 are quite large. 256 coefficients we can store. k means the size of the vector. So 210 00:22:25,230 --> 00:22:29,410 as you've seen, Kyber uses not only polynomials, but also vectors of 211 00:22:29,410 --> 00:22:38,350 polynomials. So essentially lists of multiple polynomials. And in Kyber, the k 212 00:22:38,350 --> 00:22:46,200 variable says how many polynomials are in such a vector. q is the modulus for the 213 00:22:46,200 --> 00:22:55,690 numbers. I mean, we have coefficients, right? And how big can this coefficients get? 214 00:22:55,690 --> 00:23:03,350 So the largest coefficient that is used within Kyber would be 3328 because we take 215 00:23:03,350 --> 00:23:10,780 it modulo 3329. So as you can see, in Kyber, we don't have to deal with big 216 00:23:10,780 --> 00:23:15,950 numbers, actually. We have to do with a pre-quantum cryptography, we have to deal 217 00:23:15,950 --> 00:23:25,480 a lot with huge numbers. Here, the numbers are not that big. Also important is size 218 00:23:25,480 --> 00:23:33,360 to speed tradeoffs. Now here you can see a bar chart of public key, private key and 219 00:23:33,360 --> 00:23:42,330 ciphertext sizes of an elliptic curve scheme, Curve25519, RSA, and kyber in 220 00:23:42,330 --> 00:23:47,120 smallest security level. So those three security schemes are the same security 221 00:23:47,120 --> 00:23:52,450 level, but as you can see, elliptic curve crypto is really tiny, RSA is somewhat 222 00:23:52,450 --> 00:23:58,610 bigger, an Kyber is even bigger. But if we go to the highest security level, you see 223 00:23:58,610 --> 00:24:09,970 that Kyber is actually very comparable to RSA. However, ecc is still a lot smaller. 224 00:24:09,970 --> 00:24:15,460 But you don't only care about sizes, you also care about speed, you care about 225 00:24:15,460 --> 00:24:24,070 speed even more. And if we compare the same security level in Kyber, in elliptic 226 00:24:24,070 --> 00:24:30,330 curve crypto and in RSA, we can see that Kyber is on fire. Kyber is really, really 227 00:24:30,330 --> 00:24:37,899 fast. So we can throw out RSA and just compare elliptic curve crypto to Kyber, 228 00:24:37,899 --> 00:24:44,090 and we can see Kyber is even faster than elliptic crypto, which is quite impressive 229 00:24:44,090 --> 00:24:49,649 because ellipctic crypto is already quite fast. And, even more, we can see that the 230 00:24:49,649 --> 00:24:55,730 highest security level of Kyber is faster than the lowest security level of elliptic 231 00:24:55,730 --> 00:25:04,800 curve crypto. So Kyber - fast as hell. I know benchmarks are difficult. We have 232 00:25:04,800 --> 00:25:13,490 different kinds of platforms, but as an intuition: Kyber is really fast. So the 233 00:25:13,490 --> 00:25:18,510 thing I want to mention is that Kyber source code is available online. You can 234 00:25:18,510 --> 00:25:24,700 download it from GitHub, for example, from the PQClean Project, which has AVX 235 00:25:24,700 --> 00:25:34,679 optimized implementations for desktop CPUs, from the pqm4 project, which is the 236 00:25:34,679 --> 00:25:40,160 optimized implementation for ARM-based embedded processors, or there's also a 237 00:25:40,160 --> 00:25:48,100 reference C implementation in the pq- crystals project. And, last but not least, 238 00:25:48,100 --> 00:25:52,830 the specification, the documentation, the code, everything is licensed under 239 00:25:52,830 --> 00:25:58,860 Creative Commons zero, meaning that it's public domain. So there is zero license or 240 00:25:58,860 --> 00:26:03,950 patenting issues with Kyber, it's just public domain. You can clone and do 241 00:26:03,950 --> 00:26:10,780 whatever you want with it. It's quite nice. So that was it about Kyber, now 242 00:26:10,780 --> 00:26:16,870 Krijn is going to tell you more about what actually lattices are and why Kyber is 243 00:26:16,870 --> 00:26:27,110 actually secure the way it is. Krijn: OK, so that was Kyber. And we've 244 00:26:27,110 --> 00:26:30,860 been talking a lot about polynomials, but we haven't talked so much yet about 245 00:26:30,860 --> 00:26:35,880 lattices. But we did say that Kyber was a lattice based scheme. So what do lattices 246 00:26:35,880 --> 00:26:39,539 have to do with all of this polynomial stuff? And why do we think it's secure 247 00:26:39,539 --> 00:26:45,419 because of this being lattice based? Well, let's go back to these numbers that we 248 00:26:45,419 --> 00:26:49,659 used for a second, just because they make these things more understandable and 249 00:26:49,659 --> 00:26:56,000 intuitive. We had this matrix multiplication. We multiplied the matrix 250 00:26:56,000 --> 00:27:00,170 with a vector. Now let's say we do this for numbers, right? We have this matrix 251 00:27:00,170 --> 00:27:05,400 13, 4, 2, 9 and we multiplied by a, b. Well, actually, what you could also see 252 00:27:05,400 --> 00:27:13,250 here is that you multiply the vector 13 over 2 a times and then add the vector 4 253 00:27:13,250 --> 00:27:17,789 over 9 b times. And as you see in the image, like, you can make different 254 00:27:17,789 --> 00:27:22,549 combinations of that. So if you take a = 1 and b = 1, you get the point on the top 255 00:27:22,549 --> 00:27:29,529 right corner and then you can do this for a = 2 and b = 1, then 3 and 4 infinitely. 256 00:27:29,529 --> 00:27:35,149 And then you would get all of these dots spread out over the cartesian plane, and 257 00:27:35,149 --> 00:27:39,640 it would go on infinitely in these dimensions. So you would get infinite 258 00:27:39,640 --> 00:27:49,740 number of points just by giving these two original vectors 13, 2 and 4, 9. Now, our 259 00:27:49,740 --> 00:27:54,929 secret key s was just actually then a way to pick one of these points, because we 260 00:27:54,929 --> 00:27:58,990 said, well, the Matrix a that we had in the public key, it describes some sort of 261 00:27:58,990 --> 00:28:06,309 lattice. And then the secret key s described actually a specific point: a 262 00:28:06,309 --> 00:28:11,240 number of times the first vector, plus a number of times the second vector. Then 263 00:28:11,240 --> 00:28:16,159 what does this error term do? Well, you know, it shifts just a bit from this 264 00:28:16,159 --> 00:28:22,600 lattice point that we were at and then we get the end result t over there. And now 265 00:28:22,600 --> 00:28:28,740 it's very difficult actually to get back from t to this vector s. We know that it's 266 00:28:28,740 --> 00:28:35,810 the closest vector to this given point t in this lattice described by a. But this 267 00:28:35,810 --> 00:28:40,200 problem of finding the closest vector in the lattice and in a random letters is 268 00:28:40,200 --> 00:28:44,840 actually very hard. And this is what we call the closest vector problem, which is 269 00:28:44,840 --> 00:28:51,149 a very good name because we're looking for the closest vector. So for this two 270 00:28:51,149 --> 00:28:56,220 dimensional example, we had the matrix e and the vector t in the public key, and we 271 00:28:56,220 --> 00:29:01,519 had the vector s in the private key and that was hidden by this small error term. 272 00:29:01,519 --> 00:29:07,850 So to recap: a gives you these initial vectors, which you can use to describe the 273 00:29:07,850 --> 00:29:13,909 lattice, s gives you a secret point in that lattice. The error makes sure that 274 00:29:13,909 --> 00:29:20,460 you're close to a lattice point, but not too far away. And then we get the end 275 00:29:20,460 --> 00:29:24,890 result t, which is this public point and then getting back from this information of 276 00:29:24,890 --> 00:29:32,230 this lattice and t to s is the closest vector problem, in a nutshell. You may be 277 00:29:32,230 --> 00:29:37,870 thinking now, OK, this is for numbers I can see this right. It's just these dots 278 00:29:37,870 --> 00:29:44,200 in this plane. For dimension two OK, I get it. For Dimension three you can think of a 279 00:29:44,200 --> 00:29:50,840 third dimension. Though we were talking about dimension n way larger than 3 and 280 00:29:50,840 --> 00:29:56,019 polynomials instead of numbers. And how do we visualize this? And the truth is we 281 00:29:56,019 --> 00:30:02,090 don't actually, but we do know how to compute it, which was just this 282 00:30:02,090 --> 00:30:06,840 multiplication and addition of polynomials. So we just compute it and we 283 00:30:06,840 --> 00:30:11,820 kind of think of it as a lattice abstractly, but not visually. Now let's 284 00:30:11,820 --> 00:30:15,840 finish with a short look at the future of asymmetric crypto, and let's go back to 285 00:30:15,840 --> 00:30:20,610 the post-quantum crypto zoo that we had. We already took a look at Kyber, but there 286 00:30:20,610 --> 00:30:25,740 was also other cryptographic primitives such as Rainbow, Falcon, and SABER and 287 00:30:25,740 --> 00:30:29,940 Dilithium, NTRU, McEliece. Among them, there are signature schemes, but also 288 00:30:29,940 --> 00:30:33,871 these key exchange mechanisms. Actually, this zoo is quite different from the one 289 00:30:33,871 --> 00:30:37,690 that we had pre-quantum, the one that we had pre-quantum as we explained was based 290 00:30:37,690 --> 00:30:42,899 on mostly integer factorization and a discrete logarithm problem. But in the 291 00:30:42,899 --> 00:30:48,299 post-quantum setting, we have a variety of problems. We have hash based cryptography, 292 00:30:48,299 --> 00:30:52,149 lattice based cryptography, code based cryptography, multivariate based 293 00:30:52,149 --> 00:30:54,840 cryptography, and isogeny based cryptography. And these are five quite 294 00:30:54,840 --> 00:30:59,750 different flavors of cryptography, with also different underlying mathematical 295 00:30:59,750 --> 00:31:06,220 problems. But post-quantum crypto is coming. For example, Amazon has already 296 00:31:06,220 --> 00:31:11,500 implemented some of the round two candidates, such as Kyber in post-quantum 297 00:31:11,500 --> 00:31:17,960 TLS. And also the BSI, which is the German Ministry for Information Security, has put 298 00:31:17,960 --> 00:31:23,389 out a proposal to integrate post-quantum cryptography into Thunderbird as their 299 00:31:23,389 --> 00:31:28,590 mail client. And even NIST has the following quote that if you haven't 300 00:31:28,590 --> 00:31:33,519 migrated to elliptic curve cryptography yet, don't bother, just directly migrate 301 00:31:33,519 --> 00:31:40,159 to post-quantum crypto. And that wraps up our presentation on post-quantum crypto 302 00:31:40,159 --> 00:31:45,220 and Kyber. If you want to do some further reading, there is a link here to a blog 303 00:31:45,220 --> 00:31:50,920 that goes a bit more in-depth in how Kyber works and has a very small example. Just 304 00:31:50,920 --> 00:31:55,340 as we've shown you in this video. Thank you for your attention and we'll take some 305 00:31:55,340 --> 00:31:58,200 questions now. 306 00:31:58,200 --> 00:32:00,590 Question: So why should I care about this now? 307 00:32:00,590 --> 00:32:05,639 Ruben: Well, that's an excellent question. Well, as we know from the Snowden leaks, 308 00:32:05,639 --> 00:32:16,430 the NSA is currently recording a lot of internet traffic that is encrypted, and 309 00:32:16,430 --> 00:32:20,510 they're recording this encrypted traffic in the hopes of being able to decrypt it 310 00:32:20,510 --> 00:32:25,750 later. For example, using a large quantum computer. So first, we have to care about 311 00:32:25,750 --> 00:32:30,480 this now because our internet traffic is already recorded and could be broken 312 00:32:30,480 --> 00:32:36,970 later. And second, we have to care about this now because transition, especially 313 00:32:36,970 --> 00:32:41,309 when it comes to cryptography, is really slow because standardization takes a lot 314 00:32:41,309 --> 00:32:47,019 of time. Implementation takes a lot of time, and adoption takes a lot of time. So 315 00:32:47,019 --> 00:32:52,050 that's why we have to care now. Question: But are there any downsides? 316 00:32:52,050 --> 00:32:56,250 Krijn: Another very good question. Actually, yeah, there are some downsides, 317 00:32:56,250 --> 00:33:01,940 but they're not too big. Usually, the keys are a bit larger than we are used to. In 318 00:33:01,940 --> 00:33:06,690 some cases even much larger than we are used to. And the speed is a bit worse than 319 00:33:06,690 --> 00:33:14,769 we are used to. In some schemes, even much slower than we are used to. But while this 320 00:33:14,769 --> 00:33:19,570 is already being adopted, it is also still a very active area of research and we are 321 00:33:19,570 --> 00:33:24,970 continuously trying to make the keys smaller and the schemes more efficient. In 322 00:33:24,970 --> 00:33:29,600 the hopes that we in the end, get very efficient schemes that will solve all of 323 00:33:29,600 --> 00:33:33,380 our post-quantum problems. Why didn't you let me eat the lettuce? 324 00:33:33,380 --> 00:33:42,690 Ruben: It's my lettuce! Okay, now eat it for the camera, you can eat one. But it's 325 00:33:42,690 --> 00:33:49,980 not washed. Herald: Okay, thank you. The first 326 00:33:49,980 --> 00:33:54,649 question we got from the internet is: Why are you using seven bit ASCII instead of 327 00:33:54,649 --> 00:33:59,100 Unicode? Ruben: So in that case of the letter c 328 00:33:59,100 --> 00:34:05,340 that wouldn't make a difference anyways. We just prefer to use ASCII because we 329 00:34:05,340 --> 00:34:10,340 really, really want to piss off the European people because all of these 330 00:34:10,340 --> 00:34:17,940 umlauts and that kind of stuff. Of course, they're unnecessary. So ASCII forever. 331 00:34:17,940 --> 00:34:24,810 Herald: I'm surprised that both of us Europeans as well, but let's not get to 332 00:34:24,810 --> 00:34:34,460 the nationalism bit and carry on with the next question, which is, by the way, how 333 00:34:34,460 --> 00:34:40,390 can you compare the security levels according to varying n and varying q, 334 00:34:40,390 --> 00:34:45,880 respectively? Ruben: Sorry, the connection was a bit 335 00:34:45,880 --> 00:34:53,240 lost there. Could you repeat the question? Herald: Of course, can you compare the 336 00:34:53,240 --> 00:34:58,190 security levels according to varying n and varying q, respectively? 337 00:34:58,190 --> 00:35:06,270 Ruben: Yes, of course you can. I'm not sure if I get the question. Of course, 338 00:35:06,270 --> 00:35:13,360 that's how you do it, that's how you compare and you can do that. I'm not sure 339 00:35:13,360 --> 00:35:17,680 if the question asked me to do that right now on the spot because that I couldn't 340 00:35:17,680 --> 00:35:23,390 do, but I mean, it was on the slides, like the security levels that are about to be 341 00:35:23,390 --> 00:35:29,490 standardized, at least. But the one good thing about Kyber, a very good thing that 342 00:35:29,490 --> 00:35:37,050 I want to mention is that, so the polynomials, the size stays the same, the 343 00:35:37,050 --> 00:35:43,820 modulus q stays the same. Only the size of the vectors change. So how many 344 00:35:43,820 --> 00:35:48,460 polynomials you have in a vector. And that makes it quite nice to write optimized 345 00:35:48,460 --> 00:35:54,410 code because most parts of the code are literally the same. If you look at the 346 00:35:54,410 --> 00:36:00,730 implementation, the reference implementation, you can see that it's 347 00:36:00,730 --> 00:36:05,650 actually the same code for all the security levels, just one header changes 348 00:36:05,650 --> 00:36:14,940 that specifies how big the vectors are. So that's quite nice. But you can yeah, you 349 00:36:14,940 --> 00:36:19,820 have for RSA, you have different key sizes. So yeah, it's more difficult to 350 00:36:19,820 --> 00:36:25,760 optimize, but here you can just have the same size as just the vector size changes, 351 00:36:25,760 --> 00:36:31,590 which is nice Herald: What about the potential for 352 00:36:31,590 --> 00:36:37,300 hardware acceleration for Kyber? Could that be possible, feasible? 353 00:36:37,300 --> 00:36:42,720 Ruben: So I am not sure if I just answer that or Krijn also wants to say something, 354 00:36:42,720 --> 00:36:49,200 but hardware acceleration for post-quantum schemes in general is, as we say, a very 355 00:36:49,200 --> 00:36:55,610 active area of research. So these things are very new. There were some people that 356 00:36:55,610 --> 00:37:03,120 tried to use, there's a paper about it, actually - you can look it up on the 357 00:37:03,120 --> 00:37:06,900 internet - to use RSA bignum hardware acceleration for Kyber, which is a quite 358 00:37:06,900 --> 00:37:14,010 interesting idea because you work in completely different things there. But 359 00:37:14,010 --> 00:37:18,280 it's an open question and it's a very active area of research. So if any of the 360 00:37:18,280 --> 00:37:22,410 viewers are interested in that sort of thing, to, I don't know, try out Kyber or 361 00:37:22,410 --> 00:37:29,470 FPGAs or something. Yeah, try it out! So there's a lot of potential there, but it's 362 00:37:29,470 --> 00:37:35,490 also, as I said, very actively researched because it's relatively new and it just 363 00:37:35,490 --> 00:37:45,960 now finds adaptation in industry. Herald: And there's a follow up question 364 00:37:45,960 --> 00:37:50,580 that sort of mirrors it in a way because that question is: T o what extent is this 365 00:37:50,580 --> 00:37:56,390 feasible on embedded architectures with very limited hardware to use Kyber there? 366 00:37:56,390 --> 00:38:06,710 Ruben: So I've been using it on a Cortex M3, which is ARM-based. So usually the 367 00:38:06,710 --> 00:38:14,350 reference platform, we use the Cortex M4 because we want to. Like two experiments 368 00:38:14,350 --> 00:38:18,880 that are reproducible, and you can buy Cortex M4 boards quite cheaply from 369 00:38:18,880 --> 00:38:28,590 various vendors. So it's definitely possible to run Kyber on a Cortex M3. I 370 00:38:28,590 --> 00:38:33,240 mean, there's also a project on GitHub. It's called pqm3, that has Kyber benchmark 371 00:38:33,240 --> 00:38:41,140 for various, yeah M3 boards, but that's definitely possible. What I'm working on 372 00:38:41,140 --> 00:38:51,520 right now is testing it on a Cortex M3 and M4 for also application level, so included 373 00:38:51,520 --> 00:38:59,970 it in TLS or KEMTLS. Or there's a paper about WireGuard using Kyber and Dilithium 374 00:38:59,970 --> 00:39:04,780 for example. That's definitely possible. The question, also active area of research 375 00:39:04,780 --> 00:39:10,480 is, how low can you get? Like, how much can you optimize? Because there are 376 00:39:10,480 --> 00:39:16,870 various tradeoffs, like do we want more space for code but use less RAM and you 377 00:39:16,870 --> 00:39:20,960 also always have these kinds of tradeoffs in the embedded world. And that's 378 00:39:20,960 --> 00:39:24,950 something I'm a little actively looking into right now, actually. But it's 379 00:39:24,950 --> 00:39:33,180 certainly possible to run it on embedded systems. We could also go for a Cortex M0, 380 00:39:33,180 --> 00:39:38,240 which is, like really, really low level, but the cortex M3 is already running on 381 00:39:38,240 --> 00:39:41,800 smartcards. So that's what I'm currently looking at and there it's definitely 382 00:39:41,800 --> 00:39:46,210 possible. But as I said, you have to look into tradeoffs, see how much you want to 383 00:39:46,210 --> 00:39:51,120 waste on ROM, how much you want to waste on RAM and how much time do you have for 384 00:39:51,120 --> 00:39:55,850 the runtime? But the benchmarks we are having there, as I said. Go to Github, 385 00:39:55,850 --> 00:40:01,120 pqm3, already quite good, so it's definitely usable depending on your use 386 00:40:01,120 --> 00:40:10,850 case. I hope that answers the question. Herald: So do I. There's another question 387 00:40:10,850 --> 00:40:15,970 by someone who actually has implemented it. So I just briefly read the questions: 388 00:40:15,970 --> 00:40:21,030 I implemented a raw learning error scheme in an insecure "Hold my beer"-style. It 389 00:40:21,030 --> 00:40:26,110 seems to work, but I see about 1% bit errors in the decrypted text, how do real 390 00:40:26,110 --> 00:40:32,520 implementation handle the expected bit errors in the decryption? 391 00:40:32,520 --> 00:40:41,550 Ruben: So the easy answer is rounding. So you just throw away some of the lowest 392 00:40:41,550 --> 00:40:47,430 bits, but that really depends on the scheme. So if he has done some learning 393 00:40:47,430 --> 00:40:51,740 with errors. So there are different flavors of learning with errors. There's 394 00:40:51,740 --> 00:40:54,390 like ring learning with errors, modulo learning with errors, learning with 395 00:40:54,390 --> 00:41:00,770 errors, and it depends on what he has implemented. But in the end the thing that 396 00:41:00,770 --> 00:41:06,140 seems to work is just throw off the least significant bits, for example, depending 397 00:41:06,140 --> 00:41:12,730 on how many errors you expect. I don't know, Krijn do you want to add something? 398 00:41:12,730 --> 00:41:16,530 Krijn: No, I think you're doing fine with the question. 399 00:41:16,530 --> 00:41:22,150 Ruben: If there's no question I'm going to ask your questions afterwards. Very 400 00:41:22,150 --> 00:41:32,000 personal ones for history. You know? Herald: I shall move on to the next 401 00:41:32,000 --> 00:41:36,490 question, but I think from a layman's perspective, this may also relate to the 402 00:41:36,490 --> 00:41:40,890 last question. The question is: Those sequencing terms are set to be small 403 00:41:40,890 --> 00:41:45,030 relative to the mesh's coefficients. How do you make sure that those do not 404 00:41:45,030 --> 00:41:47,910 compromise encryption and are chosen arbitrarily? 405 00:41:47,910 --> 00:41:53,800 Ruben: So again, I'm really sorry. I had a couple of hiccoughs, so I didn't get the 406 00:41:53,800 --> 00:42:00,960 question could you repeat it? Herald: Sure. The question was: The Secret 407 00:42:00,960 --> 00:42:06,880 key and error terms are set to be small relative to the message coefficients. How 408 00:42:06,880 --> 00:42:10,200 do you make sure that those do not compromise the encryption chosen 409 00:42:10,200 --> 00:42:14,330 arbitrarily? Ruben: OK. I had a hiccough again, Krijn, 410 00:42:14,330 --> 00:42:20,570 did you get the question? Otherwise, I'll answer what I heard. I think what I think 411 00:42:20,570 --> 00:42:31,590 I heard. Krijn: So why are... why don't the 412 00:42:31,590 --> 00:42:35,910 small... the fact that the error and the private key are small, why doesn't this 413 00:42:35,910 --> 00:42:42,910 compromise security? And in fact, well you need the error to be quite small in order 414 00:42:42,910 --> 00:42:46,660 to be able to solve this, this closest vector problem that we've sketched. If the 415 00:42:46,660 --> 00:42:50,640 error is too big then a different vector could be the closest vector than the one 416 00:42:50,640 --> 00:42:57,840 that you want. Now why the private key has to be small. There are some results that 417 00:42:57,840 --> 00:43:02,660 we know that this does not mean... that it doesn't break the security basically of 418 00:43:02,660 --> 00:43:06,900 the scheme. I don't know if , Ruben, you can do a two liner on why that is. 419 00:43:06,900 --> 00:43:11,750 Ruben: So I answer the question always like: we bring in all those error terms. 420 00:43:11,750 --> 00:43:19,610 How do we make sure that the decryption isn't faulty, right? And actually, it's a 421 00:43:19,610 --> 00:43:26,440 very good question, because there's a provable, probably negligible probability 422 00:43:26,440 --> 00:43:32,090 that there will be decryption errors. However, Kyber is fast enough. We handle 423 00:43:32,090 --> 00:43:39,620 them in the KEM Version of Kyber. So what we have introduced here is the public key 424 00:43:39,620 --> 00:43:45,300 encryption version. Standardized as the KEM, which uses internally the public key 425 00:43:45,300 --> 00:43:49,460 encryption version and in the KEM version, you can be sure that this doesn't happen 426 00:43:49,460 --> 00:43:56,250 because, yeah. To answer the question, there's a tiny, tiny but negligible 427 00:43:56,250 --> 00:44:00,850 probability that you have a decryption error, so in that case a very good 428 00:44:00,850 --> 00:44:06,500 question. But if you're really interested, the blog post, I mean, you can download 429 00:44:06,500 --> 00:44:14,770 the slides and there's a blog post. For the talk, let's say, so you can go to the 430 00:44:14,770 --> 00:44:19,770 blog post and there's the Kyber specification reference. They can just 431 00:44:19,770 --> 00:44:27,010 click on the specification and there you can see that it's a fine tuning of 432 00:44:27,010 --> 00:44:35,110 parameters to make sure that the sprinkled in error terms do not invalidate the 433 00:44:35,110 --> 00:44:41,900 decryption to a certain, within a certain probability. And we make that probability 434 00:44:41,900 --> 00:44:47,770 in Kyber so low that in reality it will never happen. Like, 2 to the power of... 435 00:44:47,770 --> 00:44:56,180 lets say magnitude-wise something like atoms on Earth or like to give you an idea 436 00:44:56,180 --> 00:45:00,900 of how big the numbers are there. So it's a very, very low probability that that 437 00:45:00,900 --> 00:45:10,570 will happen. But a very good question. At least thats how I interpreted the 50% of 438 00:45:10,570 --> 00:45:15,560 the question that I heard. Herald: I am sorry that we seem to have a 439 00:45:15,560 --> 00:45:21,060 technical problem. Ruben: I think it's just the shitty 440 00:45:21,060 --> 00:45:27,960 internet at my my parents place. Herald: That could also be the case also 441 00:45:27,960 --> 00:45:32,531 on my end there are troubles as well. The question after that and maybe Krijn can 442 00:45:32,531 --> 00:45:38,350 just start answering it. Would Kyber be broken if someone found a simple solution 443 00:45:38,350 --> 00:45:45,230 to the closest vector problem? Krijn: Yeah, but we that's the case, 444 00:45:45,230 --> 00:45:48,790 that's always the case for encryption. If you managed to solve the fundamental 445 00:45:48,790 --> 00:45:52,810 problem, then the encryption scheme is broken. Luckily for the closest vector 446 00:45:52,810 --> 00:45:57,910 problem, we have a very good, we have quite some trust in this problem, so some 447 00:45:57,910 --> 00:46:04,050 other of these post-quantum schemes are based or more recent problems, so the 448 00:46:04,050 --> 00:46:10,750 closest vector problem is a much older one. So we do trust it, well I have quite 449 00:46:10,750 --> 00:46:15,160 a bit of trust that it won't be easily broken in the coming years. 450 00:46:15,160 --> 00:46:19,570 Ruben: So the answer is it's a bit tricky there, because the close vector problem is 451 00:46:19,570 --> 00:46:25,050 NP hard. So we think this is like a very good problem to start from. But the 452 00:46:25,050 --> 00:46:31,480 question is also like how are these lattices related to certain instanciations 453 00:46:31,480 --> 00:46:36,450 of the closest vector problem? And are these specific closest vector problems 454 00:46:36,450 --> 00:46:41,940 maybe a bit simpler or something? But as Krijn said we're in the closest vector 455 00:46:41,940 --> 00:46:45,380 problem we trust like this is one of the problems in post-quantum crypto that we're 456 00:46:45,380 --> 00:46:49,960 pretty certain about. But yeah, if you would solve it or if you have already 457 00:46:49,960 --> 00:46:56,830 solved it, Kyber would be broken. Herald: That sounds like a potential 458 00:46:56,830 --> 00:47:01,490 inscription on the side of a coin. In the closest vector problem we trust. And 459 00:47:01,490 --> 00:47:05,851 talking about trust. The question after this is: Would you trust this, this Kyber 460 00:47:05,851 --> 00:47:10,820 algorithm to secure your communications now? 461 00:47:10,820 --> 00:47:17,220 Ruben: Should I answer or Krijn do you want to, you haven't said so much? 462 00:47:17,220 --> 00:47:21,360 Krijn: I would actually, yeah, I don't have. So if you're skeptical about it, you 463 00:47:21,360 --> 00:47:26,310 can also go to. I don't think we discussed it, but you can go to hybrid modes of the 464 00:47:26,310 --> 00:47:32,710 current classical, pre-qantum crypto and post-quantum, if you can suffer the 465 00:47:32,710 --> 00:47:37,580 drawbacks of that. But personally, yeah, I guess I would. Ruben, would you? 466 00:47:37,580 --> 00:47:45,060 Ruben: I would trust Kyber at this moment, but there's... If you don't trust it as 467 00:47:45,060 --> 00:47:51,050 Krijn said, you can go into hybrid mode, so the idea, for example, for TLS is to 468 00:47:51,050 --> 00:47:58,050 first do elliptic curve crypto and post- quantum crypto together, sort of in a way 469 00:47:58,050 --> 00:48:02,460 that the adversary, the attacker would have to break both in order to compromise 470 00:48:02,460 --> 00:48:09,220 the communication. So that way, you don't have to fully trust Kyber yet if you want 471 00:48:09,220 --> 00:48:15,260 to run the hybrid. But of course, the idea is to at some point get rid of this 472 00:48:15,260 --> 00:48:19,400 overhead and just run post-quantum crypto without elliptic curve crypto 473 00:48:19,400 --> 00:48:25,510 additionally. But yeah, I mean, I personally would use it right now. But 474 00:48:25,510 --> 00:48:32,940 what I also want to say is that in the beginning of every krypto system, RSA, 475 00:48:32,940 --> 00:48:37,400 elliptic curve doesn't matter. In the beginning, everybody is quite skeptical 476 00:48:37,400 --> 00:48:41,730 and nobody wants to use it yet. And that's fine. Like, that's how the community 477 00:48:41,730 --> 00:48:45,980 works. But over time, usually people gain trust. 478 00:48:45,980 --> 00:48:57,020 Herald: OK, thank you. Now we're getting into speculative territory, and one of the 479 00:48:57,020 --> 00:49:01,430 questions is whether you could have any guesses on which of the schemes is 480 00:49:01,430 --> 00:49:07,240 probably going to end up winning the NIST PQC competition, post-quantum crypto 481 00:49:07,240 --> 00:49:11,500 competition? Ruben: So NIST specifically says it's not 482 00:49:11,500 --> 00:49:23,560 a competition, very important. So Kyber is one of the winners coming out of it, but 483 00:49:23,560 --> 00:49:34,930 that's quite clear. And also you already see adoption in the real world. We brought 484 00:49:34,930 --> 00:49:42,290 two examples with Amazon and the BSI, for example, that wants to include it in 485 00:49:42,290 --> 00:49:49,920 Thunderbirds email encryption. So Kyber is going to be one of the winners. This is 486 00:49:49,920 --> 00:49:57,560 my... not only opinion, but yeah, that's quite clear. And otherwise, I think 487 00:49:57,560 --> 00:50:06,340 McEliece, which is a code based scheme that is quite large in all measures, let's 488 00:50:06,340 --> 00:50:11,640 say. But people seem to have more trust in it because it has been around longer. 489 00:50:11,640 --> 00:50:19,770 Yeah, so I'd say those for KEMs and everybody is quite unhappy with the 490 00:50:19,770 --> 00:50:27,490 signatures. So I don't think there will be signatures standardized like this year or 491 00:50:27,490 --> 00:50:32,910 beginning next year. But Krijn, I don't know, maybe you have a guess? 492 00:50:32,910 --> 00:50:38,530 Krijn: No, I'm not such a speculative person, but I think Ruben's answer is 493 00:50:38,530 --> 00:50:43,690 quite a good answer. Ruben: Now you really have to also 494 00:50:43,690 --> 00:50:49,170 speculate, I mean, come on, you can't just piggyback on my answer. 495 00:50:49,170 --> 00:50:52,760 Krijn: No I definitely can. It's interesting to note actually that for the 496 00:50:52,760 --> 00:51:01,960 signatures that there's less of a hurry, so to say. It's especially this key 497 00:51:01,960 --> 00:51:09,090 exchange that we wanted to make post- quantum as soon as possible, maybe, or at 498 00:51:09,090 --> 00:51:13,730 least one to standardize quickly and then integrate into whatever building. Well, 499 00:51:13,730 --> 00:51:19,830 for the signatures there a bit more time so there's also more time to come up with 500 00:51:19,830 --> 00:51:23,580 better solutions there or to analyze the current solutions a bit more. 501 00:51:23,580 --> 00:51:27,900 Ruben: Yeah, that's because I mean what we mentioned is the attacker model, big 502 00:51:27,900 --> 00:51:33,890 government agency, for example. And the key exchange you have to fix now because 503 00:51:33,890 --> 00:51:38,820 that could be later on broken and then the communication can be decrypted. But 504 00:51:38,820 --> 00:51:44,360 signatures like they have a small lifetime, for example, and also they are 505 00:51:44,360 --> 00:51:49,930 used for authentication. So you would need an active adversary. And that, yeah. You 506 00:51:49,930 --> 00:51:55,640 can't like record now and then do an active attack in 10 years, like, that 507 00:51:55,640 --> 00:51:58,990 doesn't work. So then we have some more time yeah. 508 00:51:58,990 --> 00:52:05,040 Herald: Well, that's not entirely true. There's a lot of states using, and I'm 509 00:52:05,040 --> 00:52:10,930 talking about signatures, not for the ephemeral use in online usage, but the 510 00:52:10,930 --> 00:52:16,030 more the use of signatures, for example, document signatures. And for those an 511 00:52:16,030 --> 00:52:18,180 attack would still be relevant for the future. 512 00:52:18,180 --> 00:52:23,590 Ruben: If they have, well, if they have a long runtime, usually signatures or keys 513 00:52:23,590 --> 00:52:28,790 at least, of signatures, they expire at some point. But yeah, of course, if you 514 00:52:28,790 --> 00:52:33,810 have, if you have signatures that do not have an expiration date or something, then 515 00:52:33,810 --> 00:52:37,920 they would be under threat as well. Herald: In a document signing, you will 516 00:52:37,920 --> 00:52:42,770 have signatures that have a very longer lifetime than you will have for your 517 00:52:42,770 --> 00:52:45,990 typical web transaction, for example. But I'm now full dropping out of role as 518 00:52:45,990 --> 00:52:49,120 herald who is a mere vessel of questions from the audience. 519 00:52:49,120 --> 00:52:50,590 Ruben: But of course, this is also interesting for us. 520 00:52:50,590 --> 00:52:57,420 Herald: And I guess with the last version, at least, I think this is the last 521 00:52:57,420 --> 00:53:01,020 question unless there is an additional one on IRC, so people have to be quick if they 522 00:53:01,020 --> 00:53:04,840 want to have additional questions. But the last questions are just very practical. 523 00:53:04,840 --> 00:53:11,020 And basically, do you have any ideas about pitfalls when implementing Kyber already? 524 00:53:11,020 --> 00:53:16,220 Do you have suggestions for making sure you implement it security? Or is it simply 525 00:53:16,220 --> 00:53:26,100 possible to implement it very naively? Ruben: So. This is always a big fight in 526 00:53:26,100 --> 00:53:31,010 the cryptography community, because they're the people that say, oh, there are 527 00:53:31,010 --> 00:53:36,380 a handful of chosen ones that are able to implement it securely. And you should 528 00:53:36,380 --> 00:53:41,770 never, ever, ever do it yourself. I'm on the opposite side of that, I think people 529 00:53:41,770 --> 00:53:47,590 should play around with implementation. Try it out. So, Kyber is among the schemes 530 00:53:47,590 --> 00:53:54,830 that it's definitely, let say easier to implement in a correct way. However, it 531 00:53:54,830 --> 00:54:03,650 depends where you want to use it because you also have to take side channels into 532 00:54:03,650 --> 00:54:08,440 consideration, especially if you work on embedded platforms, like power analysis 533 00:54:08,440 --> 00:54:13,930 and that kind of thing. So this is also still highly investigated. And then if you 534 00:54:13,930 --> 00:54:18,350 go for that kind of implementation, you should have a masked implementation. So 535 00:54:18,350 --> 00:54:25,210 this would be an own talk for itself. Like I don't want to like now give you two 536 00:54:25,210 --> 00:54:30,280 verbs what you should do and then say that it's secure. I mean, it's a bit more 537 00:54:30,280 --> 00:54:38,590 complicated than that. So I can't really say now do this do that. I can just say on 538 00:54:38,590 --> 00:54:45,170 the spectrum from easy to difficult, Kyber is more on the spectrum of easier to 539 00:54:45,170 --> 00:54:50,970 implement securely. But if you're interested in that, look up the 540 00:54:50,970 --> 00:54:55,650 implementations. There's a reference implementation. There's a PQClean and 541 00:54:55,650 --> 00:55:01,810 stuff. Look up the implementations online and look into that and the specification 542 00:55:01,810 --> 00:55:07,550 that is linked in the block post, that is linked on the slides. There are also some 543 00:55:07,550 --> 00:55:17,110 points that say what you maybe should, where you should be careful lets say. 544 00:55:17,110 --> 00:55:23,600 Herald: OK. And there was just an additional question as well, and that is 545 00:55:23,600 --> 00:55:28,900 what is the status of Kyber in OpenSSL and GnuTLS? 546 00:55:28,900 --> 00:55:42,400 Ruben: Okay, so we see adoption in crypto libraries, but OpenSSL. OK, I don't want 547 00:55:42,400 --> 00:55:53,610 to hate, but OpenSSL codebase is, how do I say that? Look, it's a bit complex and a 548 00:55:53,610 --> 00:56:04,140 bit difficult for outsiders to get what OpenSSL is doing in certain corners of 549 00:56:04,140 --> 00:56:11,770 their code base. But there's a project called OpenOQS, no liboqs that is a fork 550 00:56:11,770 --> 00:56:18,800 of OpenSSL, including post-quantum schemes, but not only Kyber, but various 551 00:56:18,800 --> 00:56:24,630 schemes. That's liboqs, its a OpenSSL fork. Now there are other libraries, for 552 00:56:24,630 --> 00:56:34,670 example, WolfSSL, which has a smaller code base and they already have in their actual 553 00:56:34,670 --> 00:56:40,530 release or in their main branch, let's say, in git, they already have NTLS post- 554 00:56:40,530 --> 00:56:46,420 quantum schemes, and Kyber is one of them. They have lattice based schemes,if I 555 00:56:46,420 --> 00:56:53,340 remember correctly: Kyber, Dilithium, and Falcon. So they already have it included. 556 00:56:53,340 --> 00:57:00,040 WolfSSL , OpenSSL as I said there is a fork that are like benchmarking and 557 00:57:00,040 --> 00:57:08,870 testing stuff in the hopes of later being able to return it to OpenSSL. But as I 558 00:57:08,870 --> 00:57:14,960 said OpenSSL is not exactly ideal for experimentation, becourse the code base is 559 00:57:14,960 --> 00:57:23,080 quite large and in some corners, quite complex to comprehend and so on. Other 560 00:57:23,080 --> 00:57:30,590 libraries are a little faster. I don't know of any efforts for GnuTLS to be 561 00:57:30,590 --> 00:57:35,280 honest, but I haven't looked into it yet. It's possible that somebody else did 562 00:57:35,280 --> 00:57:42,740 something there. I mean, I've I've worked with WolfSSL before and with OpenSSL. But 563 00:57:42,740 --> 00:57:53,650 GnuTLS I'm not sure. There are talks to include it in GnuPG which you can use for 564 00:57:53,650 --> 00:57:59,490 email encryption, and there are some there's some progress there. But yeah, 565 00:57:59,490 --> 00:58:07,960 GnuTLS I don't know. Herald: All right, OK. This brings us to 566 00:58:07,960 --> 00:58:15,920 our really final question, which is how close are the current cloud quantum 567 00:58:15,920 --> 00:58:24,270 offerings to be able to enable users to break current public key cryptography? 568 00:58:24,270 --> 00:58:31,050 Ruben: If I understand it correctly, Krijn you can also say something if you want, if 569 00:58:31,050 --> 00:58:37,430 I understand correctly, it's the question is general. If I can use cloud computing 570 00:58:37,430 --> 00:58:43,340 to break public key crypto? Herald: No, the question is more specific, 571 00:58:43,340 --> 00:58:48,000 there are quantum offerings by public cloud providers like Amazon right now, 572 00:58:48,000 --> 00:58:54,110 apparently. At least that's what I assume the person who asking the question is 573 00:58:54,110 --> 00:59:00,090 basing it on. And the question is, to what extent are those available options usable 574 00:59:00,090 --> 00:59:04,100 to break current public key cryptography schemes? 575 00:59:04,100 --> 00:59:08,680 Ruben: So if I understand the question correctly is like, already deployed 576 00:59:08,680 --> 00:59:14,840 quantum computers, are they a threat to pre-quantum schemes? OK, so far, they are 577 00:59:14,840 --> 00:59:23,050 not like there are quantum computers in use, but they don't have nearly enough 578 00:59:23,050 --> 00:59:32,930 qbits to break any real word schemes, so it's also more complicated than that 579 00:59:32,930 --> 00:59:37,150 because you don't only need qbits, you also need quantum registers that are large 580 00:59:37,150 --> 00:59:41,480 enough because you need to entangle all of the qbits. I mean, there we are going to 581 00:59:41,480 --> 00:59:46,110 quantum mechanics, but you need to entangle the bits and all that kind of 582 00:59:46,110 --> 00:59:52,000 quantum craziness. And then you also need error correction that's good enough. So 583 00:59:52,000 --> 01:00:00,020 there are still, there are still technical like engineering problems that you need to 584 01:00:00,020 --> 01:00:03,890 overcome, like in theory it's all fine and stuff, but there's some engineering 585 01:00:03,890 --> 01:00:08,290 efforts that you need to overcome, and the currently deployed quantum computers are 586 01:00:08,290 --> 01:00:16,430 not big enough to be a threat to quantum, to pre-quantum schemes unless you have 587 01:00:16,430 --> 01:00:23,920 some toy keysums. But for real deployments, it's not a threat yet, but it 588 01:00:23,920 --> 01:00:28,080 might be within the next couple of years. It's really difficult to foresee the 589 01:00:28,080 --> 01:00:35,000 development there and the largest quantum computers are actual quantum annealers 590 01:00:35,000 --> 01:00:39,210 that work differently, like quantum annealing is a different thing, a 591 01:00:39,210 --> 01:00:42,770 different kind of quantum computer that we're not too worried about right now. 592 01:00:42,770 --> 01:00:46,990 Like thats D-Wave for example. But yeah, so right now, they're not a threat, but 593 01:00:46,990 --> 01:00:53,400 they might be in the near future. Krijn: And especially so with regards to 594 01:00:53,400 --> 01:00:59,930 why you still switch to post-quantum crypto, is this idea that well, 595 01:00:59,930 --> 01:01:03,641 standardizing crypto and then integrating crypto and all of this takes years, as we 596 01:01:03,641 --> 01:01:08,290 know from that transition to elliptic curve crypto. So even if this quantum 597 01:01:08,290 --> 01:01:13,780 computer is 10 15 years away then still this whole transition thing will take so 598 01:01:13,780 --> 01:01:20,480 long that by the end of it, how long will your original data have been safe for? 599 01:01:20,480 --> 01:01:25,900 It's anybody's guess. Ruben: Yeah. I mean, you have to see 600 01:01:25,900 --> 01:01:30,420 asymmetric crypto is everywhere. Like, for example, also kind of example maybe in my 601 01:01:30,420 --> 01:01:34,730 passport, like my travel document. And there are documents, for example, out 602 01:01:34,730 --> 01:01:40,560 there that are valid for 10 years like, I think, a proper passport and all that kind 603 01:01:40,560 --> 01:01:44,610 of stuff. And of course, it really takes long also with these kinds of things, like 604 01:01:44,610 --> 01:01:50,670 documents like that are issued by governments. It just takes time, it takes 605 01:01:50,670 --> 01:01:57,460 a lot of time. Herald: OK, thank you very much. I should 606 01:01:57,460 --> 01:02:01,700 also note that from the signal angel, there have been several very enthusiastic 607 01:02:01,700 --> 01:02:06,200 responses from the audience and not so much questions about your talk, that's 608 01:02:06,200 --> 01:02:09,720 also very interesting. So thank you so much for doing this, and maybe see you 609 01:02:09,720 --> 01:02:11,720 around. Krijn: Thank you. 610 01:02:11,720 --> 01:02:16,530 Ruben: Bye bye! 611 01:02:16,530 --> 01:02:37,320 rc3 postroll music 612 01:02:37,320 --> 01:02:41,000 Subtitles created by c3subtitles.de in the year 2021. Join, and help us!