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

**Permalink:** http://www.ut.ee/~unruh/publications/hofheinz08towards.html