Mathematical Aspects of Division Property

[en] This work surveys mathematical aspects of division property, which is a state of the art technique in cryptanalysis of symmetric-key algorithms, such as authenticated encryption, block ciphers and stream ciphers. It aims to find integral distinguishers and cube attacks, which exploit weakness in the algebraic normal forms of the output coordinates of the involved vectorial Boolean functions. Division property can also be used to provide arguments for security of primitives against these attacks. The focus of this work is a formal presentation of the theory behind the division property, including rigorous proofs, which were often omitted in the existing literature. This survey covers the two major variants of division property, namely conventional and perfect division property. In addition, we explore relationships of the technique with classic degree bounds

Disciplines :

Sciences informatiques

Auteur, co-auteur :

Hebborn, Phil; Ruhr-Universität Bochum - RUB

Leander, Gregor; Ruhr-Universität Bochum - RUB

UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux ; CryptoExperts, Paris, France

Co-auteurs externes :

yes

Langue du document :

Anglais

Titre :

Mathematical Aspects of Division Property

Date de publication/diffusion :

02 mars 2023

Titre du périodique :

Cryptography and Communications

ISSN :

1936-2447

eISSN :

1936-2455

Maison d'édition :

Springer, New York, Etats-Unis - New York

Peer reviewed :

Peer reviewed vérifié par ORBi

Focus Area :

Computational Sciences

URL complémentaire :

https://ia.cr/2022/736

Projet FnR :

FNR13641232 - Analysis And Protection Of Lightweight Cryptographic Algorithms, 2019 (01/01/2021-31/12/2023) - Alex Biryukov

Organisme subsidiant :

FNR - Fonds National de la Recherche
DFG - Deutsche Forschungsgemeinschaft

Disponible sur ORBilu :

depuis le 19 décembre 2022

Statistiques

Nombre de vues

165 (dont 2 Unilu)

Nombre de téléchargements

108 (dont 1 Unilu)

Voir plus de statistiques

citations Scopus^®

citations Scopus^®
sans auto-citations

citations OpenAlex

citations WoS^™

