Why did post-quantum key exchanges go extinct?

On July 5, 2022, NIST chooses one KEM (Key Encapsulation Mechanism) as a PQC standard and 4 KEMs as four-round candidates. Why aren't there any key exchanges?

Similarly, KEMs are usually studied in literature. The post-quantum key exchanges in literature are very rare. Moreover, in those key exchanges, the message to be shared is generated by one party. I do not see any post-quantum key exchange that creates a shared secret with the contributions of both parties, like in Diffie-Hellman.

I do not see any post-quantum key exchange that creates a shared secret with the contributions of both parties, like in Diffie-Hellman.

Actually, in Kyber, the shared secret is a function of contributions of both parties.

On a successful exchange, Kyber outputs the shared secret:

$$KDF( G( M, H( PK )), H( C ))$$

where:

• $M$ is a value that the encryptor picks
• $PK$ is a value that the decryptor picks (his public key, actually)
• $C$ is the ciphertext the decryptor generates
• $KDF, G, H$ are one way functions.

Because this output is a noninvertible function that includes inputs from both sides, neither side can control it.

Principally because NIST did not make key exchanges a necessary part of the process. If we look at the NIST PQC FAQ "NIST provided APIs and security definitions for Public Key encryption, KEM, and digital signature. Why are other functionalities not included?" NIST state:

NIST is looking primarily to replace quantum-vulnerable schemes with functionalities that are widely used, have widely agreed upon security and correctness definitions in academic literature, and for which there appear to be a range of promising approaches for designing a postquantum replacement. NIST considered a number of other functionalities, but did not provide explicit support for them, since it did not feel they met the above criteria as well as encryption, KEM, and signature. In many cases, NIST expects that schemes providing some of these functionalities may be submitted as a special case or an extension of one of the functionalities we explicitly asked for. In such a case, any additional functionality would be considered an advantage as noted in section 4.C.1 of our Call for Proposals. Two particular functionalities NIST considered were authenticated key exchange (AKE), and a drop in replacement for Diffie-Hellman.

... However, NIST believes that in its most widely used applications, such as those requiring forward secrecy, Diffie-Hellman can be replaced by any secure KEM with an efficient key generation algorithm. The additional features of Diffie-Hellman may be useful in some applications, but there is no widely accepted security definition of which NIST is aware that captures everything one might want from a Diffie-Hellman replacement.

There are post-quantum key exchanges such as the Ding key exchange which was a significant step towards the design of Kyber (per reference 39 of the Kyber specification) and the earlier NewHope key exchange. Other PQC key exchange proposals include the the Supersingular Isogeny Key Exchange (SIDH/SIKE).

As others have mentioned, in lattice-based key exchange the derived secret is a function of contributions of both parties. In fact, the standardized algorithms are very "diffie-hellman-like" in practice (the design paradigm goes by the name of noisy diffie hellman).

There is a significant difference with standard diffie hellman though, namely that DH key exchange forms what is known as non-interactive key exchange (NIKE). There are some strong information-theoretic barriers to giving such a construction using common lattice-based design paradigms. In particular, there are some known impossibility results from constructions that use (polynomially-large) moduli $q$.

Interestingly, yesterday a new lattice-based KEM has been proposed, roughly looking at how efficient one can make lattice-based NIKE (by accepting the fact that one needs $q$ super-polynomially large). This is to say that if you really like DH-type schemes, and the lattice-based versions of them that aren't NIKE aren't good enough for you, there's a lattice-based candidate you can look into now :)