Document Open Access Logo

Fooling an Unbounded Adversary with a Short Key, Repeatedly: The Honey Encryption Perspective

Authors Xinze Li, Qiang Tang, Zhenfeng Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.23.pdf
  • Filesize: 0.73 MB
  • 21 pages

Document Identifiers

Author Details

Xinze Li
  • Tsinghua University, Beijing, China
Qiang Tang
  • The University of Sydney, Australia
Zhenfeng Zhang
  • Institute of Software, Chinese Academy of Sciences, Beijing, China

Funding

  • Tang, Qiang: Supported by a Google Faculty Award, and a gift from Filecoin.
  • Zhang, Zhenfeng: Supported by National Key R&D Program of China (2017YFB0802000)

Acknowledgements

We thank anonymous reviewers for valuable comments, specifically the simplification of the key re-use analysis.

Cite AsGet BibTex

Xinze Li, Qiang Tang, and Zhenfeng Zhang. Fooling an Unbounded Adversary with a Short Key, Repeatedly: The Honey Encryption Perspective. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.23

Abstract

This article is motivated by the classical results from Shannon that put the simple and elegant one-time pad away from practice: key length has to be as large as message length and the same key could not be used more than once. In particular, we consider encryption algorithm to be defined relative to specific message distributions in order to trade for unconditional security. Such a notion named honey encryption (HE) was originally proposed for achieving best possible security for password based encryption where secrete key may have very small amount of entropy. Exploring message distributions as in HE indeed helps circumvent the classical restrictions on secret keys.We give a new and very simple honey encryption scheme satisfying the unconditional semantic security (for the targeted message distribution) in the standard model (all previous constructions are in the random oracle model, even for message recovery security only). Our new construction can be paired with an extremely simple yet "tighter" analysis, while all previous analyses (even for message recovery security only) were fairly complicated and require stronger assumptions. We also show a concrete instantiation further enables the secret key to be used for encrypting multiple messages.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
  • Theory of computation → Cryptographic primitives
