Lower bounds on the degree of block ciphers. (English) Zbl 1511.94109
Moriai, Shiho (ed.) et al., Advances in cryptology – ASIACRYPT 2020. 26th international conference on the theory and application of cryptology and information security, Daejeon, South Korea, December 7–11, 2020. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12491, 537-566 (2020).
Summary: Only the method to estimate the upper bound of the algebraic degree on block ciphers is known so far, but it is not useful for the designer to guarantee the security. In this paper we provide meaningful lower bounds on the algebraic degree of modern block ciphers.
For the entire collection see [Zbl 1507.94004].
For the entire collection see [Zbl 1507.94004].
MSC:
| 94A60 | Cryptography |
Keywords:
block cipher; algebraic degree; minimum degree; lower bounds; division property; parity setReferences:
| [1] | Abdelkhalek, A., Sasaki, Y., Todo, Y., Tolba, M., Youssef, A.M.: MILP modeling for (large) s-boxes to optimize probability of differential characteristics. IACR Trans. Symmetric Cryptol. 2017(4), 99-129 (2017). doi:10.13154/tosc.v2017.i4.99-129 |
| [2] | Banik, S.; Pandey, SK; Peyrin, T.; Sasaki, Y.; Sim, SM; Todo, Y.; Fischer, W.; Homma, N., GIFT: a small present, Cryptographic Hardware and Embedded Systems - CHES 2017, 321-345 (2017), Cham: Springer, Cham · Zbl 1450.94026 · doi:10.1007/978-3-319-66787-4_16 |
| [3] | Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptol. ePrint Arch. 2013, 404 (2013). http://eprint.iacr.org/2013/404 |
| [4] | Beierle, C.; Robshaw, M.; Katz, J., The SKINNY family of block ciphers and its low-latency variant MANTIS, Advances in Cryptology - CRYPTO 2016, 123-153 (2016), Heidelberg: Springer, Heidelberg · Zbl 1372.94412 · doi:10.1007/978-3-662-53008-5_5 |
| [5] | Bogdanov, A.; Paillier, P.; Verbauwhede, I., PRESENT: an ultra-lightweight block cipher, Cryptographic Hardware and Embedded Systems - CHES 2007, 450-466 (2007), Heidelberg: Springer, Heidelberg · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31 |
| [6] | Boura, C.; Canteaut, A., On the influence of the algebraic degree of f \({}^{\text{-1}}\) on the algebraic degree of G \(\circ F\), IEEE Trans. Inf. Theory, 59, 1, 691-702 (2013) · Zbl 1364.94526 · doi:10.1109/TIT.2012.2214203 |
| [7] | Boura, C.; Canteaut, A.; Robshaw, M.; Katz, J., Another view of the division property, Advances in Cryptology - CRYPTO 2016, 654-682 (2016), Heidelberg: Springer, Heidelberg · Zbl 1378.94026 · doi:10.1007/978-3-662-53018-4_24 |
| [8] | Boura, C.; Canteaut, A.; De Cannière, C.; Joux, A., Higher-order differential properties of Keccak and Luffa, Fast Software Encryption, 252-269 (2011), Heidelberg: Springer, Heidelberg · Zbl 1307.94040 · doi:10.1007/978-3-642-21702-9_15 |
| [9] | Carlet, C., Crama, Y., Hammer, P.L.: Vectorial boolean functions for cryptography. In: Crama, Y., Hammer, P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 398-470. Cambridge University Press (2010). doi:10.1017/cbo9780511780448.012 · Zbl 1196.06001 |
| [10] | Daemen, J.; Knudsen, L.; Rijmen, V.; Biham, E., The block cipher square, Fast Software Encryption, 149-165 (1997), Heidelberg: Springer, Heidelberg · Zbl 1385.94025 · doi:10.1007/BFb0052343 |
| [11] | Dinur, I.; Shamir, A.; Joux, A., Cube attacks on tweakable black box polynomials, Advances in Cryptology - EUROCRYPT 2009, 278-299 (2009), Heidelberg: Springer, Heidelberg · Zbl 1239.94045 · doi:10.1007/978-3-642-01001-9_16 |
| [12] | Hao, Y.; Leander, G.; Meier, W.; Todo, Y.; Wang, Q.; Canteaut, A.; Ishai, Y., Modeling for three-subset division property without unknown subset, Advances in Cryptology - EUROCRYPT 2020, 466-495 (2020), Cham: Springer, Cham · Zbl 1479.94187 · doi:10.1007/978-3-030-45721-1_17 |
| [13] | Jean, J.: TikZ for Cryptographers. https://www.iacr.org/authors/tikz/ (2016) |
| [14] | Knudsen, L.; Wagner, D.; Daemen, J.; Rijmen, V., Integral cryptanalysis, Fast Software Encryption, 112-127 (2002), Heidelberg: Springer, Heidelberg · Zbl 1045.94527 · doi:10.1007/3-540-45661-9_9 |
| [15] | Lai, X.; Blahut, RE; Costello, DJ; Maurer, U.; Mittelholzer, T., Higher order derivatives and differential cryptanalysis, Communications and Cryptography, 227-233 (1994), Boston: Springer, Boston · Zbl 0840.94017 · doi:10.1007/978-1-4615-2694-0_23 |
| [16] | Sun, L.; Wang, W.; Wang, M.; Takagi, T.; Peyrin, T., Automatic search of bit-based division property for ARX ciphers and word-based division property, Advances in Cryptology - ASIACRYPT 2017, 128-157 (2017), Cham: Springer, Cham · Zbl 1420.94097 · doi:10.1007/978-3-319-70694-8_5 |
| [17] | Thurley, M.; Biere, A.; Gomes, CP, sharpSAT - counting models with advanced component caching and implicit BCP, Theory and Applications of Satisfiability Testing - SAT 2006, 424-429 (2006), Heidelberg: Springer, Heidelberg · doi:10.1007/11814948_38 |
| [18] | Todo, Y.; Gennaro, R.; Robshaw, M., Integral cryptanalysis on full MISTY1, Advances in Cryptology - CRYPTO 2015, 413-432 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94158 · doi:10.1007/978-3-662-47989-6_20 |
| [19] | Todo, Y.; Oswald, E.; Fischlin, M., Structural evaluation by generalized integral property, Advances in Cryptology - EUROCRYPT 2015, 287-314 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94545 · doi:10.1007/978-3-662-46800-5_12 |
| [20] | Todo, Y., Integral cryptanalysis on full MISTY1, J. Cryptol., 30, 3, 920-959 (2016) · Zbl 1377.94066 · doi:10.1007/s00145-016-9240-x |
| [21] | Todo, Y.; Morii, M.; Peyrin, T., Bit-based division property and application to Simon family, Fast Software Encryption, 357-377 (2016), Heidelberg: Springer, Heidelberg · Zbl 1387.94102 · doi:10.1007/978-3-662-52993-5_18 |
| [22] | Xiang, Z.; Zhang, W.; Bao, Z.; Lin, D.; Cheon, JH; Takagi, T., Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers, Advances in Cryptology - ASIACRYPT 2016, 648-678 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94120 · doi:10.1007/978-3-662-53887-6_24 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
