XOCB: Beyond-Birthday-Bound Secure Authenticated Encryption Mode with Rate-One Computation | SpringerLink
Skip to main content
Springer Nature Link
Log in

XOCB: Beyond-Birthday-Bound Secure Authenticated Encryption Mode with Rate-One Computation

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2023 (EUROCRYPT 2023)

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

  • 1209 Accesses

Abstract

We present a new block cipher mode of operation for authenticated encryption (AE), dubbed \(\textsf{XOCB}\), that has the following features: (1) beyond-birthday-bound (BBB) security based on the standard pseudorandom assumption of the internal block cipher if the maximum block length is sufficiently smaller than the birthday bound, (2) rate-1 computation, and (3) supporting any block cipher with any key length. Namely, \(\textsf{XOCB}\) has effectively the same efficiency as the seminal \(\textsf{OCB}\) while having stronger quantitative security without any change in the security model or the required primitive in \(\textsf{OCB}\). Although numerous studies have been conducted in the past, our \(\textsf{XOCB}\) is the first mode of operation to achieve these multiple goals simultaneously.

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We use the term AE to mean nonce-based AEAD [36] throughout the paper, unless otherwise stated.

  2. 2.

    By convention, we ignore the constant number of block cipher calls per message.

  3. 3.

    https://competitions.cr.yp.to/caesar.html.

  4. 4.

    We may simply write \(\textsf{OCB}\) to mean \(\textsf{OCB3}\).

  5. 5.

    The second version \(\textsf {OCB2}\) is flawed and allows devastating attacks, though a simple fix is possible [20].

  6. 6.

    https://csrc.nist.gov/News/2022/proposal-to-revise-sp-800-38a.

  7. 7.

    In concurrent to our work, Bhattacharjee, Bhaumik, and Nandi [8] presented an AE scheme combining SPRP and PRF that has some structural similarity to \(\textsf{XOCB}\).

  8. 8.

    More precisely, the block length of an encryption (resp. decryption) query is defined as \(|A|_n+|M|_n\) (resp. \(|A|_n+|C|_n\)), while the length of the “empty” query is 1.

  9. 9.

    A trail is a walk in which all edges are distinct.

  10. 10.

    The source codes can be found via https://www.dropbox.com/sh/k0y8h1boah072mn/AAAYPUr0j4MU9F3-w1k7U52Ha?dl=0.

