Subject: Re: [Pqc-forum] Key Establishment for PQC algorithms From: Christopher J Peikert Date: Fri, 28 Oct 2016 15:44:22 -0400 To: "Moody, Dustin (Fed)" CC: pqc-forum Message-ID: Greetings, Summary: interactive key-exchange (KEX) protocols and (unidirectional) key encapsulation mechanisms (KEM) are completely different beasts, each with their own particular use cases and incomparable security requirements. So NIST certainly should not conflate the two or treat them interchangeably. Instead, it should request proposals for both kinds of objects, being clear about which security properties they are expected to satisfy. Details: While it is possible to *syntactically* (at an API level) convert some KEX protocols to KEMs and vice versa, the *security properties* usually asked of these objects are very different. I say "some KEX protocols" because others can involve a combination of long-lived and ephemeral keys/messages, and are ill-fit to the KEM model. For KEX protocols, a long line of important works has established some very subtle attack models and strong security requirements, e.g., Bellare-Rogaway, Canetti-Krawczyk, etc. These capture desirable security properties like forward secrecy, one-sided or mutual authentication, key confirmation, etc. etc. Many such properties -- especially forward secrecy -- are by now considered non-negotiable by many (if not most) theorists and practitioners alike. By contrast, basic security properties like IND-CCA2 for KEMs may not, or do not, provide the above-mentioned properties in a KEX context. For example, in typical usage a KEM public key is long lived ("static"), and therefore provides no forward security. One can of course generate a new KEM keypair every time a new pairwise key is needed, but then one needs an additional mechanism to ensure that the new public key is authentic, etc. etc. So one still has to design a good KEX protocol around the KEM to get the requisite security properties. And in the end, it may be that a CCA2-secure KEM was unnecessary in the first place. In addition, the real-world efficiency profiles of one kind of object may change significantly when it is converted to the other. E.g., a KEX might do additional work that is unnecessary for obtaining just IND-CCA2 security, while a KEM might have slow key generation that is acceptable for rare use, but too slow to be run every time a new pairwise key is needed. There is also precedent for treating KEX and KEM differently: NIST SP800 56A (revision 2) separately defines interactive "Key Agreement Schemes" (aka KEX) and non-interactive "Key Transport Schemes" (aka KEM). In conclusion, I do not believe it makes sense to treat KEX and KEM as interchangeable, or to force them into the same API. What was the rationale for this change? Those (like me) who thought that the initial request for a KEX was plainly a good idea may have seen no reason to speak up for its virtues, nor raised the drawbacks of using a KEM for KEX purposes, since that was not part of NIST's initial plans. Sincerely yours in cryptography, Chris Peikert