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