Bibliographie

Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE’94. LNCS, vol. 1008, pp. 196–211. Springer. 10.1007/3-540-60590-8_16 (1995)
Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer. 10.1007/3-540-45661-9_9 (2002)
Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer. 10.1007/978-3-642-01001-9_16 (2009)
Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 287–314. Springer. 10.1007/978-3-662-46800-5_12 (2015)
Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 413–432. Springer. 10.1007/978-3-662-47989-6_20 (2015)
Todo, Y.: Integral cryptanalysis on full MISTY1. J. Cryptol. 30(3), 920–959 (2017). 10.1007/s00145-016-9240-x DOI: 10.1007/s00145-016-9240-x
Todo, Y., Morii, M.: Bit-based division property and application to simon family. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 357–377. Springer. 10.1007/978-3-662-52993-5_18 (2016)
Hao, Y., Leander, G., Meier, W., Todo, Y., Wang, Q.: Modeling for three-subset division property without unknown subset - improved cube attacks against Trivium and Grain-128AEAD. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part I. LNCS, vol. 12105, pp. 466–495. Springer. 10.1007/978-3-030-45721-1_17 (2020)
Hao, Y., Leander, G., Meier, W., Todo, Y., Wang, Q.: Modeling for three-subset division property without unknown subset. J. Cryptol. 34(3), 22 (2021). 10.1007/s00145-021-09383-2 DOI: 10.1007/s00145-021-09383-2
Xiang, Z., Zhang, W., Bao, Z., Lin, D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 648–678. Springer. 10.1007/978-3-662-53887-6_24 (2016)
Boura, C., Canteaut, A.: Another view of the division property. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 654–682. Springer. 10.1007/978-3-662-53018-4_24 (2016)
Boura, C., Canteaut, A.: On the influence of the algebraic degree of f − 1 on the algebraic degree of G ∘ F. IEEE Trans. Inf. Theory 59(1), 691–702 (2013) DOI: 10.1109/TIT.2012.2214203
Biryukov, A., Khovratovich, D., Perrin, L.: Multiset-algebraic cryptanalysis of reduced Kuznyechik, Khazad, and secret SPNs. IACR Trans. Symm. Cryptol. 2016(2), 226–247 (2016). 10.13154/tosc.v2016.i2.226-247. https://tosc.iacr.org/index.php/ToSC/article/view/572 DOI: 10.13154/tosc.v2016.i2.226-247
Carlet, C.: Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions. IEEE Transactions on Information Theory, 1–1. 10.1109/TIT.2020.3017494 (2020)
Chen, S., Xiang, Z., Zeng, X., Zhang, S.: On the relationships between different methods for degree evaluation. IACR Trans. Symm. Cryptol. 2021(1), 411–442 (2021). 10.46586/tosc.v2021.i1.411-442 DOI: 10.46586/tosc.v2021.i1.411-442
Udovenko, A.: Convexity of division property transitions: Theory, algorithms and compact models. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part I. LNCS, vol. 13090, pp. 332–361. Springer. 10.1007/978-3-030-92062-3_12 (2021)
Hu, K., Sun, S., Wang, M., Wang, Q.: An algebraic formulation of the division property: Revisiting degree evaluations, cube attacks, and key-independent sums. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part I. LNCS, vol. 12491, pp. 446–476. Springer. 10.1007/978-3-030-64837-4_15 (2020)
Carlet, C.: Boolean functions for cryptography and coding theory, Cambridge University Press. 10.1017/9781108606806 (2021)
Jean, J.: TikZ for Cryptographers. https://www.iacr.org/authors/tikz/
Shannon, C.: A mathematical theory of cryptography (1945)
Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., Whiting, D.: Improved cryptanalysis of Rijndael. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer. 10.1007/3-540-44706-7_15 (2001)
Todo, Y., Aoki, K.: Fast fourier transform key recovery for integral attacks. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 98-A (9), 1944–1952 (2015) DOI: 10.1587/transfun.E98.A.1944
Ye, C.-D., Tian, T.: Revisit division property based cube attacks: key-recovery or distinguishing attacks?. IACR Trans. Symm. Cryptol. 2019(3), 81–102 (2019). 10.13154/tosc.v2019.i3.81-102 DOI: 10.13154/tosc.v2019.i3.81-102
Hebborn, P., Lambin, B., Leander, G., Todo, Y.: Lower bounds on the degree of block ciphers. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part I. LNCS, vol. 12491, pp. 537–566. Springer. 10.1007/978-3-030-64837-4_18 (2020)
Hebborn, P.: Security assessment and design of symmetric ciphers for emerging applications. doctoralthesis, Ruhr-Universität Bochum, Universitätsbibliothek. 10.13154/294-8588 (2022)
Zhang, W., Rijmen, V.: Division cryptanalysis of block ciphers with a binary diffusion layer. IET Inf. Secur. 13(2), 87–95 (2018) DOI: 10.1049/iet-ifs.2018.5151
Hu, K., Wang, Q., Wang, M.: IACR transactions class documentation. IACR Trans. Symm. Cryptol. 2020(1), 396–424 (2020). 10.13154/tosc.v2020.i1.396-424 DOI: 10.13154/tosc.v2020.i1.396-424
Göloğlu, F., Rijmen, V., Wang, Q.: On the division property of S-boxes. Cryptology ePrint Archive, Report 2016/188.(2016) https://eprint.iacr.org/2016/188
Lambin, B., Derbez, P., Fouque, P. -A.: Linearly equivalent S-boxes and the division property. Des. Codes Crypt. 88(10), 2207–2231 (2020) DOI: 10.1007/s10623-020-00773-4
Derbez, P., Fouque, P.-A.: Increasing precision of division property. IACR Trans. Symm. Cryptol. 2020(4), 173–194 (2020). 10.46586/tosc.v2020.i4.173-194 DOI: 10.46586/tosc.v2020.i4.173-194
Canteaut, A., Videau, M.: Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 518–533. Springer. 10.1007/3-540-46035-7_34 (2002)
Boura, C., Canteaut, A.: De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer. 10.1007/978-3-642-21702-9_15 (2011)
Perrin, L., Udovenko, A.: Algebraic insights into the secret Feistel network. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 378–398. Springer. 10.1007/978-3-662-52993-5_19 (2016)
Carlet, C.: Handling vectorial functions by means of their graph indicators. IEEE Trans. Inf. Theory 66(10), 6324–6339 (2020). 10.1109/TIT.2020.2981524 DOI: 10.1109/TIT.2020.2981524
Lai, X.: Higher order derivatives and differential cryptanalysis. In: Communications and cryptography. the springer international series in engineering and computer science, Vol. 276, Pp. 227–233. Springer (1994)
Hebborn, P., Lambin, B., Leander, G., Todo, Y.: Strong and tight security guarantees against integral distinguishers. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part I. LNCS, vol. 13090, pp. 362–391. Springer. 10.1007/978-3-030-92062-3_13 (2021)
Todo, Y., Morii, M.: Compact representation for division property. In: Foresti, S., Persiano, G. (eds.) CANS 16. LNCS, vol. 10052, pp. 19–35. Springer. 10.1007/978-3-319-48965-0_2 (2016)
Todo, Y., Isobe, T., Hao, Y., Meier, W.: Cube attacks on non-blackbox polynomials based on division property. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 250–279. Springer. 10.1007/978-3-319-63697-9_9 (2017)
Sasaki, Y., Todo, Y.: New algorithm for modeling S-box in MILP Based Differential and division trail search. In: SECITC. Lecture Notes in Computer Science, Vol. 10543, Pp. 150–165. Springer (2017)
Wang, S., Hu, B., Guan, J., Zhang, K., Shi, T.: MILP-aided method of searching division property using three subsets and applications. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part III. LNCS, vol. 11923, pp. 398–427. Springer. 10.1007/978-3-030-34618-8_14 (2019)
Sun, L., Wang, W., Wang, M.: MILP-Aided bit-based division property for primitives with non-bit-permutation linear layers. IET. Inf. Secur. 14(1), 12–20 (2020) DOI: 10.1049/iet-ifs.2018.5283
Delaune, S., Derbez, P., Gontier, A., Prud’homme, C.: A simpler model for recovering superpoly on trivium. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 266–285. Springer. 10.1007/978-3-030-99277-4_13 (2022)
ElSheikh, M., Youssef, A.M.: On MILP-based automatic search for bit-based division property for ciphers with (large) linear layers. In: Baek, J., Ruj, S. (eds.) ACISP 21. LNCS, vol. 13083, pp. 111–131. Springer. 10.1007/978-3-030-90567-5_6 (2021)
Sun, L., Wang, W., Wang, M.: Automatic search of bit-based division property for ARX ciphers and word-based division property. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part I. LNCS, vol. 10624, pp. 128–157. Springer. 10.1007/978-3-319-70694-8_5 (2017)
Han, Y., Li, Y., Wang, M.: Automatical method for searching integrals of ARX block cipher with division property using three subsets. In: Naccache, D., Xu, S., Qing, S., Samarati, P., Blanc, G., Lu, R., Zhang, Z., Meddahi, A. (eds.) ICICS 18. LNCS, vol. 11149, pp. 647–663. Springer. 10.1007/978-3-030-01950-1_38 (2018)
Eskandari, Z., Kidmose, A. B., Kölbl, S., Tiessen, T.: Finding integral distinguishers with ease. In: Cid, C., Jacobson Jr:, M.J. (eds.) SAC 2018. LNCS, vol. 11349, pp. 115–138. Springer. 10.1007/978-3-030-10970-7_6 (2019)
Hu, K., Wang, M.: Automatic search for a variant of division property using three subsets. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 412–432. Springer. 10.1007/978-3-030-12612-4_21 (2019)
Ghosh, S., Dunkelman, O.: Automatic search for bit-based division property. In: LATINCRYPT. lecture notes in computer science, Vol. 12912, pp. 254–274. Springer (2021)