Paper 2016/174

Honey Encryption Beyond Message Recovery Security

Joseph Jaeger, Thomas Ristenpart, and Qiang Tang


Juels and Ristenpart introduced honey encryption (HE) and showed how to achieve message recovery security even in the face of attacks that can exhaustively try all likely keys. This is important in contexts like password-based encryption where keys are very low entropy, and HE schemes based on the JR construction were subsequently proposed for use in password management systems and even long-term protection of genetic data. But message recovery security is in this setting, like previous ones, a relatively weak property, and in particular does not prohibit an attacker from learning partial information about plaintexts or from usefully mauling ciphertexts. We show that one can build HE schemes that can hide partial information about plaintexts and that prevent mauling even in the face of exhaustive brute force attacks. To do so, we introduce target-distribution semantic-security and target-distribution non-malleability security notions and proofs that a slight variant of the JR HE construction can meet them. The proofs require new balls-and-bins type analyses significantly different from those used in prior work. Finally, we provide a formal proof of the folklore result that an unbounded adversary which obtains a limited number of encryptions of known plaintexts can always succeed at message recovery.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Contact author(s)
qtang84 @ gmail com
2016-02-23: last of 3 revisions
2016-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joseph Jaeger and Thomas Ristenpart and Qiang Tang},
      title = {Honey Encryption Beyond Message Recovery Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/174},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.