rc3 preroll music Herald: Good afternoon everyone watching, the upcoming talk is by Ruben Gonzalez and Krijn Reijnders, they're both Ph.D. students at Radboud University, and Ruben is also a capture-the-flag player, under the name "Red Rocket", or affiliated with "Red Rocket". Their talk will me about post-quantum cryptography. And we'll take a kind of introductory dive into Kyber. This talk will also be live-translated into German, so if you don't speak German, don't despair. Dieser Vortrag wird also übersetzt simultan in Deutsch, and that's also the extent of my German. Also, this talk is prerecorded will last a bit over 30 minutes, but the Q&A will be live afterwards. So enjoy. Ruben Gonzalez: Hello, and welcome to our presentation on Kyber and post-quantum cryptography. How does it work? First, my name is Ruben Gonzalez, I'm a Ph.D. student in the Netherlands. I'm doing this presentation together with my colleague Krijn Reijnders, and we'll be teaching you all about Kyber today. So, first things first, a small disclaimer, because I don't want to disappoint any people: We're doing boomer crypto here, so we won't be talking about blockchain, NFTs, shitcoins,... at all. Instead, we're going to bore you with mathematics, weird kinds of key pairs, and U.S. government agencies. So, our talk is divided into four segments. First, I'm going to teach you a little bit about what post-quantum cryptography actually is and why you should care about it. Then we're going to talk about Kyber, which is the scheme we're going to go into detail about, because it's just about to take over the world. And then Kreijn will talk to you a little bit more about the security guarantees about how the system actually works mathematically. And then we're going to give you a brief outlook on the future of crypto and where we're headed in the field. So, post-quantum crypto. A little bit of basics here: Today, cryptography, on a high level, is divided into two parts; a boring part and an exciting part. So the boring part is called symmetric crypto and symmetric crypto does what you usually expect from cryptography. So you can encrypt stuff with it and sometimes you do authentication with it. But the biggest part is the encryption stuff. So you have a secret team that nobody is allowed to have, and if you have this secret key you can encrypt things, and another person that has the same secret you can decrypt with it. So that's why it's symmetric - you have one key for encryption and decryption. And what you actually use implementation wise, is almost exclusively AES encryption encryption or hash functions that are from the SHA family and it's a symmetric world. That's a symmetric side of things. Now you also have asymmetric crypto because if you look at symmetric crypto, you have this secret key, but you don't actually have a way of getting two parties having the same secret key. And it's where asymmetric crypto comes into play. So, you can use asymmetric crypto, among other things, to exchange this secret key. So asymmetric crypto uses a key pair: a public key that everybody can have and a secret key that only the recipient can have. So. Yeah, essentially with the public key you encrypt, for example, the symmetric key, and with the private key you decrypt, and here it feels a bit more difficult. There's not only two algorithms that are being used, but there's an entire zoo of algorithms used. So, let's look at the zoo real quick. Probably some of these terms you've already heard: Curve25519 is pretty big; maybe you've used RSA before, Diffie- Hellman, that sort of thing. So there's this big zoo of different kinds of schemes in asymmetric crypto that it can use for different things. Sometimes there are different schemes that you can use for the same thing, or you can use one scheme for different things. So it's a bit more complicated to make an overview of the algorithms. But, if you look at the zoo, people seem to be happy, right? Oh, they look around, they have a look, things seem to work, it's a happy world. So why would you want to change that? And in post- quantum crypto, we actually want to change the asymmetric crypto fundamentally. Well, there's one big problem with this zoo, and it's not in the zoo, but it's coming for the zoo. So there's this guy, Peter Shore, and he's threatening the zoo. He's about to destroy it and everything in it. And why is that? Well, we have this big zoo of asymmetric crypto, right? But if you look at the different schemes in detail, you actually see that they are only based on two mathematical problems. And that is integer factorization and the discrete logarithm. We don't have to we don't have the time to go into much detail on those, but you have to know that the entire asymmetric crypto zoo is based on two problems. And, coincidentally, Peter Shore, defined an algorithm, a quantum algorithm, that breaks those two problems and all cryptography that's based on them. So all of today's crypto is actually broken if we can use Shore's algorithm. Now Shore's algorithm is a quantum algorithm. That means we need a large enough quantum computer for it to work, but once we have that, all asymmatric crypto is destroyed. And why should you care about that? Well, maybe you use one of those things here. Well, actually you do, whether you like it or not. You're watching this stream right now via TLS. Maybe you also use things like SSH or email encryption or VPNs with IPsec or WireGuard. Well, Shore's algorithm would break all of those protocols. Everything. And you should care because in the modern information age, essentially everything is digital communication. All security is virtually based on cryptography, so, if Shorezilla and breaks everything, we do have a huge problem. So the natural question that arises is: "when will we have large quantum computers?" And the answer is: "we don't know." Different experts say different things. The opinions vary from within five years to never. But the truth is, nobody knows. We can't see in the future. We don't have a magic eight ball there. But we should definitely be prepared for the large quantum computer because we don't want all of our information security to be broken when, let's say, a large U.S. government agency all of a sudden manages to build a quantum computer. So post-quantum crypto is all about designing asymmetric cryptography that is unaffected by quantum computers. Or let's say we hope they are. But we're pretty certain they should be unaffected. They're certainly unaffected by Shore's algorithm. So now that you know a little bit about what post-quantum cryptography is about and why we need it, I want to talk about Kyber. Kyber is the post- quantum scheme that is most likely to be adopted in the near future. So the asymmetric crypto zoo is threatened - Let's make a new new zoo, where people can and people can be happy and live their fulfilled lives. The standardization organization NIST launched a call a couple of years back for new cryptographic schemes that are resilient against quantum computers. And first schemes are actually about to be standardized very soon in early 2022. So, we want to look at one scheme that is about to be standardized, and it's called Kyber. Now why are looking at exactly that scheme? Well, it's very fast, and the public and private key sizes are not too big, meaning you can actually use it in real world projects, which is not always the case for all post-quantum schemes. So it is already, even though it's not, it's standardized, it has already seen some adoption in industry. And it's a lattice-based scheme. And right now it looks a little bit like lattice is going to be the future. If you don't know what a lot of space scheme is, that's really fine; Krijn is going to tell you in the end. So, that was the fun part of our presentation, the easygoing part. Now we need to roll up our sleeves, we need to get our hands dirty and we need some mathematics. And for that, I'm going to give the mic - turn over to Krijn. (How do you say that? Give it to Krijn? I don't know.) Bye. Krijn Reijnders: So, now we need maths. So let's start. What we need in Kyber are polynomials, and we need to work with polynomials. But actually, you can think of polynomials just like you do of as numbers. What do I mean with that? I mean that you can just multiply them and you can also just add them together like you do with numbers. And just as we do with numbers in pre- quantum cryptography, when they get too big, we reduced them. We do this modulo operation. We'll do the same for the coefficients in the polynomials, but also, when the degree of a polynomial gets too big, we will reduce them by another polynomial. So we have a modulo operation with polynomials, and in this way you can do all kinds of things with polynomials. And that's actually all of the mathematics that we all need fundamentally to work with Kyber. What do I mean by that? Well, if you can do multiplication and addition, then you can also do these things like we do for numbers with matrices and vectors, so we can multiply a matrix with a vector and add another vector. And this works the same for these polynomials, so you can have a matrix full of polynomials and a vector full of polynomials, and you can just multiply them together, add another vector. It's just this basic operation of multiplication and addition of polynomials. It looks a bit more complicated, but that's it. And then, let's say we do this, we have a matrix and we multiplied by a vector and we add another small vector. Now if I give you the end result of this computation, and I give you this matrix that we started with, it's actually very hard to recover the vector that we've multiplied the matrix with. And this is the fundamental problem that we need in Kyber. And it's called module-learning-with-errors. I know this name does not make a lot of sense, but apparently mathematicians thinks it does aptly describe the problem. So this matrix, we call it 'A', this secret vector of ours, we call it 's', then we need to add a small error term so that it's not too easy to solve this problem, and then we get a public value again, which we call 't'. This gets you the equation A times s plus e equals t. And then the public key pair is this matrix 'A' and this end result 't', and the private key is our secret vector, 's'. That's all that we need to generate a key pair in Kyber. We need to ensure actually that the private key pair has small coefficient, and that also makes it very compact to transmit. And also, this error has small coefficients. For the rest of the presentation: These error terms, they are necessary, but they complicate the equations are a bit too, so we'll just write them in emojis so that you know what the errors are and what are the important values, and now Ruben will explain again: How can we encrypt and decrypt messages using such a public and private key pair? R.G.: OK, our Boomer is back, and he wants to encrypt something. So, as an example, he wants to encrypt the letter C. So C is not a variable, it's literally the letter "C" that he wants to encrypt. And as we learned earlier, to encrypt something, we need the public key. So we have this public key, which is the matrix A and the vector t. So first, we need to transform the letter "C" into some form that Kyber can work with because we want to encrypt it with Kyber. So let's first break it down into binary, right, in a computer, everything is binary anyways, so let's say we used to ASCII encoding. So we turn the letter "C" into a series of ones and zeros. In this case, it's one zero zero zero zero one one. Now we have binary representation, but Kyber uses those polynomials, right? So we have to somehow turn this into a polynomial, which turns out to be quite simple. So we just do a binary polynomial, so we take the ones and zeros and use them as coefficients for a polynomial. In this case, you can see the polynomial on the slides, quite simple. So one bit is one polynomial coefficient. Since zero times something is just zero, which is just leave out the zero terms and shrink our polynomial a bit. So we now have a plain text and we can use within Kyber, right? The plaintext is a polynomial "x to the power of six plus x plus one". That's our plain text. We haven't encrypted anything yet, but we have a plain text. So now let's us Kyber to encrypt the plain text polynomial. First, we have to scale it. We have to make our polynomial big. And we do that simply by multiplying the polynomial with a large factor. So here I chose 1337, it's arbitrary, depends on the Kyber instance, but we just multiply every polynomial coefficient with the large number 1337. So we have the same polynomial, but with larger coefficients. So our scale plaintext is 1337 x to the power of, and so on and so on. So now we do the actual encryption, which in Kyber, it's actually quite simple. We just sprinkle in some error terms. As Krijn mentioned earlier, in our presentation, small error terms are represented as emojis. Because they're not that important, but you should still know they're there. So our ciphertext is actually just two values, v, which is a polynomial and u, which is a vector of polynomials. So, v is the key value from the public key, multiplied and added with error terms, and then the actual scale plaintext message is added as well. u is a matrix from the public key, multiplied with an error term and an added error term. You can see the carrot error term appears in both equations. And that's it. That's our encryption. (v,u) is the encryption of our plaintext. So doing only encryption would be kind of boring. We probably also want to decrypt stuff. So, how do we do that in Kyber? Well, we need the private key, right? Public key encrypts, private key decrypts. So we have our ciphertext, those two values v and u. And in order to decrypt, we first remove the public key from it. And we do that just by taking v minus the private key, multiplied by u. And if I spell out the equations, they become quite long. But as you can see, if you think about the emojis as error terms is that most of the public key, or actually the entire public key, kind of cancels out. So, and d, here on the slide, is the end result of the calculations of v minus private key times u. And so we have our message in d, which is the plain text, but we also have these error terms laying around and the private key. Now one core observation is important. I mentioned earlier that error terms are all small, meaning they're polynomials with small coefficients. And the private key also has polynomials with small coefficients. So here on the slide, everything on the right side is actually small, but our plain text is large because we scaled it earlier. We multiplied it with a large number 1337. So simply by kind of rounding everything, we get our scaled plaintext back, because these terms are small. So just by rounding, we get our scaled plaintext back. And then we have essentially decrypted. What we now have to do is just turn it back into the original text, so we scale down, divide every coefficient by 1337. We bring back to zero terms, so every coefficient that is not in the polynomial has a zero. Yeah, every term that is not in the polynomial has a zero coefficient. So we bring back the zeros and then from the binary polynomial, we can just read out the ones and zeros from the coefficients. We have back binary code and this binary now we can decode again using the ASCII, for example, and we have our plaintext back. And that's how Kyber decrypts. And then we can decode the Kyber plaintext into your original message, which was a "C". So how does Kyber looks like for the home consumer? Well, Kyber comes in three flavors, three different security levels. There's Kyber512 until Kyber1024. So, in cryptography usually security is measured in bits. Sometimes it's related to how strong AES is. So the lowest acceptable acceptable security level for us is 128 bit and the strongest security level we use in practice is 256 bit. So Kyber512 has around 128 bit security and Kyber1024 as around 256 bit of security. Now that's what the end user needs to know. But I also want to show you what these securities actually mean in terms of Kyber, because Kyber instances are mainly defined by three variables: n, k, and q. And what do those mean? Well, n just means the degree of the polynomials used within Kyber. So 256 means we have exponents x to the power of maximum 256. So polynomials are quite large. 256 coefficients we can store. k means the size of the vector. So as you've seen, Kyber uses not only polynomials, but also vectors of polynomials. So essentially lists of multiple polynomials. And in Kyber, the k variable says how many polynomials are in such a vector. q is the modulus for the numbers. I mean, we have coefficients, right? And how big can this coefficients get? So the largest coefficient that is used within Kyber would be 3328 because we take it modulo 3329. So as you can see, in Kyber, we don't have to deal with big numbers, actually. We have to do with a pre-quantum cryptography, we have to deal a lot with huge numbers. Here, the numbers are not that big. Also important is size to speed tradeoffs. Now here you can see a bar chart of public key, private key and ciphertext sizes of an elliptic curve scheme, Curve25519, RSA, and kyber in smallest security level. So those three security schemes are the same security level, but as you can see, elliptic curve crypto is really tiny, RSA is somewhat bigger, an Kyber is even bigger. But if we go to the highest security level, you see that Kyber is actually very comparable to RSA. However, ecc is still a lot smaller. But you don't only care about sizes, you also care about speed, you care about speed even more. And if we compare the same security level in Kyber, in elliptic curve crypto and in RSA, we can see that Kyber is on fire. Kyber is really, really fast. So we can throw out RSA and just compare elliptic curve crypto to Kyber, and we can see Kyber is even faster than elliptic crypto, which is quite impressive because ellipctic crypto is already quite fast. And, even more, we can see that the highest security level of Kyber is faster than the lowest security level of elliptic curve crypto. So Kyber - fast as hell. I know benchmarks are difficult. We have different kinds of platforms, but as an intuition: Kyber is really fast. So the thing I want to mention is that Kyber source code is available online. You can download it from GitHub, for example, from the PQClean Project, which has AVX optimized implementations for desktop CPUs, from the pqm4 project, which is the optimized implementation for ARM-based embedded processors, or there's also a reference C implementation in the pq- crystals project. And, last but not least, the specification, the documentation, the code, everything is licensed under Creative Commons zero, meaning that it's public domain. So there is zero license or patenting issues with Kyber, it's just public domain. You can clone and do whatever you want with it. It's quite nice. So that was it about Kyber, now Krijn is going to tell you more about what actually lattices are and why Kyber is actually secure the way it is. Krijn: OK, so that was Kyber. And we've been talking a lot about polynomials, but we haven't talked so much yet about lattices. But we did say that Kyber was a lattice based scheme. So what do lattices have to do with all of this polynomial stuff? And why do we think it's secure because of this being lattice based? Well, let's go back to these numbers that we used for a second, just because they make these things more understandable and intuitive. We had this matrix multiplication. We multiplied the matrix with a vector. Now let's say we do this for numbers, right? We have this matrix 13, 4, 2, 9 and we multiplied by a, b. Well, actually, what you could also see here is that you multiply the vector 13 over 2 a times and then add the vector 4 over 9 b times. And as you see in the image, like, you can make different combinations of that. So if you take a = 1 and b = 1, you get the point on the top right corner and then you can do this for a = 2 and b = 1, then 3 and 4 infinitely. And then you would get all of these dots spread out over the cartesian plane, and it would go on infinitely in these dimensions. So you would get infinite number of points just by giving these two original vectors 13, 2 and 4, 9. Now, our secret key s was just actually then a way to pick one of these points, because we said, well, the Matrix a that we had in the public key, it describes some sort of lattice. And then the secret key s described actually a specific point: a number of times the first vector, plus a number of times the second vector. Then what does this error term do? Well, you know, it shifts just a bit from this lattice point that we were at and then we get the end result t over there. And now it's very difficult actually to get back from t to this vector s. We know that it's the closest vector to this given point t in this lattice described by a. But this problem of finding the closest vector in the lattice and in a random letters is actually very hard. And this is what we call the closest vector problem, which is a very good name because we're looking for the closest vector. So for this two dimensional example, we had the matrix e and the vector t in the public key, and we had the vector s in the private key and that was hidden by this small error term. So to recap: a gives you these initial vectors, which you can use to describe the lattice, s gives you a secret point in that lattice. The error makes sure that you're close to a lattice point, but not too far away. And then we get the end result t, which is this public point and then getting back from this information of this lattice and t to s is the closest vector problem, in a nutshell. You may be thinking now, OK, this is for numbers I can see this right. It's just these dots in this plane. For dimension two OK, I get it. For Dimension three you can think of a third dimension. Though we were talking about dimension n way larger than 3 and polynomials instead of numbers. And how do we visualize this? And the truth is we don't actually, but we do know how to compute it, which was just this multiplication and addition of polynomials. So we just compute it and we kind of think of it as a lattice abstractly, but not visually. Now let's finish with a short look at the future of asymmetric crypto, and let's go back to the post-quantum crypto zoo that we had. We already took a look at Kyber, but there was also other cryptographic primitives such as Rainbow, Falcon, and SABER and Dilithium, NTRU, McEliece. Among them, there are signature schemes, but also these key exchange mechanisms. Actually, this zoo is quite different from the one that we had pre-quantum, the one that we had pre-quantum as we explained was based on mostly integer factorization and a discrete logarithm problem. But in the post-quantum setting, we have a variety of problems. We have hash based cryptography, lattice based cryptography, code based cryptography, multivariate based cryptography, and isogeny based cryptography. And these are five quite different flavors of cryptography, with also different underlying mathematical problems. But post-quantum crypto is coming. For example, Amazon has already implemented some of the round two candidates, such as Kyber in post-quantum TLS. And also the BSI, which is the German Ministry for Information Security, has put out a proposal to integrate post-quantum cryptography into Thunderbird as their mail client. And even NIST has the following quote that if you haven't migrated to elliptic curve cryptography yet, don't bother, just directly migrate to post-quantum crypto. And that wraps up our presentation on post-quantum crypto and Kyber. If you want to do some further reading, there is a link here to a blog that goes a bit more in-depth in how Kyber works and has a very small example. Just as we've shown you in this video. Thank you for your attention and we'll take some questions now. Question: So why should I care about this now? Ruben: Well, that's an excellent question. Well, as we know from the Snowden leaks, the NSA is currently recording a lot of internet traffic that is encrypted, and they're recording this encrypted traffic in the hopes of being able to decrypt it later. For example, using a large quantum computer. So first, we have to care about this now because our internet traffic is already recorded and could be broken later. And second, we have to care about this now because transition, especially when it comes to cryptography, is really slow because standardization takes a lot of time. Implementation takes a lot of time, and adoption takes a lot of time. So that's why we have to care now. Question: But are there any downsides? Krijn: Another very good question. Actually, yeah, there are some downsides, but they're not too big. Usually, the keys are a bit larger than we are used to. In some cases even much larger than we are used to. And the speed is a bit worse than we are used to. In some schemes, even much slower than we are used to. But while this is already being adopted, it is also still a very active area of research and we are continuously trying to make the keys smaller and the schemes more efficient. In the hopes that we in the end, get very efficient schemes that will solve all of our post-quantum problems. Why didn't you let me eat the lettuce? Ruben: It's my lettuce! Okay, now eat it for the camera, you can eat one. But it's not washed. Herald: Okay, thank you. The first question we got from the internet is: Why are you using seven bit ASCII instead of Unicode? Ruben: So in that case of the letter c that wouldn't make a difference anyways. We just prefer to use ASCII because we really, really want to piss off the European people because all of these umlauts and that kind of stuff. Of course, they're unnecessary. So ASCII forever. Herald: I'm surprised that both of us Europeans as well, but let's not get to the nationalism bit and carry on with the next question, which is, by the way, how can you compare the security levels according to varying n and varying q, respectively? Ruben: Sorry, the connection was a bit lost there. Could you repeat the question? Herald: Of course, can you compare the security levels according to varying n and varying q, respectively? Ruben: Yes, of course you can. I'm not sure if I get the question. Of course, that's how you do it, that's how you compare and you can do that. I'm not sure if the question asked me to do that right now on the spot because that I couldn't do, but I mean, it was on the slides, like the security levels that are about to be standardized, at least. But the one good thing about Kyber, a very good thing that I want to mention is that, so the polynomials, the size stays the same, the modulus q stays the same. Only the size of the vectors change. So how many polynomials you have in a vector. And that makes it quite nice to write optimized code because most parts of the code are literally the same. If you look at the implementation, the reference implementation, you can see that it's actually the same code for all the security levels, just one header changes that specifies how big the vectors are. So that's quite nice. But you can yeah, you have for RSA, you have different key sizes. So yeah, it's more difficult to optimize, but here you can just have the same size as just the vector size changes, which is nice Herald: What about the potential for hardware acceleration for Kyber? Could that be possible, feasible? Ruben: So I am not sure if I just answer that or Krijn also wants to say something, but hardware acceleration for post-quantum schemes in general is, as we say, a very active area of research. So these things are very new. There were some people that tried to use, there's a paper about it, actually - you can look it up on the internet - to use RSA bignum hardware acceleration for Kyber, which is a quite interesting idea because you work in completely different things there. But it's an open question and it's a very active area of research. So if any of the viewers are interested in that sort of thing, to, I don't know, try out Kyber or FPGAs or something. Yeah, try it out! So there's a lot of potential there, but it's also, as I said, very actively researched because it's relatively new and it just now finds adaptation in industry. Herald: And there's a follow up question that sort of mirrors it in a way because that question is: T o what extent is this feasible on embedded architectures with very limited hardware to use Kyber there? Ruben: So I've been using it on a Cortex M3, which is ARM-based. So usually the reference platform, we use the Cortex M4 because we want to. Like two experiments that are reproducible, and you can buy Cortex M4 boards quite cheaply from various vendors. So it's definitely possible to run Kyber on a Cortex M3. I mean, there's also a project on GitHub. It's called pqm3, that has Kyber benchmark for various, yeah M3 boards, but that's definitely possible. What I'm working on right now is testing it on a Cortex M3 and M4 for also application level, so included it in TLS or KEMTLS. Or there's a paper about WireGuard using Kyber and Dilithium for example. That's definitely possible. The question, also active area of research is, how low can you get? Like, how much can you optimize? Because there are various tradeoffs, like do we want more space for code but use less RAM and you also always have these kinds of tradeoffs in the embedded world. And that's something I'm a little actively looking into right now, actually. But it's certainly possible to run it on embedded systems. We could also go for a Cortex M0, which is, like really, really low level, but the cortex M3 is already running on smartcards. So that's what I'm currently looking at and there it's definitely possible. But as I said, you have to look into tradeoffs, see how much you want to waste on ROM, how much you want to waste on RAM and how much time do you have for the runtime? But the benchmarks we are having there, as I said. Go to Github, pqm3, already quite good, so it's definitely usable depending on your use case. I hope that answers the question. Herald: So do I. There's another question by someone who actually has implemented it. So I just briefly read the questions: I implemented a raw learning error scheme in an insecure "Hold my beer"-style. It seems to work, but I see about 1% bit errors in the decrypted text, how do real implementation handle the expected bit errors in the decryption? Ruben: So the easy answer is rounding. So you just throw away some of the lowest bits, but that really depends on the scheme. So if he has done some learning with errors. So there are different flavors of learning with errors. There's like ring learning with errors, modulo learning with errors, learning with errors, and it depends on what he has implemented. But in the end the thing that seems to work is just throw off the least significant bits, for example, depending on how many errors you expect. I don't know, Krijn do you want to add something? Krijn: No, I think you're doing fine with the question. Ruben: If there's no question I'm going to ask your questions afterwards. Very personal ones for history. You know? Herald: I shall move on to the next question, but I think from a layman's perspective, this may also relate to the last question. The question is: Those sequencing terms are set to be small relative to the mesh's coefficients. How do you make sure that those do not compromise encryption and are chosen arbitrarily? Ruben: So again, I'm really sorry. I had a couple of hiccoughs, so I didn't get the question could you repeat it? Herald: Sure. The question was: The Secret key and error terms are set to be small relative to the message coefficients. How do you make sure that those do not compromise the encryption chosen arbitrarily? Ruben: OK. I had a hiccough again, Krijn, did you get the question? Otherwise, I'll answer what I heard. I think what I think I heard. Krijn: So why are... why don't the small... the fact that the error and the private key are small, why doesn't this compromise security? And in fact, well you need the error to be quite small in order to be able to solve this, this closest vector problem that we've sketched. If the error is too big then a different vector could be the closest vector than the one that you want. Now why the private key has to be small. There are some results that we know that this does not mean... that it doesn't break the security basically of the scheme. I don't know if , Ruben, you can do a two liner on why that is. Ruben: So I answer the question always like: we bring in all those error terms. How do we make sure that the decryption isn't faulty, right? And actually, it's a very good question, because there's a provable, probably negligible probability that there will be decryption errors. However, Kyber is fast enough. We handle them in the KEM Version of Kyber. So what we have introduced here is the public key encryption version. Standardized as the KEM, which uses internally the public key encryption version and in the KEM version, you can be sure that this doesn't happen because, yeah. To answer the question, there's a tiny, tiny but negligible probability that you have a decryption error, so in that case a very good question. But if you're really interested, the blog post, I mean, you can download the slides and there's a blog post. For the talk, let's say, so you can go to the blog post and there's the Kyber specification reference. They can just click on the specification and there you can see that it's a fine tuning of parameters to make sure that the sprinkled in error terms do not invalidate the decryption to a certain, within a certain probability. And we make that probability in Kyber so low that in reality it will never happen. Like, 2 to the power of... lets say magnitude-wise something like atoms on Earth or like to give you an idea of how big the numbers are there. So it's a very, very low probability that that will happen. But a very good question. At least thats how I interpreted the 50% of the question that I heard. Herald: I am sorry that we seem to have a technical problem. Ruben: I think it's just the shitty internet at my my parents place. Herald: That could also be the case also on my end there are troubles as well. The question after that and maybe Krijn can just start answering it. Would Kyber be broken if someone found a simple solution to the closest vector problem? Krijn: Yeah, but we that's the case, that's always the case for encryption. If you managed to solve the fundamental problem, then the encryption scheme is broken. Luckily for the closest vector problem, we have a very good, we have quite some trust in this problem, so some other of these post-quantum schemes are based or more recent problems, so the closest vector problem is a much older one. So we do trust it, well I have quite a bit of trust that it won't be easily broken in the coming years. Ruben: So the answer is it's a bit tricky there, because the close vector problem is NP hard. So we think this is like a very good problem to start from. But the question is also like how are these lattices related to certain instanciations of the closest vector problem? And are these specific closest vector problems maybe a bit simpler or something? But as Krijn said we're in the closest vector problem we trust like this is one of the problems in post-quantum crypto that we're pretty certain about. But yeah, if you would solve it or if you have already solved it, Kyber would be broken. Herald: That sounds like a potential inscription on the side of a coin. In the closest vector problem we trust. And talking about trust. The question after this is: Would you trust this, this Kyber algorithm to secure your communications now? Ruben: Should I answer or Krijn do you want to, you haven't said so much? Krijn: I would actually, yeah, I don't have. So if you're skeptical about it, you can also go to. I don't think we discussed it, but you can go to hybrid modes of the current classical, pre-qantum crypto and post-quantum, if you can suffer the drawbacks of that. But personally, yeah, I guess I would. Ruben, would you? Ruben: I would trust Kyber at this moment, but there's... If you don't trust it as Krijn said, you can go into hybrid mode, so the idea, for example, for TLS is to first do elliptic curve crypto and post- quantum crypto together, sort of in a way that the adversary, the attacker would have to break both in order to compromise the communication. So that way, you don't have to fully trust Kyber yet if you want to run the hybrid. But of course, the idea is to at some point get rid of this overhead and just run post-quantum crypto without elliptic curve crypto additionally. But yeah, I mean, I personally would use it right now. But what I also want to say is that in the beginning of every krypto system, RSA, elliptic curve doesn't matter. In the beginning, everybody is quite skeptical and nobody wants to use it yet. And that's fine. Like, that's how the community works. But over time, usually people gain trust. Herald: OK, thank you. Now we're getting into speculative territory, and one of the questions is whether you could have any guesses on which of the schemes is probably going to end up winning the NIST PQC competition, post-quantum crypto competition? Ruben: So NIST specifically says it's not a competition, very important. So Kyber is one of the winners coming out of it, but that's quite clear. And also you already see adoption in the real world. We brought two examples with Amazon and the BSI, for example, that wants to include it in Thunderbirds email encryption. So Kyber is going to be one of the winners. This is my... not only opinion, but yeah, that's quite clear. And otherwise, I think McEliece, which is a code based scheme that is quite large in all measures, let's say. But people seem to have more trust in it because it has been around longer. Yeah, so I'd say those for KEMs and everybody is quite unhappy with the signatures. So I don't think there will be signatures standardized like this year or beginning next year. But Krijn, I don't know, maybe you have a guess? Krijn: No, I'm not such a speculative person, but I think Ruben's answer is quite a good answer. Ruben: Now you really have to also speculate, I mean, come on, you can't just piggyback on my answer. Krijn: No I definitely can. It's interesting to note actually that for the signatures that there's less of a hurry, so to say. It's especially this key exchange that we wanted to make post- quantum as soon as possible, maybe, or at least one to standardize quickly and then integrate into whatever building. Well, for the signatures there a bit more time so there's also more time to come up with better solutions there or to analyze the current solutions a bit more. Ruben: Yeah, that's because I mean what we mentioned is the attacker model, big government agency, for example. And the key exchange you have to fix now because that could be later on broken and then the communication can be decrypted. But signatures like they have a small lifetime, for example, and also they are used for authentication. So you would need an active adversary. And that, yeah. You can't like record now and then do an active attack in 10 years, like, that doesn't work. So then we have some more time yeah. Herald: Well, that's not entirely true. There's a lot of states using, and I'm talking about signatures, not for the ephemeral use in online usage, but the more the use of signatures, for example, document signatures. And for those an attack would still be relevant for the future. Ruben: If they have, well, if they have a long runtime, usually signatures or keys at least, of signatures, they expire at some point. But yeah, of course, if you have, if you have signatures that do not have an expiration date or something, then they would be under threat as well. Herald: In a document signing, you will have signatures that have a very longer lifetime than you will have for your typical web transaction, for example. But I'm now full dropping out of role as herald who is a mere vessel of questions from the audience. Ruben: But of course, this is also interesting for us. Herald: And I guess with the last version, at least, I think this is the last question unless there is an additional one on IRC, so people have to be quick if they want to have additional questions. But the last questions are just very practical. And basically, do you have any ideas about pitfalls when implementing Kyber already? Do you have suggestions for making sure you implement it security? Or is it simply possible to implement it very naively? Ruben: So. This is always a big fight in the cryptography community, because they're the people that say, oh, there are a handful of chosen ones that are able to implement it securely. And you should never, ever, ever do it yourself. I'm on the opposite side of that, I think people should play around with implementation. Try it out. So, Kyber is among the schemes that it's definitely, let say easier to implement in a correct way. However, it depends where you want to use it because you also have to take side channels into consideration, especially if you work on embedded platforms, like power analysis and that kind of thing. So this is also still highly investigated. And then if you go for that kind of implementation, you should have a masked implementation. So this would be an own talk for itself. Like I don't want to like now give you two verbs what you should do and then say that it's secure. I mean, it's a bit more complicated than that. So I can't really say now do this do that. I can just say on the spectrum from easy to difficult, Kyber is more on the spectrum of easier to implement securely. But if you're interested in that, look up the implementations. There's a reference implementation. There's a PQClean and stuff. Look up the implementations online and look into that and the specification that is linked in the block post, that is linked on the slides. There are also some points that say what you maybe should, where you should be careful lets say. Herald: OK. And there was just an additional question as well, and that is what is the status of Kyber in OpenSSL and GnuTLS? Ruben: Okay, so we see adoption in crypto libraries, but OpenSSL. OK, I don't want to hate, but OpenSSL codebase is, how do I say that? Look, it's a bit complex and a bit difficult for outsiders to get what OpenSSL is doing in certain corners of their code base. But there's a project called OpenOQS, no liboqs that is a fork of OpenSSL, including post-quantum schemes, but not only Kyber, but various schemes. That's liboqs, its a OpenSSL fork. Now there are other libraries, for example, WolfSSL, which has a smaller code base and they already have in their actual release or in their main branch, let's say, in git, they already have NTLS post- quantum schemes, and Kyber is one of them. They have lattice based schemes,if I remember correctly: Kyber, Dilithium, and Falcon. So they already have it included. WolfSSL , OpenSSL as I said there is a fork that are like benchmarking and testing stuff in the hopes of later being able to return it to OpenSSL. But as I said OpenSSL is not exactly ideal for experimentation, becourse the code base is quite large and in some corners, quite complex to comprehend and so on. Other libraries are a little faster. I don't know of any efforts for GnuTLS to be honest, but I haven't looked into it yet. It's possible that somebody else did something there. I mean, I've I've worked with WolfSSL before and with OpenSSL. But GnuTLS I'm not sure. There are talks to include it in GnuPG which you can use for email encryption, and there are some there's some progress there. But yeah, GnuTLS I don't know. Herald: All right, OK. This brings us to our really final question, which is how close are the current cloud quantum offerings to be able to enable users to break current public key cryptography? Ruben: If I understand it correctly, Krijn you can also say something if you want, if I understand correctly, it's the question is general. If I can use cloud computing to break public key crypto? Herald: No, the question is more specific, there are quantum offerings by public cloud providers like Amazon right now, apparently. At least that's what I assume the person who asking the question is basing it on. And the question is, to what extent are those available options usable to break current public key cryptography schemes? Ruben: So if I understand the question correctly is like, already deployed quantum computers, are they a threat to pre-quantum schemes? OK, so far, they are not like there are quantum computers in use, but they don't have nearly enough qbits to break any real word schemes, so it's also more complicated than that because you don't only need qbits, you also need quantum registers that are large enough because you need to entangle all of the qbits. I mean, there we are going to quantum mechanics, but you need to entangle the bits and all that kind of quantum craziness. And then you also need error correction that's good enough. So there are still, there are still technical like engineering problems that you need to overcome, like in theory it's all fine and stuff, but there's some engineering efforts that you need to overcome, and the currently deployed quantum computers are not big enough to be a threat to quantum, to pre-quantum schemes unless you have some toy keysums. But for real deployments, it's not a threat yet, but it might be within the next couple of years. It's really difficult to foresee the development there and the largest quantum computers are actual quantum annealers that work differently, like quantum annealing is a different thing, a different kind of quantum computer that we're not too worried about right now. Like thats D-Wave for example. But yeah, so right now, they're not a threat, but they might be in the near future. Krijn: And especially so with regards to why you still switch to post-quantum crypto, is this idea that well, standardizing crypto and then integrating crypto and all of this takes years, as we know from that transition to elliptic curve crypto. So even if this quantum computer is 10 15 years away then still this whole transition thing will take so long that by the end of it, how long will your original data have been safe for? It's anybody's guess. Ruben: Yeah. I mean, you have to see asymmetric crypto is everywhere. Like, for example, also kind of example maybe in my passport, like my travel document. And there are documents, for example, out there that are valid for 10 years like, I think, a proper passport and all that kind of stuff. And of course, it really takes long also with these kinds of things, like documents like that are issued by governments. It just takes time, it takes a lot of time. Herald: OK, thank you very much. I should also note that from the signal angel, there have been several very enthusiastic responses from the audience and not so much questions about your talk, that's also very interesting. So thank you so much for doing this, and maybe see you around. Krijn: Thank you. Ruben: Bye bye! rc3 postroll music Subtitles created by c3subtitles.de in the year 2021. Join, and help us!