You are looking at a specific version 20131015:065236 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
related key attackskey-dependent message securitygarbled circuits
Contact author(s)
gareth davies @ bristol ac uk
History
2013-12-03: revised
2013-10-15: received
See all versions
Short URL
https://ia.cr/2013/653
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.