Skip to main content
Springer Nature Link
Log in

Succinctly-Committing Authenticated Encryption

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2024 (CRYPTO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14923))

Included in the following conference series:

  • 509 Accesses

Abstract

Recent attacks and applications have led to the need for symmetric encryption schemes that, in addition to providing the usual authenticity and privacy, are also committing. In response, many committing authenticated encryption schemes have been proposed. However, all known schemes, in order to provide s bits of committing security, suffer an expansion—this is the length of the ciphertext minus the length of the plaintext—of 2s bits. This incurs a cost in bandwidth or storage. (We typically want \(s=128\), leading to 256-bit expansion.) However, it has been considered unavoidable due to birthday attacks. We show how to bypass this limitation. We give authenticated encryption (AE) schemes that provide s bits of committing security, yet suffer expansion only around s as long as messages are long enough, namely more than s bits. We call such schemes succinct. We do this via a generic, ciphertext-shortening transform called \(\textsf{SC}\): given an AE scheme with 2s-bit expansion, \(\textsf{SC}\) returns an AE scheme with s-bit expansion while preserving committing security. \(\textsf{SC}\) is very efficient; an AES-based instantiation has overhead just two AES calls. As a tool, \(\textsf{SC}\) uses a collision-resistant invertible PRF called \(\textsf{HtM}\), that we design, and whose analysis is technically difficult. To add the committing security that \(\textsf{SC}\) assumes to a base scheme, we also give a transform \(\textsf{CTY}\) that improves Chan and Rogaway’s \(\textsf{CTX}\). Our results hold in a general framework for authenticated encryption that includes both classical AEAD and AE2 (also called nonce-hiding AE) as special cases, so that we in particular obtain succinctly-committing AE schemes for both these settings.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 109.00
Price excludes VAT (USA)
Softcover Book
USD 79.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    For example, we can let \(\textsf{pad}(M, 0) = M \Vert 1 0^{n - |M| - 1}\). For \(\textsf{unpad}(Y)\), we first obtain a string X by removing the trailing 0’s and the last 1 of Y. If \(Y \ne 0^n\) and \(|X| \le n - d\) then we return X; otherwise we return \(\bot \). Later we will give a more efficient instantiation of \(\textsf{pad}\) and \(\textsf{unpad}\) where \(n = 128\) and \(d= 8\).

  2. 2.

    For example, we can let \(\textsf{pad}(M) = M \Vert 1 0^{n - 1 - |M|}\). Conversely, \(\textsf{unpad}(Y)\) returns \(\bot \) if \(Y = 0^n\) or if Y doesn’t end with \(0^{s - 1}\). Otherwise, return the string X obtained by removing the trailing 0’s and the last bit 1 of Y.

  3. 3.

    There is also an AES key-setup cost since we have to rekey \(\textsf{HtM}\) for every encryption, but a good implementation can hide this latency. For example, AES-GCM-SIV [27] also derives new subkeys for every encryption, but manages to hide the key-setup cost of AES.

