[00:00.000 --> 00:15.800]  We are starting in a couple of seconds, so welcome, Norbert.
[00:15.800 --> 00:16.800]  Thank you.
[00:16.800 --> 00:18.560]  I hope you can hear me, right?
[00:18.560 --> 00:20.600]  So yeah, my name is Norbert Poč.
[00:20.600 --> 00:29.000]  I work at Red Hat, and today I will talk about hybrid public encryption, and later we will
[00:29.000 --> 00:32.000]  source it with, like, some post-quantum.
[00:32.000 --> 00:37.000]  Okay, so is here anybody who already knows about HPK?
[00:37.000 --> 00:39.000]  Please raise your hand.
[00:39.000 --> 00:40.000]  Oh, nice.
[00:40.000 --> 00:42.000]  There's quite a few people.
[00:42.000 --> 00:43.000]  Okay.
[00:43.000 --> 00:47.000]  Okay, so who doesn't know?
[00:47.000 --> 00:50.000]  HPK stands for hybrid public key encryption.
[00:50.000 --> 00:59.000]  It's a symmetric and f-symmetric, like, it's combining both into a scheme.
[00:59.000 --> 01:03.000]  It uses a key encapsulation mechanism.
[01:03.000 --> 01:05.000]  It's used for key exchange.
[01:05.000 --> 01:10.000]  It's, like, key exchanges, like, you have, like, Diffie-Hellman.
[01:10.000 --> 01:14.000]  This is a bit different approach.
[01:14.000 --> 01:20.000]  You can find the RFC in the 9180.
[01:20.000 --> 01:26.000]  So, yeah, we have the fundamental parts of the HPK scheme.
[01:26.000 --> 01:32.000]  You have, like, key encapsulation method, the key derivation, or key schedule, and the
[01:32.000 --> 01:38.000]  AEAD, which provides the encryption of the messages itself.
[01:38.000 --> 01:44.000]  Below, you can see listed the algorithms, which are supported.
[01:44.000 --> 01:49.000]  For the key encapsulation method, we have prime, curves, and Edward curves.
[01:49.000 --> 02:00.000]  For the key derivation, we use SHA versions, and AEAD supports AES and Chachapoly.
[02:00.000 --> 02:04.000]  So, yeah, some familiar, like, words.
[02:04.000 --> 02:10.000]  You will find later, for the CAM operations, we have K generations,
[02:10.000 --> 02:13.000]  and encapsulation and the encapsulation.
[02:13.000 --> 02:17.000]  For the KDF, we have extract and expand.
[02:17.000 --> 02:23.000]  The extract generates a key from some input data, and the expand
[02:23.000 --> 02:33.000]  expands this extracted K to some length, we wish.
[02:33.000 --> 02:39.000]  For the AEAD, we have seal and open, which are encrypt and decrypt.
[02:39.000 --> 02:43.000]  It's just an LES to it.
[02:43.000 --> 02:48.000]  Okay, so let's talk about how does it work.
[02:48.000 --> 02:56.000]  At the one side, you can see the CAM and the case schedule, encryption context, and AEAD.
[02:56.000 --> 03:02.000]  Encryption context divides asymmetric on the left and symmetric on the right.
[03:02.000 --> 03:11.000]  This is really important, because, like, we'll see later, that this diversion
[03:11.000 --> 03:20.000]  enables us to change parts in it and leave the scheme still intact.
[03:20.000 --> 03:26.000]  So, let's say we want to use, like, different algorithms for the KDF method,
[03:26.000 --> 03:34.000]  and, like, we just change it and all, like, can proceed with the scheme itself.
[03:34.000 --> 03:44.000]  So, we use K derivation to the KNGAP solution, create an encryption context,
[03:44.000 --> 03:52.000]  which means which will consist of data we will need to do encryption
[03:52.000 --> 03:57.000]  or some data or messages in the AEAD.
[03:57.000 --> 04:02.000]  Yeah, and the last part, like, the symmetric part is the AEAD,
[04:02.000 --> 04:08.000]  where we, like, grab some messages, encrypt it, and, like, send it over.
[04:08.000 --> 04:11.000]  So, this is the communication part.
[04:11.000 --> 04:14.000]  Now, I want some feedback from the last row.
[04:14.000 --> 04:17.000]  Is it readable?
[04:17.000 --> 04:19.000]  Okay, thank you.
[04:19.000 --> 04:22.000]  So, this is a formal diagram. How does it work?
[04:22.000 --> 04:24.000]  I will go it through.
[04:24.000 --> 04:30.000]  So, we have Bob on the right and Alice on the left.
[04:30.000 --> 04:38.000]  We will assume that Bob has some private key which already shared with Alice.
[04:38.000 --> 04:41.000]  We don't care in the HPK how.
[04:41.000 --> 04:46.000]  So, let's pretend that Alice knows the public key of Bob.
[04:46.000 --> 04:49.000]  Then we will start with the encapsulation.
[04:49.000 --> 04:58.000]  So, Alice generates a temporary key pair called fmrl.
[04:58.000 --> 05:00.000]  Okay, it's visible.
[05:00.000 --> 05:05.000]  So, here, it's the PKE and SKE.
[05:05.000 --> 05:16.000]  And we will use Bob's private key and Alice's private, sorry, public key and private key to make,
[05:16.000 --> 05:22.000]  like, Diffie-Hellman, which will give us a shared secret.
[05:22.000 --> 05:28.000]  Then we use the shared secret in the KD version function to create a common key.
[05:28.000 --> 05:39.000]  Then we send over our public fmrl key to Bob so he can do the same to get the shared secret.
[05:39.000 --> 05:47.000]  Here, like, so we encapsulate it, send it over, and now we are at Bob.
[05:47.000 --> 05:50.000]  Bob does the encapsulation.
[05:50.000 --> 05:54.000]  He has his private key and Alice's public key.
[05:54.000 --> 05:57.000]  Does the Diffie-Hellman get the same shared secret?
[05:57.000 --> 06:01.000]  The shared secret is, again, used at the KDF, and we have a common key.
[06:01.000 --> 06:06.000]  So, the common key is the same at Alice and Bob.
[06:06.000 --> 06:11.000]  This is the end of the K encapsulation part.
[06:11.000 --> 06:14.000]  Now we move to K schedule.
[06:14.000 --> 06:24.000]  So, we get this common key, use the extract to generate some salt, let's say,
[06:24.000 --> 06:30.000]  then expand it to get a key, and expand it one more time,
[06:30.000 --> 06:36.000]  but with different information, as you can see here, to get an answer.
[06:36.000 --> 06:44.000]  And then the third one is secret for exportation.
[06:44.000 --> 06:48.000]  So, now we have set up the communication,
[06:48.000 --> 06:53.000]  and we can do actually encrypted message conversations,
[06:53.000 --> 06:56.000]  which is the seal and the open.
[06:56.000 --> 07:01.000]  As you can see, we use the key, the nonce,
[07:01.000 --> 07:08.000]  some additional information and the key, the private text, plain text.
[07:08.000 --> 07:10.000]  Thank you.
[07:10.000 --> 07:14.000]  So, here, you can see XOR.
[07:14.000 --> 07:17.000]  The messages are counted.
[07:17.000 --> 07:22.000]  So, every message has a counter and we explore it with the nonce.
[07:22.000 --> 07:26.000]  Therefore, every message will be different,
[07:26.000 --> 07:31.000]  even if the message is like the same.
[07:31.000 --> 07:36.000]  So, if the plain text is the same, we will get a different cipher text.
[07:36.000 --> 07:38.000]  That's the reason.
[07:38.000 --> 07:41.000]  Okay, so, we have this nice scheme.
[07:41.000 --> 07:43.000]  What can we use it for?
[07:43.000 --> 07:49.000]  Possible messages are the MLS or messaging layer security.
[07:49.000 --> 07:52.000]  It's quite new stuff.
[07:52.000 --> 07:57.000]  I think, maybe one year old.
[07:57.000 --> 08:02.000]  The MLS uses...
[08:02.000 --> 08:07.000]  So, MLS solves a problem where we want to communicate.
[08:07.000 --> 08:11.000]  We have communicating parties more than two.
[08:11.000 --> 08:13.000]  So, let's say, I want to communicate with you,
[08:13.000 --> 08:16.000]  but I want to communicate with you and you and you.
[08:16.000 --> 08:20.000]  So, it's harder to exchange keys this way
[08:20.000 --> 08:25.000]  because when we have, like, a two-way communication, it's easier, right?
[08:25.000 --> 08:28.000]  So, this is the problem that MLS solves.
[08:28.000 --> 08:37.000]  Then we have the TLS client hello and Oblivios DNS over HTTPS.
[08:37.000 --> 08:41.000]  The last one is, I think, Nu1.2.
[08:41.000 --> 08:49.000]  That solves the encryption of the IP address of the requester.
[08:49.000 --> 08:53.000]  Okay, so, HPK comes with three modes.
[08:53.000 --> 08:55.000]  The first one is the basic,
[08:55.000 --> 09:01.000]  and then there are two more, providing authentication.
[09:01.000 --> 09:05.000]  We have authentication mode with private key
[09:05.000 --> 09:11.000]  or a pre-shared key in a PSK mode, or we can combine the both
[09:11.000 --> 09:16.000]  and have the old PSK mode.
[09:16.000 --> 09:18.000]  What about the security?
[09:18.000 --> 09:25.000]  The base mode is programmed to be secure
[09:25.000 --> 09:31.000]  against indistinguishability ciphertext,
[09:31.000 --> 09:37.000]  and the authenticated modes are outside there and inside the CCS secure.
[09:37.000 --> 09:44.000]  Yeah, so, later on, you can find a report at the references.
[09:44.000 --> 09:50.000]  So, let's move to the post-quantum stuff.
[09:50.000 --> 09:56.000]  As I said before, the key encapsulation and the AEAD are separated.
[09:56.000 --> 10:02.000]  So, to make it post-quantum, we can just put post-quantum algorithms
[10:02.000 --> 10:10.000]  to the key encapsulation method, and we will get post-quantum HPK.
[10:10.000 --> 10:13.000]  The proposal was for kyber and psych,
[10:13.000 --> 10:17.000]  but as most of you know, psych is already out of the game.
[10:17.000 --> 10:23.000]  Kyber is one of the NIST finalists for key exchange methods.
[10:23.000 --> 10:30.000]  It uses chem the same way instead of DH-style key exchange.
[10:30.000 --> 10:35.000]  It is a lattice-based game standing upon learning with errors
[10:35.000 --> 10:45.000]  and running problem, and kyber is proven to be IND CCS secure too.
[10:45.000 --> 10:50.000]  Yeah, so we have this nice diagram again.
[10:50.000 --> 10:53.000]  There we can see hybrid version.
[10:53.000 --> 10:58.000]  We have post-quantum only version of HPK and hybrid.
[10:58.000 --> 11:06.000]  Hybrid uses post-quantum and the old algorithms too for the key encapsulation method.
[11:06.000 --> 11:11.000]  Like if one breaks, you can still have some security.
[11:11.000 --> 11:16.000]  So, you can see gray boxes here.
[11:16.000 --> 11:23.000]  These boxes are the old algorithms,
[11:23.000 --> 11:28.000]  which means if we eliminate them, the post-quantum version will be visible.
[11:28.000 --> 11:34.000]  That means the same way, so first I will go through the post-quantum.
[11:34.000 --> 11:41.000]  The same way Bob generates the key pair prior HPK,
[11:41.000 --> 11:45.000]  and let's say that Alice already knows that key.
[11:45.000 --> 11:53.000]  The difference here is that we don't do classical Diffie-Hellman,
[11:53.000 --> 12:02.000]  but we encrypt some random data and we will get a shared secret here.
[12:02.000 --> 12:12.000]  And the ciphertext of that shared secret.
[12:12.000 --> 12:17.000]  Then we do the key derivation to get the common key,
[12:17.000 --> 12:23.000]  send over the ciphertext of the shared secret to Bob,
[12:23.000 --> 12:28.000]  who can decrypt it and do the same here.
[12:28.000 --> 12:35.000]  And as you can see, everything else is the same as the basic HPK.
[12:35.000 --> 12:47.000]  For the hybrid mode, the only difference is here.
[12:47.000 --> 12:56.000]  So, for the KDF, the post-quantum and the basic shared secret is concatenated,
[12:56.000 --> 13:01.000]  and everything else should be the same.
[13:01.000 --> 13:05.000]  Okay, so what is the security of the post-quantum?
[13:05.000 --> 13:10.000]  In the base mode, it's still INCCI2 secure
[13:10.000 --> 13:17.000]  because the KM algorithm is proven to be INCCI2 secure.
[13:17.000 --> 13:23.000]  For the hybrid mode, it needs more proof because the concatenation there,
[13:23.000 --> 13:34.000]  and the authentication for both hybrid and PQ only would need more work.
[13:34.000 --> 13:37.000]  So, let's see some benchmarks.
[13:37.000 --> 13:44.000]  I got this benchmark from the paper, which you can see below.
[13:44.000 --> 13:53.000]  They were done on Intel Core E7 with 4 cores, 8 megabytes of cache and 8 megabytes of RAM,
[13:53.000 --> 14:01.000]  using AWC LST, cryptographic library.
[14:01.000 --> 14:09.000]  And the environment, each algorithm was run 10,000 times,
[14:09.000 --> 14:17.000]  and the first and fourth quartile was eliminated of the measures to make it more accurate.
[14:17.000 --> 14:25.000]  The measures are in CPU clock cycles, and I think it was medium or something like that.
[14:25.000 --> 14:31.000]  Okay, so here you can see Psyche, which is now eliminated,
[14:31.000 --> 14:38.000]  but I think it's a nice reference that it was a lot slower.
[14:38.000 --> 14:47.000]  So, this blue one is the basic Edward curve, like the basic HPK,
[14:47.000 --> 14:58.000]  then the green one is a hybrid one, and yeah, here the yellow is kyber only.
[14:58.000 --> 15:06.000]  And as you can see, it is faster than the Edward curve, which is interesting.
[15:06.000 --> 15:09.000]  Then there is one more graph.
[15:09.000 --> 15:21.000]  Here you can see the green lines, which tells us that the ky encapsulation method is constant time,
[15:21.000 --> 15:27.000]  so it doesn't constant in a way that it doesn't affect the encryption itself,
[15:27.000 --> 15:38.000]  because the tests were done for data encryption for 1 kilobyte of data, 10 kilobyte, 100 kilobyte, and 1 megabyte of data.
[15:38.000 --> 15:45.000]  So, as you can see, the cost is more on the encryption of the data itself.
[15:45.000 --> 15:48.000]  So, there is a red line.
[15:48.000 --> 16:02.000]  You can see that's for reference. This is a version of LSA encrypting 240 bytes of data.
[16:02.000 --> 16:06.000]  Yeah, so here you can see references if you want to read more about it,
[16:06.000 --> 16:08.000]  and thank you for attention.
[16:08.000 --> 16:20.000]  So, any questions?
[16:20.000 --> 16:26.000]  We had some questions on metrics, so I will try to read it.
[16:26.000 --> 16:32.000]  The question was, how do we make quantum resistant crypto work on constrained devices?
[16:32.000 --> 16:33.000]  What?
[16:33.000 --> 16:51.000]  How do we make quantum resistant crypto work on constrained devices?
[16:51.000 --> 16:56.000]  Well, that's a good question. I don't know the answer before, so sorry for that.
[16:56.000 --> 17:07.000]  Okay, so any other question in here?
[17:07.000 --> 17:12.000]  Thank you. The last slide, I think page 15, you showed some benchmarks,
[17:12.000 --> 17:15.000]  but these are on the whole encryption, right?
[17:15.000 --> 17:21.000]  Like, not only the exchange of the keys and the setup of the symmetry key, but the whole exchange, right?
[17:21.000 --> 17:27.000]  They are both. So, as you can see, the green line is like the key exchange itself,
[17:27.000 --> 17:31.000]  and then you have like the seal and the open operation here.
[17:31.000 --> 17:37.000]  So, it's, if you take, for example, one message and one key exchange,
[17:37.000 --> 17:40.000]  that's what the benchmark says, like it's together.
[17:40.000 --> 17:46.000]  Yeah, okay, all right. Which was expected, because anyway, the quantum,
[17:46.000 --> 17:50.000]  the post quantum part is only in the beginning of the exchange.
[17:50.000 --> 17:58.000]  And then when the symmetry key is established, you continue with using your EEAD.
[17:58.000 --> 17:59.000]  Yes, that's correct.
[17:59.000 --> 18:00.000]  All right, thanks.
[18:00.000 --> 18:06.000]  So, the post quantum part is only at the K exchange, and later on it is the same.
[18:06.000 --> 18:08.000]  Okay, any other question?
[18:08.000 --> 18:14.000]  Yeah, I just wanted to say that the post quantum is more about like asymmetric keys.
[18:14.000 --> 18:19.000]  It doesn't really affect the symmetric part, so it's okay.
[18:19.000 --> 18:23.000]  Any other question around here?
[18:23.000 --> 18:27.000]  If not, we can probably, thank you for the talk, thank you for the questions.
[18:27.000 --> 18:53.000]  Thank you for coming.