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