International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Michael Backes
Birgit Pfitzmann
Andre Scedrov
Search ePrint
Search Google
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.
  title={Key-dependent Message Security under Active Attacks -- BRSIM/UC-Soundness of Symbolic Encryption with Key Cycles},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Key cycles, active KDM security, symbolic encryption, cryptographic soundness},
  note={ 13629 received 21 Nov 2005, last revised 26 Apr 2007},
  author={Michael Backes and Birgit Pfitzmann and Andre Scedrov},