[CFRG] KEM combiners design team output

[Stephen Farrell <[e-mail]>]

Hi all,

We'd like to share the outcome of the Hybrid KEM requirements design
team. First, not everyone from the announced design team could make
the calls we had, so the blame for this output should be shared between
Aron, Bas, Deirdre, Mike, Nick and Stephen.

Our considerations distilled from the discussions within the research group.

(1) There are valid but conflicting preferences for a hybrid PQ/T KEM
expressed in earlier discussions in the research group; a single KEM
will not do. ([1,2,3] are just a few sample emails showing diverse
opinions.)

(2) Given recent work [4] on binding properties [5], there is a general
lack on clarity on KEM security properties.

(3) By its very nature, there are many choices that have to be made for
a hybrid KEM. Without coordination, this will lead (and has led) to
needlessly incompatible KEMs and duplicate effort.

(4) There are stakeholders that want to adopt some PQ/T hybrid, once
NIST finishes ML-KEM this summer.

Hence, we propose that the CFRG produce a document "Hybrid PQ/T Key
Encapsulation Mechanisms", which will cover the following.

(A) Identify which KEM security properties are IETF-relevant, and
provide a terse overview of those security properties (eg. IND-CCA,
LEAK-BIND-K-PK, HON-BIND-K-CT, etc), as well as security properties
unique to hybrid KEMs (component key material reuse between hybrid and
non-hybrid uses or between multiple hybrids, one component is malicious
while the other is honest, etc) with reference to literature, and put
into context with real-world attacks. From that, give guidance on a
sensible baseline.

(B) Provide a terse overview of well-reviewed techniques that are
options to safely produce the concrete combinations in (C), and which
security properties are achieved given those of the constituents.

(C) Provide an initial number of explicit PQ/T hybrid KEMs using
techniques from (B) that reach the baseline set in (A), and should include:

       (I)  a hybrid of P-256 and ML-KEM-768,
       (II)  a hybrid of X25519 and ML-KEM-768, and,
       (III) a hybrid of P-384 and ML-KEM-1024.

These hybrids should be accompanied by pseudocode and test vectors.

This list includes two options at the ~128-bit security level (due to
current implementation/deployment trends) and one at a higher level.

The DT would be happy for the RG to omit C(I) above should there not be
significant implementations for which C(II) and C(III) are hard. The DT
did not attempt to survey implementations to determine this.

There is demand for other hybrid variants that either use different
primitives (RSA, NTRU, Classic McEliece, FrodoKEM), parameters, or that
use a combiner optimized for a specific use case. The DT recommends the
work outlined in (C) is done in a first document, and other use cases
could be covered in subsequent documents.

Regards,
The DT.

[1]: https://mailarchive.ietf.org/arch/msg/cfrg/ZYd_q7QP17EtHtvSj60eSeJvkX0/
[2]: https://mailarchive.ietf.org/arch/msg/cfrg/wfXX0xvooCdQb3THtRLxBdwCB68/
[3]: https://mailarchive.ietf.org/arch/msg/cfrg/HaeAK6MdANmZ8UYGPWWeIK5_OP0/
[4]: https://eprint.iacr.org/2023/1933.pdf
[5]: https://eprint.iacr.org/2024/702.pdf