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