References

  1. Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800–38D (2007), National Institute of Standards and Technology

    Google Scholar 

  2. Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Mouha, N., Yasuda, K.: How to securely release unverified plaintext in authenticated encryption. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part I. LNCS, vol. 8873, pp. 105–125. Springer, Heidelberg (Dec 2014). https://doi.org/10.1007/978-3-662-45611-8_6

  3. Banik, S., Bogdanov, A., Isobe, T., Shibutani, K., Hiwatari, H., Akishita, T., Regazzoni, F.: Midori: A block cipher for low energy. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part II. LNCS, vol. 9453, pp. 411–436. Springer, Heidelberg (Nov / Dec 2015). https://doi.org/10.1007/978-3-662-48800-3_17

  4. Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: GIFT: A small present - towards reaching the limit of lightweight encryption. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 321–345. Springer, Heidelberg (Sep 2017). https://doi.org/10.1007/978-3-319-66787-4_16

  5. Beierle, C., Biryukov, A., dos Santos, L.C., Großschädl, J., Perrin, L., Udovenko, A., Velichkov, V., Wang, Q.: Alzette: A 64-bit ARX-box - (feat. CRAX and TRAX). In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part III. LNCS, vol. 12172, pp. 419–448. Springer, Heidelberg (Aug 2020). https://doi.org/10.1007/978-3-030-56877-1_15

  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 (Dec 2000). https://doi.org/10.1007/3-540-44448-3_41

  7. Bhargavan, K., Leurent, G.: On the practical (in-)security of 64-bit block ciphers: Collision attacks on HTTP over TLS and OpenVPN. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016. pp. 456–467. ACM Press (Oct 2016). https://doi.org/10.1145/2976749.2978423

  8. Bhattacharjee, A., Bhaumik, R., Nandi, M.: Offset-based bbb-secure tweakable block-ciphers with updatable caches. In: INDOCRYPT. Lecture Notes in Computer Science, vol. 13774, pp. 171–194. Springer (2022)

    Google Scholar 

  9. Bhaumik, R., Nandi, M.: Improved security for OCB3. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 638–666. Springer, Heidelberg (Dec 2017). https://doi.org/10.1007/978-3-319-70697-9_22

  10. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (Sep 2007). https://doi.org/10.1007/978-3-540-74735-2_31

  11. Borghoff, J., Canteaut, A., Güneysu, T., Kavun, E.B., Knežević, M., Knudsen, L.R., Leander, G., Nikov, V., Paar, C., Rechberger, C., Rombouts, P., Thomsen, S.S., Yalçin, T.: PRINCE - A low-latency block cipher for pervasive computing applications - extended abstract. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 208–225. Springer, Heidelberg (Dec 2012). https://doi.org/10.1007/978-3-642-34961-4_14

  12. Choi, W., Lee, B., Lee, Y., Lee, J.: Improved Security Analysis for Nonce-Based Enhanced Hash-then-Mask MACs. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 697–723. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_23

    Chapter  Google Scholar 

  13. Cogliati, B., Dutta, A., Nandi, M., Patarin, J., Saha, A.: Proof of Mirror Theory for any xi_max. Cryptology ePrint Archive, Paper 2022/686 (2022), https://eprint.iacr.org/2022/686, https://eprint.iacr.org/2022/686

  14. Cogliati, B., Patarin, J.: Mirror theory: A simple proof of the pi+pj theorem with xi_max=2. Cryptology ePrint Archive, Paper 2020/734 (2020), https://eprint.iacr.org/2020/734, https://eprint.iacr.org/2020/734

  15. Datta, N., Dutta, A., Nandi, M., Paul, G.: Double-block hash-then-sum: A paradigm for constructing BBB secure PRF. IACR Trans. Symm. Cryptol. 2018(3), 36–92 (2018). 10.13154/tosc.v2018.i3.36-92

    Google Scholar 

  16. Datta, N., Dutta, A., Nandi, M., Yasuda, K.: Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology - CRYPTO 2018 (Proceedings, Part I). LNCS, vol. 10991, pp. 631–661. Springer (2018). https://doi.org/10.1007/978-3-319-96884-1_21

  17. Dutta, A., Nandi, M., Saha, A.: Proof of mirror theory for xi_max=2. IEEE Transactions on Information Theory 68(9), 6218–6232 (2022). https://doi.org/10.1109/TIT.2022.3171178

    Article  MathSciNet  MATH  Google Scholar 

  18. Dutta, A., Nandi, M., Talnikar, S.: Beyond Birthday Bound Secure MAC in Faulty Nonce Model. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2019 (Proceedings, Part I). LNCS, vol. 11476, pp. 437–466. Springer (2019). https://doi.org/10.1007/978-3-030-17653-2_15

  19. Hoang, V.T., Tessaro, S.: Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology - CRYPTO 2016 (Proceedings, Part I). LNCS, vol. 9814, pp. 3–32. Springer (2016). https://doi.org/10.1007/978-3-662-53018-4_1

  20. Inoue, A., Iwata, T., Minematsu, K., Poettering, B.: Cryptanalysis of OCB2: Attacks on authenticity and confidentiality. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 3–31. Springer, Heidelberg (Aug 2019). https://doi.org/10.1007/978-3-030-26948-7_1

  21. Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (Mar 2006). https://doi.org/10.1007/11799313_20

  22. Iwata, T.: Authenticated Encryption Mode for Beyond the Birthday Bound Security. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 125–142. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_9

    Chapter  Google Scholar 

  23. Iwata, T., Ohashi, K., Minematsu, K.: Breaking and repairing GCM security proofs. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 31–49. Springer, Heidelberg (Aug 2012). https://doi.org/10.1007/978-3-642-32009-5_3

  24. Jha, A., List, E., Minematsu, K., Mishra, S., Nandi, M.: XHX - A framework for optimally secure tweakable block ciphers from classical block ciphers and universal hashing. In: Lange, T., Dunkelman, O. (eds.) LATINCRYPT 2017. LNCS, vol. 11368, pp. 207–227. Springer, Heidelberg (Sep 2017). https://doi.org/10.1007/978-3-030-25283-0_12

  25. Katz, J., Yung, M.: Unforgeable encryption and chosen ciphertext secure modes of operation. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 284–299. Springer, Heidelberg (Apr 2001). https://doi.org/10.1007/3-540-44706-7_20

  26. Kim, S., Lee, B., Lee, J.: Tight security bounds for double-block hash-then-sum MACs. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. LNCS, vol. 12105, pp. 435–465. Springer, Heidelberg (May 2020). https://doi.org/10.1007/978-3-030-45721-1_16

  27. Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (Feb 2011). https://doi.org/10.1007/978-3-642-21702-9_18

  28. Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. Journal of Cryptology 24(3), 588–613 (2011). https://doi.org/10.1007/s00145-010-9073-y

    Article  MathSciNet  MATH  Google Scholar 

  29. Mennink, B.: Optimally secure tweakable blockciphers. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 428–448. Springer, Heidelberg (Mar 2015). https://doi.org/10.1007/978-3-662-48116-5_21

  30. Mennink, B.: Insuperability of the standard versus ideal model gap for tweakable blockcipher security. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 708–732. Springer, Heidelberg (Aug 2017). https://doi.org/10.1007/978-3-319-63715-0_24

  31. Naito, Y.: Improved XKX-based AEAD scheme: Removing the birthday terms. In: Lange, T., Dunkelman, O. (eds.) LATINCRYPT 2017. LNCS, vol. 11368, pp. 228–246. Springer, Heidelberg (Sep 2017). https://doi.org/10.1007/978-3-030-25283-0_13

  32. Naito, Y.: Tweakable blockciphers for efficient authenticated encryptions with beyond the birthday-bound security. IACR Trans. Symm. Cryptol. 2017(2), 1–26 (2017). 10.13154/tosc.v2017.i2.1-26

    Google Scholar 

  33. Niwa, Y., Ohashi, K., Minematsu, K., Iwata, T.: GCM security bounds reconsidered. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 385–407. Springer, Heidelberg (Mar 2015). https://doi.org/10.1007/978-3-662-48116-5_19

  34. Patarin, J.: Introduction to Mirror Theory: Analysis of Systems of Linear Equalities and Linear Non Equalities for Cryptography. IACR Cryptology ePrint Archive, Report 2010/287 (2010), available at https://eprint.iacr.org/2010/287

  35. Patarin, J.: Mirror Theory and Cryptography. IACR Cryptology ePrint Archive, Report 2016/702 (2016), available at https://eprint.iacr.org/2016/702

  36. Rogaway, P.: Authenticated-encryption with associated-data. In: Atluri, V. (ed.) ACM CCS 2002. pp. 98–107. ACM Press (Nov 2002). https://doi.org/10.1145/586110.586125

  37. Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (Dec 2004). https://doi.org/10.1007/978-3-540-30539-2_2

  38. 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 (Nov 2001). https://doi.org/10.1145/501983.502011

  39. 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 (May / Jun 2006). https://doi.org/10.1007/11761679_23

  40. Sovyn, Y., Khoma, V., Podpora, M.: Comparison of Three CPU-Core Families for IoT Applications in Terms of Security and Performance of AES-GCM. IEEE Internet of Things Journal 7(1), 339–348 (2020). https://doi.org/10.1109/JIOT.2019.2953230

    Article  Google Scholar 

