XPX: generalized tweakable Even-Mansour with improved security guarantees. (English) Zbl 1351.94058

Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-53017-7/pbk; 978-3-662-53018-4/ebook). Lecture Notes in Computer Science 9814, 64-94 (2016).
Summary: We present \(\mathrm {XPX}\), a tweakable blockcipher based on a single permutation \(P\). On input of a tweak \((t_{11},t_{12},t_{21},t_{22})\in \mathcal {T}\) and a message \(m\), it outputs ciphertext \(c=P(m\oplus \varDelta_1)\oplus \varDelta_2\), where \(\varDelta_1=t_{11}k\oplus t_{12}P(k)\) and \(\varDelta_2=t_{21}k\oplus t_{22}P(k)\). Here, the tweak space \(\mathcal {T}\) is required to satisfy a certain set of trivial conditions (such as \((0,0,0,0)\not \in \mathcal {T}\)). We prove that \(\mathrm {XPX}\) with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of \(\mathrm {XPX}\) under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that \(\mathrm {XPX}\) achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of \(\mathcal {T}\). For instance, if \(t_{12}, t_{22}\neq 0\) and \((t_{21}, t_{22})\neq (0,1)\) for all tweaks, \(\mathrm {XPX}\) is XOR-related-key secure. \(\mathrm {XPX}\) generalizes Even-Mansour (\(\mathrm {EM}\)), but also Rogaway’s \(\mathrm {XEX}\) based on \(\mathrm {EM}\), and various other tweakable blockciphers. As such, \(\mathrm {XPX}\) finds a wide range of applications. We show how our results on \(\mathrm {XPX}\) directly imply related-key security of the authenticated encryption schemes Prøst-\(\mathrm {COPA}\) and \(\mathrm {Minalpher}\), and how a straightforward adjustment to the MAC function \(\mathrm {Chaskey}\) and to keyed Sponges makes them provably related-key secure.
For the entire collection see [Zbl 1344.94001].


94A60 Cryptography


ELmD; Minalpher
Full Text: DOI Link


