Split-key PRFs and a new notion for hybrid KEM security

In 2018, Giacon, Heuer, and Poettering introduced the idea of combiners for key encapsulation mechanisms (KEMs) . A parallel KEM combiner takes in ℓ ingredient KEMs K₁, . . . ,K_ℓ and a core function W, and produces a combined KEM K by computing (\(k\)_i, \(c\)_i) ← K_i.Enc(pk_i) for each of the ingredient KEMs, applying the core function to obtain the shared secret \(k\) ← W(k₁, . . . , \(k\)_ℓ, \(c\)1∥ . . . ∥c_ℓ), and finally outputting (\(k\), \(c\)₁∥ . . . ∥\(c\)_ℓ). They showed that if W is a split-key PRF — meaning that it is a secure PRF in any one of its ℓ key arguments — and at least one of the ingredient KEMs is IND-CCA-secure, then the combined KEM satisfies IND-CCA security for KEMs. This yields a hybrid security result, suitable for combining traditional and post-quantum algorithms: the combined KEM is secure as long as at least one of the underlying KEMs is not broken. Additionally, they provided a few constructions for split-key PRFs: several in the random oracle model and one in the standard model.