IACR paper details
Title  Towards KeyDependent Message Security in the Standard Model 

Booktitle  IACR Eprint archive 

Pages  

Year  2007 

URL  http://eprint.iacr.org/2007/333 

Author  Dennis Hofheinz 

Author  Dominique Unruh 

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 *keydependent* messages (KDM security) that is required in a number of applications: most prominently, KDM security plays an important role in analyzing cryptographic multiparty 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 keydependent 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 informationtheoretically 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 oneway 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).


Search for the paper
@misc{eprint200713613,
title={Towards KeyDependent Message Security in the Standard Model},
booktitle={IACR Eprint archive},
keywords={secretkey cryptography / keydependent message security, security proofs, symmetric encryption schemes},
url={http://eprint.iacr.org/2007/333},
note={ Dennis.Hofheinz@cwi.nl 13748 received 22 Aug 2007},
author={Dennis Hofheinz and Dominique Unruh},
year=2007
}
Download a complete BibTeX file.