Download references

Acknowledgement

We thank the anonymous reviewers for their insightful comments that improved the presentation of our paper. Jooyoung Lee was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No.2021R1F1A1047146). Zhenzhen Bao was supported by the National Key R &D Program of China (Grant No. 2018YFA0704701), the Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008), and the Shandong Province Key R &D Project (Nos. 2020ZLYS09 and 2019JZZY010133).

Author information

Authors and Affiliations

  1. Institute for Network Sciences and Cyberspace, BNRist, Tsinghua University, Beijing, China

    Zhenzhen Bao

  2. KAIST, Daejeon, Korea

    Seongha Hwang, Byeonghak Lee & Jooyoung Lee

  3. NEC, Kawasaki, Japan

    Akiko Inoue & Kazuhiko Minematsu

  4. Zhongguancun Laboratory, Beijing, China

    Zhenzhen Bao

Authors
  1. Zhenzhen Bao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Seongha Hwang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Akiko Inoue
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Byeonghak Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jooyoung Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Kazuhiko Minematsu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhenzhen Bao .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bao, Z., Hwang, S., Inoue, A., Lee, B., Lee, J., Minematsu, K. (2023). XOCB: Beyond-Birthday-Bound Secure Authenticated Encryption Mode with Rate-One Computation. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30634-1_18

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30633-4

  • Online ISBN: 978-3-031-30634-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation