Paper 2011/269

Authenticated and Misuse-Resistant Encryption of Key-Dependent Data

Mihir Bellare and Sriram Keelveedhi


This paper provides a comprehensive treatment of the security of authenticated encryption (AE) in the presence of key-dependent data, considering the four variants of the goal arising from the choice of universal nonce or random nonce security and presence or absence of a header. We present attacks showing that universal-nonce security for key-dependent messages is impossible, as is security for key-dependent headers, not only ruling out security for three of the four variants but showing that currently standarized and used schemes (all these target universal nonce security in the presence of headers) fail to provide security for key-dependent data. To complete the picture we show that the final variant (random-nonce security in the presence of key-dependent messages but key-independent headers) is efficiently achievable. Rather than a single dedicated scheme, we present a RO-based transform RHtE that endows ANY AE scheme with this security, so that existing implementations may be easily upgraded to have the best possible seurity in the presence of key-dependent data. RHtE is cheap, software-friendly, and continues to provide security when the key is a password, a setting in which key-dependent data is particularly likely. We go on to give a key-dependent data treatment of the goal of misuse resistant AE. Implementations are provided and show that RHtE has small overhead.

Available format(s)
Publication info
Published elsewhere. Preliminary version appears in proceedings of CRYPTO 2011. This is the full version.
Authenticated encryptionsymmetric encryptionrandom oracles
Contact author(s)
sriramkr @ cs ucsd edu
2011-05-30: last of 2 revisions
2011-05-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Sriram Keelveedhi},
      title = {Authenticated and Misuse-Resistant Encryption of Key-Dependent Data},
      howpublished = {Cryptology ePrint Archive, Paper 2011/269},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.