## Kyber and Post-Quantum Crypto - How does it work?

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

more » « less
Video Language:
English
Duration:
01:02:41
 alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work? alcuna edited English subtitles for Kyber and Post-Quantum Crypto - How does it work?

• Edited
alcuna