Cryptology ePrint Archive: Report 2013/653

RKA-KDM secure encryption from public-key encryption

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

Abstract: 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.

Category / Keywords: public-key cryptography / related key attacks, key-dependent message security, garbled circuits

Date: received 10 Oct 2013, last revised 3 Dec 2013

Contact author: gareth davies at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20131203:124215 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]