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

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!