Paper 2007/333

Towards Key-Dependent Message Security in the Standard Model

Dennis Hofheinz and Dominique Unruh


Standard security notions for encryption schemes do not guarantee any security if the encrypted messages depend on the secret key. Yet it is exactly the stronger notion of security in the presence of key-dependent messages (KDM security) that is required in a number of applications: most prominently, KDM security plays an important role in analyzing cryptographic multi-party protocols in a formal calculus. But although often assumed, the mere existence of KDM secure schemes is an open problem. The only previously known construction was proven secure in the random oracle model. We present symmetric encryption schemes that are KDM secure in the standard model (i.e., without random oracles). The price we pay is that we achieve only a relaxed (but still useful) notion of key-dependent message security. Our work answers (at least partially) an open problem posed by Black, Rogaway, and Shrimpton. More concretely, our contributions are as follows: - We present a (stateless) symmetric encryption scheme that is information-theoretically secure in face of a bounded number and length of encryptions for which the messages depend in an arbitrary way on the secret key. - We present a stateful symmetric encryption scheme that is computationally secure in face of an arbitrary number of encryptions for which the messages depend only on the respective current secret state/key of the scheme. The underlying computational assumption is minimal: we assume the existence of one-way functions. - We give evidence that the only previously known KDM secure encryption scheme cannot be proven secure in the standard model (i.e., without random oracles).

Note: This revision contains changes in the explanatory text and corrections of minor mistakes. The results of this paper have not changed. We thank the anonymous referees for their input.

Available format(s)
Publication info
Published elsewhere. To be published at Eurocrypt 2008
Key-dependent message securitysecurity proofssymmetric encryption schemes
Contact author(s)
unruh @ cs uni-sb de
2008-01-13: revised
2007-08-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz and Dominique Unruh},
      title = {Towards Key-Dependent Message Security in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2007/333},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.