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