Mathematical Aspects of Division Property

Hebborn, Phil; Leander, Gregor; Udovenko, Aleksei

doi:10.1007/s12095-022-00622-2

Download

Article (Scientific journals)

Mathematical Aspects of Division Property

Hebborn, Phil; Leander, Gregor; Udovenko, Aleksei

2023 • In Cryptography and Communications

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/10993/53221

DOI
10.1007/s12095-022-00622-2

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

AM.pdf

Author postprint (662.51 kB)

Download

This version of the article has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s12095-022-00622-2. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https: //www.springernature.com/gp/open-research/policies/acceptedmanuscript-terms.

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

symmetric cryptography; Boolean functions; algebraic degree; integral cryptanalysis; division property

Abstract :

[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 :

Computer science

Author, co-author :

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

External co-authors :

yes

Language :

English

Title :

Mathematical Aspects of Division Property

Publication date :

02 March 2023

Journal title :

Cryptography and Communications

ISSN :

1936-2455

Publisher :

Springer, New York, United States - New York

Peer reviewed :

Peer Reviewed verified by ORBi

Focus Area :

Computational Sciences

Additional URL :

https://ia.cr/2022/736

FnR Project :

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

Funders :

FNR - Fonds National de la Recherche [LU]
DFG - Deutsche Forschungsgemeinschaft [DE]

Available on ORBilu :

since 19 December 2022

Statistics

Number of views

40 (1 by Unilu)

Number of downloads

15 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

WoS citations^™

Bibliography

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)