[1] Albrecht, M.R., Farshim, P., Paterson, K.G., Watson, G.J.: On cipher-dependent related-key attacks in the ideal-cipher model. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 128–145. Springer, Heidelberg (2011) · Zbl 1282.94030
[2] Andreeva, E., Bogdanov, A., Dodis, Y., Mennink, B., Steinberger, J.P.: On the indifferentiability of key-alternating ciphers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013) · Zbl 1310.94124
[3] Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K.: Parallelizable and authenticated online ciphers. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 424–443. Springer, Heidelberg (2013) · Zbl 1327.94026
[4] Andreeva, E., Bogdanov, A., Mennink, B.: Towards understanding the known-key security of block ciphers. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 348–366. Springer, Heidelberg (2014) · Zbl 1321.94033
[5] Andreeva, E., Daemen, J., Mennink, B., Van Assche, G.: Security of keyed sponge constructions using a modular proof approach. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 364–384. Springer, Heidelberg (2015) · Zbl 1382.94045
[6] Bellare, M., Kohno, T.: A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 491–506. Springer, Heidelberg (2003) · Zbl 1038.94520
[7] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the security of the keyed sponge construction. In: Symmetric Key Encryption Workshop (SKEW 2011) (2011) · Zbl 1149.94304
[8] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Permutation-based encryption, authentication and authenticated encryption. In: Directions in Authenticated Ciphers (DIAC 2012) (2012) · Zbl 1292.94030
[9] Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-alternating ciphers in a provable setting: encryption using a small number of public permutations. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 45–62. Springer, Heidelberg (2012) · Zbl 1290.94044
[10] CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness, May 2015. http://competitions.cr.yp.to/caesar.html
[11] Chakraborty, D., Sarkar, P.: A general construction of tweakable block ciphers and different modes of operations. In: Lipmaa, H., Yung, M., Lin, D. (eds.) Inscrypt 2006. LNCS, vol. 4318, pp. 88–102. Springer, Heidelberg (2006) · Zbl 1172.94565
[12] Chang, D., Dworkin, M., Hong, S., Kelsey, J., Nandi, M.: A keyed sponge construction with pseudorandomness in the standard model. In: NIST’s 3rd SHA-3 Candidate Conference 2012 (2012)
[13] Chen, S., Lampe, R., Lee, J., Seurin, Y., Steinberger, J.: Minimizing the two-round Even-Mansour cipher. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 39–56. Springer, Heidelberg (2014) · Zbl 1317.94095
[14] Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014) · Zbl 1317.94096
[15] Cogliati, B., Lampe, R., Seurin, Y.: Tweaking Even-Mansour ciphers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 493–517. Springer, Heidelberg (2015) · Zbl 1369.94526
[16] Cogliati, B., Seurin, Y.: Beyond-birthday-bound security for tweakable Even-Mansour ciphers with linear tweak and key mixing. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 134–158. Springer, Heidelberg (2015) · Zbl 1375.94113
[17] Cogliati, B., Seurin, Y.: On the provable security of the iterated Even-Mansour cipher against related-key and chosen-key attacks. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 584–613. Springer, Heidelberg (2015) · Zbl 1370.94500
[18] Cogliati, B., Seurin, Y.: Strengthening the known-key security notion for block ciphers. In: FSE 2016. LNCS, Springer, Heidelberg (2016, to appear) · Zbl 1387.94077
[19] Dai, Y., Lee, J., Mennink, B., Steinberger, J.: The security of multiple encryption in the ideal cipher model. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 20–38. Springer, Heidelberg (2014) · Zbl 1317.94100
[20] Datta, N., Nandi, M.: ELmD v1.0, submission to CAESAR competition (2014)
[21] Dobraunig, C., Eichlseder, M., Mendel, F.: Related-key forgeries for Prøst-OTR. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 282–296. Springer, Heidelberg (2015) · Zbl 1382.94093
[22] Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the Even-Mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012) · Zbl 1297.94065
[23] Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 201–224. Springer, Heidelberg (1993) · Zbl 0808.94024
[24] Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997) · Zbl 1053.94552
[25] Farshim, P., Procter, G.: The related-key security of iterated Even-Mansour ciphers. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 342–363. Springer, Heidelberg (2015) · Zbl 1382.94102
[26] Gaži, P., Pietrzak, K., Tessaro, S.: The exact PRF security of truncation: tight bounds for keyed sponges and truncated CBC. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015 Part I. LNCS, vol. 9215, pp. 368–387. Springer, Heidelberg (2015) · Zbl 1375.94127
[27] Granger, R., Jovanovic, P., Mennink, B., Neves, S.: Improved masking for tweakable blockciphers with applications to authenticated encryption. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 263–293. Springer, Heidelberg (2016) · Zbl 1384.94065
[28] Karpman, P.: From distinguishers to key recovery: improved related-key attacks on Even-Mansour. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 177–188. Springer, Heidelberg (2015) · Zbl 1397.94077
[29] Kavun, E., Lauridsen, M., Leander, G., Rechberger, C., Schwabe, P., Yalçın, T.: Prøst v1, submission to CAESAR competition (2014)
[30] Lampe, R., Patarin, J., Seurin, Y.: An asymptotically tight security analysis of the iterated even-mansour cipher. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 278–295. Springer, Heidelberg (2012) · Zbl 1293.94085
[31] Lampe, R., Seurin, Y.: How to construct an ideal cipher from a small set of public permutations. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 444–463. Springer, Heidelberg (2013) · Zbl 1327.94063
[32] Lampe, R., Seurin, Y.: Tweakable blockciphers with asymptotically optimal security. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 133–152. Springer, Heidelberg (2014) · Zbl 1321.94071
[33] Landecker, W., Shrimpton, T., Terashima, R.S.: Tweakable blockciphers with beyond birthday-bound security. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 14–30. Springer, Heidelberg (2012) · Zbl 1294.94058
[34] Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 31–46. Springer, Heidelberg (2002) · Zbl 1026.94533
[35] Mennink, B.: Optimally secure tweakable blockciphers. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 428–448. Springer, Heidelberg (2015) · Zbl 1382.94141
[36] Mennink, B.: Optimally secure tweakable blockciphers. Cryptology ePrint Archive, report 2015/363, full version of [35] (2015) · Zbl 1382.94141
[37] Mennink, B.: XPX: Generalized tweakable Even-Mansour with improved security guarantees. Cryptology ePrint Archive, report 2015/476, full version of this paper (2015) · Zbl 1351.94058
[38] Mennink, B., Preneel, B.: On the XOR of multiple random permutations. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 619–634. Springer, Heidelberg (2015) · Zbl 1423.94089
[39] Mennink, B., Reyhanitabar, R., Vizár, D.: Security of full-state keyed sponge and duplex: applications to authenticated encryption. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 465–489. Springer, Heidelberg (2015) · Zbl 1382.94142
[40] Minematsu, K.: Improved security analysis of XEX and LRW modes. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 96–113. Springer, Heidelberg (2007) · Zbl 1161.94420
[41] Minematsu, K.: Beyond-birthday-bound security based on tweakable block cipher. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 308–326. Springer, Heidelberg (2009) · Zbl 1248.94082
[42] Mouha, N.: Chaskey: a MAC algorithm for microcontrollers - status update and proposal of Chaskey-12. Cryptology ePrint Archive, report 2015/1182 (2015)
[43] Mouha, N., Mennink, B., Van Herrewege, A., Watanabe, D., Preneel, B., Verbauwhede, I.: Chaskey: an efficient MAC algorithm for 32-bit microcontrollers. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 306–323. Springer, Heidelberg (2014) · Zbl 1382.94145
[44] Naito, Y., Yasuda, K.: New bounds for keyed sponges with extendable output: Independence between capacity and message length. In: FSE 2016. LNCS, Springer, Heidelberg (2016, to appear) · Zbl 1387.94094
[45] Nyberg, K., Knudsen, L.R.: Provable security against differential cryptanalysis. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 566–574. Springer, Heidelberg (1993) · Zbl 0824.68037
[46] Patarin, A.: A proof of security in \[ O(2^{n}) \] for the Xor of two randompermutations. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 232–248. Springer, Heidelberg (2008) · Zbl 1162.94397
[47] Procter, G.: A note on the CLRW2 tweakable block cipher construction. Cryptology ePrint Archive, report 2014/111 (2014)
[48] 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 (2004) · Zbl 1094.94035
[49] Sasaki, Y., Todo, Y., Aoki, K., Naito, Y., Sugawara, T., Murakami, Y., Matsui, M., Hirose, S.: Minalpher v1, submission to CAESAR competition (2014)
[50] Steinberger, J.: Improved security bounds for key-alternating ciphers via Hellinger distance. Cryptology ePrint Archive, report 2012/481 (2012)
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.