Encryption-Scheme Security in the Presence of Key-Dependent Messages

Authors: John Black, Phillip Rogaway, and Tom Shrimpton

Reference: Selected Areas in Cryptography 2002 (SAC 2002), Lecture Notes in Computer Science, vol. 2595, Springer-Verlag, 2003.

Abstract: Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example, one encrypts using a shared key K the value K. Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the public-key and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model. By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under ``formal'' models of security can, in time, be safely realized by generically instantiating their primitives.

Availability: pdf or ps

Rogaway's home page.