[Cryptography] Kyber PQC Key Exchange

[Kristian Gjøsteen]

31. jul. 2022 kl. 17:11 skrev Phillip Hallam-Baker <phill at hallambaker.com>:
> I am trying to get some info on the mechanism underlying NIST's chosen key exchange, Kyber. So far the most accessible explanation is the Python implementation.
> 
> If we are going to adopt a new approach to public key, some of us will want to understand it. And academic papers that spend the entire time referring to the differences with the previous papers are really no help at all.
> 
> So does anyone have a pointer to a YouTube with a good description of the Lattice crypto approach? Just telling me something is a lattice is really telling me nothing at all. It might as well be a Hausdorffian Manifold with Lipschitz signature.
> 
> At least some of the information I have received is inconsistent. I am told that I can't use Kyber as a drop in for ECDH because it is an interactive key exchange. The API seems to suggest otherwise. From a protocol design point of view, there is really no difference between a Key Agreement and a Key Encapsulation that can't be fixed with a bit of Key Wrap.
> 
> The use case I have in mind is:
> 
> 1) Alice exchanges public keys with Bob. 
> 2) Alice writes a Word document and encrypts to Bob's public key
> 3) Alice puts enveloped Word document on thumb drive and mails it to Bob
> 4) Bob gets the thumb drive and decrypts the document.
> 
> From what was said at the CFRG meeting, I was expecting I might have to do an El Gamal like move and create an ephemeral key pair per document to encrypt. But that doesn't seem to be the case looking at the API.
> 
> Then I find mention of 'malleability' which seems utterly odd to me since that is an integrity issue and not a confidentiality concern. And I can't find the word 'malleable' in the paper.

Hi,

Kyber is what cryptographers call a *key encapsulation mechanism* (KEM).

There are two interesting stories here. The first is how Kyber is designed, and the second is how to use a KEM.

*** The first story comes in two parts.

The first part is how to design a public key encryption scheme (PKE) that has weak security (ind-cpa is the accepted technical term, essentially confidentiality against passive adversaries) based on a lattice problem (Module-LWE).

The second is how to turn the PKE into a KEM that has strong security (ind-cca, confidentiality against active adversaries), which uses Fujisaki-Okamoto (FO). FO is a really nice trick that from the late 90s which went out of fashion in the dlog/factoring world because we have better tricks there, but has come back into fashion now, since the dlog/factoring tricks don’t work very well for most post-quantum schemes (for very interesting reasons).

Both of these parts are well-described by the various Kyber papers, if you know the requisite background. If you don’t, I don’t really see how an implementation can help you. There are probably many good introductory videos for lattice cryptography out there, but unless your goal is a superficial explanation of the mechanics, you will probably need more. There are textbooks that will explain this stuff, if you care. Depending on your background and your goal, you will need anything from a few weeks to many years to get up to speed.

«Malleable» is a concept that is important for the first story. The PKE that Kyber is constructed from is trivially malleable.

Integrity and confidentiality is often tightly linked in applications, in the sense that many types of integrity failures lead to confidentiality failures. And vice versa.

In practice, a system designer can often (sometimes?) compensate for malleability in a black box way, but it is usually easier for the cryptographer to deal with this. Which is what FO does.

You usually cannot safely use the PKE scheme for anything sensible unless you are a high-powered cryptographer.


*** The second story has multiple parts, but your use case suggests that you are interested in how to turn the KEM back into a PKE.

(I am guessing that you actually know this stuff, but anyway…)

At this point, it is worth reminding ourselves what the difference between a KEM and a PKE is. We all know what a PKE is. A KEM is a restricted sort of PKE that will only allow you to encrypt random messages (that’s the keys we encapsulate). In particular:
* For a PKE, the encryption algorithm takes an encryption key and a message as input and outputs a ciphertext.
* For a KEM, the encapsulation algorithm takes an encapsulation key as input and outputs a ciphertext and a message (key).
The key generation and decryption/decapsulation algorithms work as you would expect.

So how do we turn a KEM into a PKE? We use a construction called hybrid encryption, where we use the KEM to encapsulate a symmetric key and use a symmetric cryptosystem to encrypt the message. This is essentially simple. If you want multiple recipients, KEMs are slightly more complicated than PKEs. (It is probably possible to do a more efficient multi-recipient scheme based on Kyber, compared to Kyber used as a black box in the obvious fashion.)

Another part of the second story is key exchange.

If you have a KEM, you can do key exchange in a black box way. You can either use just the KEM or add signatures if you feel like it. This is easy and well-explained in textbooks.

If you have a KEM, you can use it in TLS, but TLS is complex, so this is more complicated.

Kyber is not in general a drop-in replacement for DH, but the words «in general» are doing a bit of work here.

DH is best thought of as a key exchange scheme, but any such scheme trivially becomes a KEM. When you think of your DH as a KEM and only as a KEM, then Kyber is usually a drop-in replacement. At least if you don’t care about the length of your messages.

If you use DH in a more complicated fashion, for instance for implicitly authenticated key exchange or in protocols like Signal, you often rely on the symmetry property of DH (both parties do exactly the same mathematical operations). Kyber does not have this property. Which means that it is not a drop-in replacement.

-- 
Kristian Gjøsteen