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).Category / Keywords: Key-dependent message security, security proofs, symmetric encryption schemes Publication Info: To be published at Eurocrypt 2008 Date: received 22 Aug 2007, last revised 13 Jan 2008 Contact author: unruh at cs uni-sb de Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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. Version: 20080113:194827 (All versions of this report) Discussion forum: Show discussion | Start new discussion