*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!