< Return to Video

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

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

more » « less
Video Language:
English
Duration:
01:02:41

English subtitles

Revisions