Cryptology ePrint Archive: Report 2005/421

Key-dependent Message Security under Active Attacks -- BRSIM/UC-Soundness of Symbolic Encryption with Key Cycles

Michael Backes and Birgit Pfitzmann and Andre Scedrov

Abstract: Key-dependent message security, short KDM security, was introduced by Black, Rogaway and Shrimpton to address the case where key cycles occur among encryptions, e.g., a key is encrypted with itself. It was mainly motivated by key cycles in Dolev-Yao models, i.e., symbolic abstractions of cryptography by term algebras, and a corresponding soundness result was later shown by Ad\~{a}o et al. However, both the KDM definition and this soundness result do not allow the general active attacks typical for Dolev-Yao models and for security protocols in general.

We extend these definitions so that we can obtain a soundness result under active attacks. We first present a definition AKDM as a KDM equivalent of authenticated symmetric encryption, i.e., it provides chosen-ciphertext security and integrity of ciphertexts even for key cycles. However, this is not yet sufficient for the desired soundness, and thus we give a definition DKDM that additionally allows limited dynamic revelation of keys. We show that this is sufficient for soundness, even in the strong sense of blackbox reactive simulatability (BRSIM)/UC and including joint terms with other operators.

We also present constructions of schemes secure under the new definitions, based on current KDM-secure schemes. Moreover, we explore the relations between the new definitions and existing ones for symmetric encryption in detail, in the sense of implications or separating examples for almost all cases.

Category / Keywords: secret-key cryptography / Key cycles, active KDM security, symbolic encryption, cryptographic soundness

Date: received 21 Nov 2005, last revised 26 Apr 2007

Contact author: backes at cs uni-sb de

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Accepted at CSF'07. Improved presentation.

Version: 20070426:061205 (All versions of this report)

Discussion forum: Show discussion | Start new discussion