Douglas Stebila

Split-key PRFs and extended hybrid security for KEM combiners

Abstract

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.

Keywords: hybrid security, key encapsulation mechanism, combiners, split-key pseudorandom function

Reference

Lise Millerjord, Douglas Stebila, Camryn Steckel. Split-key PRFs and extended hybrid security for KEM combiners. IACR Communications in Cryptology, 2(4):17. January 2026. © The authors.

Download

BibTeX

@article{CIC:MilSteSte26,
 	Author = {Lise Millerjord and Douglas Stebila and Camryn Steckel},
 	Doi = {10.62056/ah890lmol},
 	Journal = {IACR Communications in Cryptology},
 	Month = jan,
 	Number = {4},
 	Pages = {17},
 	Title = {Split-key {PRF}s and extended hybrid security for {KEM} combiners},
 	Volume = {2},
 	Year = {2026}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
• NSERC Alliance grant ALLRP 578463-22
• Research Council of Norway under Project No. 288545
• NSERC Alexander Graham Bell Canada Graduate Scholarship - Doctoral