POEx: a beyond-birthday-bound-secure on-line cipher. (English) Zbl 1379.94037

Summary: On-line ciphers are convenient building blocks for realizing efficient single- pass encryption. In particular, the trend to limit the consequences of nonce reuses rendered them popular in recent authenticated encryption schemes. While encryption schemes, such as POE, COPE, or the ciphers within ElmE/ElmD concentrated on efficiency, their security guarantees and that of all earlier on-line ciphers is limited by the birthday bound, and so are those of the AE schemes built upon them. This work proposes POEx, a beyond-birthday-bound-secure on-line cipher which employs one call to a tweakable block cipher and one call to a 2\(n\)-bit universal hash function per message block. POEx builds upon the recently proposed XTX tweak extender by K. Minematsu and T. Iwata [IMACC 2015, Lect. Notes Comput. Sci. 9496, 77–93 (2015; Zbl 1376.94040)]. We prove the security of our construction and discuss possible instantiations.


94A60 Cryptography

Biographic References:

Verdegay, José Luis


Zbl 1376.94040
Full Text: DOI


[1] Abed, F., Forler, C., McGrew, D., List, E., Fluhrer, S., Lucks, S., Wenzel, J.: Pipelineable on-line encryption. In: Cid, C., Rechberger, C. (eds.) FSE, volume 8540 of Lecture Notes in Computer Science, pp. 205-223. Springer (2014) · Zbl 1382.94036
[2] Andreeva, E., Bogdanov, A., Datta, N., Luykx, A, Mennink, B., Nandi, M., Tischhauser, E., Yasuda, K.: COLM v1. http://competitions.cr.yp.to/caesar-submissions.html (2016)
[3] 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 (1), volume 8873 of LNCS, pp. 105-125. Springer (2014) · Zbl 1306.94021
[4] Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K., Sarkar, P.: Parallelizable and authenticated online ciphers. In: Sako, K. (ed.) ASIACRYPT (1), vol. 8269, pp. 424-443. Springer (2013) · Zbl 1327.94026
[5] Andreeva, E., Luykx, A., Mennink, B., Yasuda, K.: COBRA: A parallelizable authenticated online cipher without block cipher inverse. In: Cid, C., Rechberger, C. (eds.) FSE, volume 8540 of LNCS, pp. 187-204. Springer (2014) · Zbl 1382.94046
[6] Beierle, C., Jean, J., Kölbl, S., Leander, G., Moradi, A., Peyrin, T., Sasaki, Y., Sasdrich, P., Sim, S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO II, volume 9815 of LNCS, pp. 123-153. Springer (2016) · Zbl 1372.94412
[7] Bellare, M., Boldyreva, A., Knudsen, L.R., Namprempre, C.: Online ciphers and the Hash-CBC construction. In: Kilian, J. (ed.) CRYPTO, volume 2139 of Lecture Notes in Computer Science, pp. 292-309. Springer (2001) · Zbl 1002.94520
[8] Bellare, M; Rogaway, P, Code-based game-playing proofs and the security of triple encryption, IACR Cryptol ePrint Archive, 2004, 331, (2004) · Zbl 1140.94321
[9] Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT, volume 4004 of LNCS, pp. 409-426. Springer (2006) · Zbl 1140.94321
[10] Bernstein, D.: Caesar: Competition for authenticated encryption: Security, applicability, and robustness. https://competitions.cr.yp.to/caesar.html,Version2016.08.15
[11] Bhaumik, R; Mridul, N, Olef: an inverse-free online cipher, Trans Symmetric Cryptol Issue, 2016, 30-51, (2016)
[12] Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Yannick, Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES, volume 4727 of LNCS, pp. 450-466. Springer (2007) · Zbl 1142.94334
[13] Boldyreva, A., Taesombut, N.: Online encryption schemes: New security notions and constructions. In: Okamoto, T. (ed.) CT-RSA, volume 2964 of Lecture Notes in Computer Science, pp. 1-14. Springer (2004) · Zbl 1196.94044
[14] Datta, N., Nandi, M.: ELmD. http://competitions.cr.yp.to/caesar-submissions.html (2014)
[15] Datta, N., Nandi, M., Susilo, W., Mu, Y.: ELmE: A misuse resistant parallel authenticated encryption. In: ACISP, volume 8544 of Lecture Notes in Computer Science, pp. 306-321. Springer (2014) · Zbl 1337.94094
[16] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The skein hash function family. Submission to NIST (Round 3) (2010)
[17] Fleischmann, E., Forler, C., Lucks, S.: McOE: A family of almost foolproof on-line authenticated encryption schemes. In: Canteaut, A. (ed.) FSE, volume 7549 of LNCS, pp. 196-215. Springer (2012) · Zbl 1312.94113
[18] Halevi, S., Rogaway, P.: A parallelizable enciphering mode. In: Okamoto, T. (ed.) , pp. 292-304. Springer (2004) · Zbl 1196.94055
[19] ISO/IEC. ISO/IEC 29192-2:2012, Information technology ? Security techniques ? Lightweight cryptography ? Part 2: Block ciphers, 2012 · Zbl 1140.94321
[20] Jean, J., Nikolic, I., Peyrin, T., Sarkar, P., Iwata, T.: Tweaks and keys for block ciphers: The TWEAKEY framework. In: ASIACRYPT (2), volume 8874 of Lecture Notes in Computer Science, pp. 274?-288 (2014) · Zbl 1317.94113
[21] Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE, volume 6733 of Lecture Notes in Computer Science, pp. 306-327. Springer (2011) · Zbl 1307.94119
[22] Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO, volume 2442 of Lecture Notes in Computer Science, pp. 31-46. Springer (2002) · Zbl 1026.94533
[23] List, E., Nandi, M.: Revisiting full-PRF-secure PMAC and using it for beyond-birthday authenticated encryption. In: Handschuh, H. (ed.) CT-RSA, volume 10159 of LNCS, pp. 258-274. Springer (2017) · Zbl 1383.94029
[24] Lu, J, On the security of the COPA and marble authenticated encryption algorithms against (almost) universal forgery attack, IACR Cryptology ePrint Archive, 2015, 79, (2015)
[25] McGrew, D., Viega, J.: The Galois/Counter Mode of Operation (GCM). Submission to NIST. http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/gcm/gcm-spec.pdf (2004) · Zbl 1113.94315
[26] Mennink, B: Optimally secure tweakable blockciphers. In: Leander, G. (ed.) FSE, volume 9054 of Lecture Notes in Computer Science, pp. 428-448. Springer (2015) · Zbl 1382.94141
[27] Minematsu, K.: Parallelizable rate-1 authenticated encryption from pseudorandom functions. In: Nguyen, P. Q., Oswald, E. (eds.) EUROCRYPT, volume 8441 of Lecture Notes in Computer Science, pp. 275-292. Springer (2014) · Zbl 1332.94091
[28] Minematsu, K., Iwata, T.: Tweak-length extension for tweakable blockciphers. In: Groth, J. (ed.) IMA International Conference, volume 9496 of Lecture Notes in Computer Science, pp. 77-93. Springer (2015) · Zbl 1376.94040
[29] Nandi, M.: A simple security analysis of hash-cbc and a new efficient one-key online cipher. Cryptology ePrint Archive, Report 2007/158 (2007)
[30] Nandi, M.: Two new efficient CCA-secure online ciphers: MHCBC and MCBC. In: Chowdhury, D. R., Rijmen, V., Das, A. (eds.) INDOCRYPT, volume 5365 of LNCS, pp. 350-362. Springer (2008) · Zbl 1203.94117
[31] Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: ASIACRYPT, volume 3329 of Lecture Notes in Computer Science, pp. 16-31. Springer (2004) · Zbl 1094.94035
[32] Rogaway, P., Zhang, H.: Online ciphers from tweakable blockciphers. In: CT-RSA, volume 6558 of Lecture Notes in Computer Science, pp. 237-249. Springer (2011) · Zbl 1284.94106
[33] Wang, L., Guo, J., Zhang, G., Zhao, J., Gu, D.: How to build fully secure tweakable blockciphers from classical blockciphers. In: Cheon, J. H., Takagi, T. (eds.) ASIACRYPT (1), volume 10031 of LNCS, pp. 455?-483 (2016) · Zbl 1404.94118
[34] Young, E.A., Hudson, T.J.: OpenSSL: The Open Source toolkit for SSL/TLS. http://www.openssl.org/ (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.