6
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ A KEM and a two-move key-exchange are the same thing described with different syntax. $\endgroup$
    – Maeher
    Feb 27, 2023 at 11:00
  • $\begingroup$ If I interpreted it correctly, I agree with Maeher. KEM is more general than a peer-symmetric key exchange. $\endgroup$
    – DannyNiu
    Feb 27, 2023 at 12:29

3 Answers 3

8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.