TY - GEN
T1 - Honey encryption beyond message recovery security
AU - Jaeger, Joseph
AU - Ristenpart, Thomas
AU - Tang, Qiang
N1 - Funding Information:
We thank the anonymous reviewers for valuable comments. Joseph Jaeger was supported in part by NSF grants CNS-1526801 and CNS-1228890, ERC Project ERCC FP7/615074 and a gift from Microsoft. Thomas Ristenpart was supported by NSF grants CNS-1514163, CNS-1546033, CNS-1065134, CNS-1330308 and a gift from Microsoft. Qiang Tang was supported by NSF grants CNS-1518765 and CNS-1514261.
Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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. We prove 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.
AB - 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. We prove 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.
UR - http://www.scopus.com/inward/record.url?scp=84978997654&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978997654&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49890-3_29
DO - 10.1007/978-3-662-49890-3_29
M3 - Conference contribution
AN - SCOPUS:84978997654
SN - 9783662498897
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 758
EP - 788
BT - Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fischlin, Marc
A2 - Coron, Jean-Sebastien
PB - Springer Verlag
T2 - 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
Y2 - 8 May 2016 through 12 May 2016
ER -