Paper 2013/567

KDM Security in the Hybrid Framework

Gareth T. Davies and Martijn Stam


We study the natural question of how well suited the hybrid encryption paradigm is in the context of key-dependent message (KDM) attacks. We prove that if a key derivation function (KDF) is used in between the public (KEM) and symmetric (DEM) part of the hybrid scheme and this KDF is modelled as a random oracle, then one-wayness of the KEM and indistinguishability of the DEM together suffice for KDM security of the resulting hybrid scheme. We consider the most general scenario, namely CCA attacks and KDM functions that can call the random oracle. Although the result itself is not entirely unsuspected -- it does solve an open problem from Black, Rogaway, and Shrimpton (SAC 2002) -- proving it is considerably less straightforward; we develop some proof techniques that might be applicable in a wider context.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
KDM SecurityHybrid EncryptionKEMDEMPublic Key Encryption.
Contact author(s)
csgtd @ bristol ac uk
2013-09-09: revised
2013-09-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gareth T.  Davies and Martijn Stam},
      title = {KDM Security in the Hybrid Framework},
      howpublished = {Cryptology ePrint Archive, Paper 2013/567},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.