Split-key PRFs and Extended Hybrid Security for KEM Combiners

Key encapsulation mechanism (KEM) combiners allow for the construction of hybrid KEMs that are secure as long as at least one of several underlying ingredient KEMs remains secure. In PKC 2018, Giacon, Heuer, and Poettering showed that parallel KEM combiners whose core function is a split-key pseudorandom function (PRF) satisfy IND-CCA security if at least one of the ingredient KEMs satisfies IND-CCA security. However, their result assumes that public keys of the combined KEM are generated independently from any instances of the ingredient KEMs, which may not hold in real-world applications. To address this, we introduce a new security model which captures adversarial access to both the combined KEM and (post-processed versions of) the ingredient KEMs. We show that security in this extended model can still be achieved if at least one ingredient KEM satisfies IND-CCA security, the core function is a split-key PRF, and the ingredient KEM outputs are post-processed using standard PRFs. We consider an application of this approach to hybrid KEMs in the S/MIME secure email standard. We also provide a new construction for a split-key PRF, which uses a t-resilient extractor to output a string of truly random bits from an input in which the adversary controls t bits, and show that this split-key PRF construction is secure in the standard model.