References

  1. Abdalla, M., Bellare, M., Neven, G.: Robust encryption. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 480–497. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_28

    Chapter  Google Scholar 

  2. Albertini, A., Duong, T., Gueron, S., Kölbl, S., Luykx, A., Schmieg, S.: How to abuse and fix authenticated encryption without key commitment. In: Butler, K.R.B., Thomas, K. (eds.) USENIX Security 2022, pp. 3291–3308. USENIX Association (2022)

    Google Scholar 

  3. Barbosa, M., Farshim, P.: Indifferentiable authenticated encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 187–220. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_7

    Chapter  Google Scholar 

  4. Bellare, M., Hoang, V.T.: Efficient schemes for committing authenticated encryption. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 845–875. Springer, Heidelberg, May / June (2022). https://doi.org/10.1007/978-3-031-07085-3_29

    Chapter  Google Scholar 

  5. Bellare, M., Hoang, V.T.: Succinctly-committing Authenticated Encryption. Cryptology ePrint Archive (2024)

    Google Scholar 

  6. Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 531–545. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_41

    Chapter  Google Scholar 

  7. Bellare, M., Ng, R., Tackmann, B.: Nonces are noticed: AEAD revisited. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 235–265. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_9

    Chapter  Google Scholar 

  8. Bellare, M., Rogaway, P.: Encode-then-encipher encryption: how to exploit nonces or redundancy in plaintexts for efficient cryptography. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 317–330. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_24

    Chapter  Google Scholar 

  9. Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_25

    Chapter  Google Scholar 

  10. Bellare, M., Rogaway, P., Wagner, D.: The EAX mode of operation. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 389–407. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-25937-4_25

    Chapter  Google Scholar 

  11. Bellare, M., Shea, L.: Flexible password-based encryption: securing cloud storage and provably resisting partitioning-oracle attacks. In: Rosulek, M. (ed.) CT-RSA 2023. LNCS, vol. 13871, pp. 594–621. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30872-7_23

    Chapter  Google Scholar 

  12. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 320–337. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_19

    Chapter  Google Scholar 

  13. Bose, P., Hoang, V.T., Tessaro, S.: Revisiting AES-GCM-SIV: multi-user security, faster key derivation, and better bounds. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_18

    Chapter  Google Scholar 

  14. Chan, J., Rogaway, P.: Anonymous AE. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part II. LNCS, vol. 11922, pp. 183–208. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_7

    Chapter  Google Scholar 

  15. Chan, J., Rogaway, P.: On committing authenticated-encryption. In: Atluri, V., Di Pietro, R., Jensen, C.D., Meng, W. (eds.) ESORICS 2022, Part II. LNCS, vol. 13555, pp. 275–294. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-17146-8_14

    Chapter  Google Scholar 

  16. Chen, Y.L., et al.: Key committing security of AEZ and more. IACR Trans. Symm. Cryptol. 2023(4), 452–488 (2023)

    Article  Google Scholar 

  17. Crowley, P., Biggers, E.: Adiantum: length-preserving encryption for entry-level processors. IACR Trans. Symm. Cryptol. 2018(4), 39–61 (2018)

    Article  Google Scholar 

  18. Crowley, P., Huckleberry, N., Biggers, E.: Length-preserving encryption with HCTR2. Technical report, Cryptology ePrint Archive, Report 2021/11441 (2021). http://eprintiacr.org

  19. Daemen, J., Rijmen, V.: AES proposal: Rijndael. NIST AES proposal (1998)

    Google Scholar 

  20. Dai, Y., Steinberger, J.: Indifferentiability of 8-round feistel networks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 95–120. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_4

    Chapter  Google Scholar 

  21. Degabriele, J.P., Fischlin, M., Govinden, J.: The indifferentiability of the duplex and its practical applications. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part VIII. LNCS, vol. 14445, pp. 237–269. Springer, Cham (2023). https://doi.org/10.1007/978-981-99-8742-9_8

    Chapter  Google Scholar 

  22. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: lightweight authenticated encryption and hashing. J. Cryptol. 34(3), 33 (2021)

    Article  MathSciNet  Google Scholar 

  23. Dworkin, M.: Recommendation for block cipher modes of operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D (2007)

    Google Scholar 

  24. Farshim, P., Orlandi, C., Roşie, R.: Security of symmetric primitives under incorrect usage of keys. IACR Trans. Symm. Cryptol. 2017(1), 449–473 (2017)

    Article  Google Scholar 

  25. Gertner, Y., Herzberg, A.: Committing encryption and publicly-verifiable signcryption. Cryptology ePrint Archive, Report 2003/254 (2003). https://eprint.iacr.org/2003/254

  26. Grubbs, P., Lu, J., Ristenpart, T.: Message franking via committing authenticated encryption. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 66–97. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_3

    Chapter  Google Scholar 

  27. Gueron, S.: AES-GCM-SIV (2018). https://github.com/Shay-Gueron/AES-GCM-SIV

  28. Gueron, S., Mouha, N.: Simpira v2: a family of efficient permutations using the AES round function. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 95–125. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_4

    Chapter  Google Scholar 

  29. Hoang, V.T., Krovetz, T., Rogaway, P.: Robust authenticated-encryption AEZ and the problem that it solves. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 15–44. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_2

    Chapter  Google Scholar 

  30. Hoang, V.T., Shen, Y.: Security of streaming encryption in google’s tink library. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, pp. 243–262. ACM Press (2020)

    Google Scholar 

  31. Lambæk, M.: Breaking and fixing private set intersection protocols. Cryptology ePrint Archive, Report 2016/665 (2016). https://eprint.iacr.org/2016/665

  32. Len, J., Grubbs, P., Ristenpart, T.: Partitioning oracle attacks. In: Bailey, M., Greenstadt, R. (eds.) USENIX Security 2021, pp. 195–212. USENIX Association (2021)

    Google Scholar 

  33. Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_2

    Chapter  Google Scholar 

  34. McGrew, D.A., Viega, J.: The security and performance of the galois/counter mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30556-9_27

    Chapter  Google Scholar 

  35. Menda, S., Len, J., Grubbs, P., Ristenpart, T.: Context discovery and commitment attacks - how to break CCM, EAX, SIV, and more. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part IV. LNCS, vol. 14007, pp. 379–407. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30634-1_13

    Chapter  Google Scholar 

  36. Naito, Y., Sasaki, Y., Sugawara, T.: KIVR: committing authenticated encryption using redundancy and application to GCM, CCM, and more. In: Pöpper, C., Batina, L. (eds.) ACNS 2024. LNCS, vol. 14583, pp. 318–347. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-54770-6_13

    Chapter  Google Scholar 

  37. Namprempre, C., Rogaway, P., Shrimpton, T.: Reconsidering generic composition. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 257–274. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_15

    Chapter  Google Scholar 

  38. Rogaway, P.: Authenticated-encryption with associated-data. In: Atluri, V. (ed.) ACM CCS 2002, pp. 98–107. ACM Press (2002)

    Google Scholar 

  39. Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Reiter, M.K., Samarati, P. (eds.) ACM CCS 2001, pp. 196–205. ACM Press (2001)

    Google Scholar 

  40. Rogaway, P., Shrimpton, T.: A provable-security treatment of the key-wrap problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 373–390. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_23

    Chapter  Google Scholar 

  41. Salowey, J., Choudhury, A., McGrew, D.: AES Galois Counter Mode (GCM) Cipher Suites for TLS. RFC 5288 (2008). https://datatracker.ietf.org/doc/html/rfc5288

  42. Whiting, D., Housely, R., Ferguson, N.: Counter with CBC-MAC (CCM). IETF Network Working Group, RFC 3610 (2003)

    Google Scholar 

Download references

Acknowledgments

Many thanks to Cong Wu who implemented our transforms and provided extensive benchmarks. We thank the CRYPTO 2024 reviewers for their careful reading and valuable comments. Mihir Bellare was supported in part by NSF grant CNS-2154272 and KACST. Viet Tung Hoang was supported in part by NSF grant CNS-2046540 (CAREER).

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of California San Diego, La Jolla, USA

    Mihir Bellare

  2. Department of Computer Science, Florida State University, Tallahassee, USA

    Viet Tung Hoang

Authors
  1. Mihir Bellare
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Viet Tung Hoang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mihir Bellare .

Editor information

Editors and Affiliations

  1. Boston University, Boston, MA, USA

    Leonid Reyzin

  2. University of Waterloo, Waterloo, ON, Canada

    Douglas Stebila

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bellare, M., Hoang, V.T. (2024). Succinctly-Committing Authenticated Encryption. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14923. Springer, Cham. https://doi.org/10.1007/978-3-031-68385-5_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-68385-5_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-68384-8

  • Online ISBN: 978-3-031-68385-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation