Paper 2013/653

RKA-KDM secure encryption from public-key encryption

Florian Böhl, Gareth T. Davies, and Dennis Hofheinz


We construct secret-key encryption (SKE) schemes that are secure against related-key attacks and in the presence of key-dependent messages (RKA-KDM secure). We emphasize that RKA-KDM security is not merely the conjunction of individual security properties, but covers attacks in which ciphertexts of key-dependent messages under related keys are available. Besides being interesting in their own right, RKA-KDM secure schemes allow to garble circuits with XORs very efficiently (Applebaum, TCC 2013). Until now, the only known RKA-KDM secure SKE scheme (due to Applebaum) is based on the LPN assumption. Our schemes are based on various other computational assumptions, namely DDH, LWE, QR, and DCR. We abstract from Applebaum’s construction and proof, and formalize three generic technical properties that imply RKA-KDM security: one property is IND-CPA security, and the other two are the existence of suitable oracles that produce ciphertexts under related keys, resp. of key-dependent messages. We then give simple SKE schemes that achieve these properties. Our constructions are variants of known KDM-secure public-key encryption schemes. To additionally achieve RKA security, we isolate suitable homomorphic properties of the underlying schemes in order to simulate ciphertexts under related keys in the security proof. From a conceptual point of view, our work provides a generic and extensible way to construct encryption schemes with multiple special security properties.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
related key attackskey-dependent message securitygarbled circuits
Contact author(s)
gareth davies @ bristol ac uk
2013-12-03: revised
2013-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Florian Böhl and Gareth T.  Davies and Dennis Hofheinz},
      title = {RKA-KDM secure encryption from public-key encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2013/653},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.