Keywords
  • unconditional security
  • information theoretic encryption
  • honey encryption

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Esther Omolara Abiodun and Aman Jantan. Modified honey encryption scheme for encoding natural language message. Int. J. Electr. Comput. Eng., 9(3):1871, 2019. Google Scholar
  2. Thomas Agrikola, Geoffroy Couteau, Yuval Ishai, Stanislaw Jarecki, and Amit Sahai. On pseudorandom encodings. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 639-669. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64381-2_23.
  3. Yonatan Aumann, Yan Zong Ding, and Michael O. Rabin. Everlasting security in the bounded storage model. IEEE Trans. Inf. Theory, 48(6):1668-1680, 2002. URL: https://doi.org/10.1109/TIT.2002.1003845.
  4. Petra Berenbrink, Tom Friedetzky, Zengjian Hu, and Russell A. Martin. On weighted balls-into-bins games. Theor. Comput. Sci., 409(3):511-520, 2008. URL: https://doi.org/10.1016/j.tcs.2008.09.023.
  5. Nikita Borisov, Ian Goldberg, and David A. Wagner. Intercepting mobile communications: the insecurity of 802.11. In Christopher Rose, editor, MOBICOM 2001, Proceedings of the seventh annual international conference on Mobile computing and networking, Rome, Italy, July 16-21, 2001, pages 180-189. ACM, 2001. URL: https://doi.org/10.1145/381677.381695.
  6. Christian Cachin and Ueli M. Maurer. Unconditional security against memory-bounded adversaries. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, volume 1294 of Lecture Notes in Computer Science, pages 292-306. Springer, 1997. URL: https://doi.org/10.1007/BFb0052243.
  7. Rahul Chatterjee, Joseph Bonneau, Ari Juels, and Thomas Ristenpart. Cracking-resistant password vaults using natural language encoders. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 481-498. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/SP.2015.36.
  8. Yan Zong Ding and Michael O. Rabin. Hyper-encryption and everlasting security. In Helmut Alt and Afonso Ferreira, editors, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science, pages 1-26. Springer, 2002. URL: https://doi.org/10.1007/3-540-45841-7_1.
  9. Yevgeniy Dodis and Adam D. Smith. Entropic security and the encryption of high entropy messages. In Joe Kilian, editor, Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science, pages 556-577. Springer, 2005. URL: https://doi.org/10.1007/978-3-540-30576-7_30.
  10. Flávio du Pin Calmon, Muriel Médard, Linda M. Zeger, João Barros, Mark M. Christiansen, and Ken R. Duffy. Lists that are smaller than their parts: A coding approach to tunable secrecy. In 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012, Allerton Park & Retreat Center, Monticello, IL, USA, October 1-5, 2012, pages 1387-1394. IEEE, 2012. URL: https://doi.org/10.1109/Allerton.2012.6483380.
  11. Stefan Dziembowski and Ueli M. Maurer. Optimal randomizer efficiency in the bounded-storage model. J. Cryptol., 17(1):5-26, 2004. URL: https://doi.org/10.1007/s00145-003-0309-y.
  12. Maximilian Golla, Benedict Beuscher, and Markus Dürmuth. On the security of cracking-resistant password vaults. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 1230-1241. ACM, 2016. URL: https://doi.org/10.1145/2976749.2978416.
  13. Zhicong Huang, Erman Ayday, Jacques Fellay, Jean-Pierre Hubaux, and Ari Juels. Genoguard: Protecting genomic data against brute-force attacks. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 447-462. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/SP.2015.34.
  14. Joseph Jaeger, Thomas Ristenpart, and Qiang Tang. Honey encryption beyond message recovery security. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 758-788. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-49890-3_29.
  15. Ari Juels and Thomas Ristenpart. Honey encryption: Security beyond the brute-force bound. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 293-310. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_17.
  16. Burt Kaliski. PKCS #5: Password-based cryptography specification version 2.0. RFC, 2898:1-34, 2000. URL: https://doi.org/10.17487/RFC2898.
  17. Cheuk Ting Li and Abbas El Gamal. Maximal correlation secrecy. IEEE Trans. Inf. Theory, 64(5):3916-3926, 2018. URL: https://doi.org/10.1109/TIT.2018.2816066.
  18. Ueli M. Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher. J. Cryptol., 5(1):53-66, 1992. URL: https://doi.org/10.1007/BF00191321.
  19. Ueli M. Maurer and James L. Massey. Local randomness in pseudorandom sequences. J. Cryptol., 4(2):135-149, 1991. URL: https://doi.org/10.1007/BF00196773.
  20. Abiodun Esther Omolara, Aman Jantan, Oludare Isaac Abiodun, and Howard Eldon Poston. A novel approach for the adaptation of honey encryption to support natural language message. In Proceedings of the International MultiConference of Engineers and Computer Scientists, volume 1, 2018. Google Scholar
  21. Alexander Russell and Hong Wang. How to fool an unbounded adversary with a short key. In Lars R. Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings, volume 2332 of Lecture Notes in Computer Science, pages 133-148. Springer, 2002. URL: https://doi.org/10.1007/3-540-46035-7_9.
  22. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discret. Math., 8(2):223-250, 1995. URL: https://doi.org/10.1137/S089548019223872X.
  23. Claude E. Shannon. Communication theory of secrecy systems. Bell Syst. Tech. J., 28(4):656-715, 1949. URL: https://doi.org/10.1002/j.1538-7305.1949.tb00928.x.
  24. Junji Shikata. Formalization of information-theoretic security for key agreement, revisited. In Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, July 7-12, 2013, pages 2720-2724. IEEE, 2013. URL: https://doi.org/10.1109/ISIT.2013.6620721.
  25. Mathy Vanhoef and Frank Piessens. Key reinstallation attacks: Forcing nonce reuse in WPA2. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, pages 1313-1328. ACM, 2017. URL: https://doi.org/10.1145/3133956.3134027.
  26. Mark N. Wegman and Larry Carter. New classes and applications of hash functions. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 175-182. IEEE Computer Society, 1979. URL: https://doi.org/10.1109/SFCS.1979.26.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact