[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Mathematical aspects of division property

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

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 weaknesses 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. This, and the picture of the Feistel cipher are taken from [19].

References

  1. Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE’94. LNCS, vol. 1008, pp. 196–211. Springer. https://doi.org/10.1007/3-540-60590-8_16 (1995)

  2. Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS , vol. 2365, pp. 112–127. Springer. https://doi.org/10.1007/3-540-45661-9_9 (2002)

  3. Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer. https://doi.org/10.1007/978-3-642-01001-9_16 (2009)

  4. 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. https://doi.org/10.1007/978-3-662-46800-5_12 (2015)

  5. 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. https://doi.org/10.1007/978-3-662-47989-6_20 (2015)

  6. Todo, Y.: Integral cryptanalysis on full MISTY1. J. Cryptol. 30(3), 920–959 (2017). https://doi.org/10.1007/s00145-016-9240-x

    Article  MathSciNet  MATH  Google Scholar 

  7. 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. https://doi.org/10.1007/978-3-662-52993-5_18 (2016)

  8. 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. https://doi.org/10.1007/978-3-030-45721-1_17 (2020)

  9. 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). https://doi.org/10.1007/s00145-021-09383-2

    Article  MathSciNet  MATH  Google Scholar 

  10. 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. https://doi.org/10.1007/978-3-662-53887-6_24 (2016)

  11. 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. https://doi.org/10.1007/978-3-662-53018-4_24 (2016)

  12. 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)

    Article  MathSciNet  MATH  Google Scholar 

  13. 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). https://doi.org/10.13154/tosc.v2016.i2.226-247. https://tosc.iacr.org/index.php/ToSC/article/view/572

    Article  Google Scholar 

  14. Carlet, C.: Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions. IEEE Transactions on Information Theory, 1–1. https://doi.org/10.1109/TIT.2020.3017494 (2020)

  15. 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). https://doi.org/10.46586/tosc.v2021.i1.411-442

    Article  Google Scholar 

  16. 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. https://doi.org/10.1007/978-3-030-92062-3_12 (2021)

  17. 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. https://doi.org/10.1007/978-3-030-64837-4_15 (2020)

  18. Carlet, C.: Boolean functions for cryptography and coding theory, Cambridge University Press. https://doi.org/10.1017/9781108606806 (2021)

  19. Jean, J.: TikZ for Cryptographers. https://www.iacr.org/authors/tikz/

  20. Shannon, C.: A mathematical theory of cryptography (1945)

  21. 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. https://doi.org/10.1007/3-540-44706-7_15 (2001)

  22. 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)

    Article  Google Scholar 

  23. 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). https://doi.org/10.13154/tosc.v2019.i3.81-102

    Article  Google Scholar 

  24. 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. https://doi.org/10.1007/978-3-030-64837-4_18 (2020)

  25. Hebborn, P.: Security assessment and design of symmetric ciphers for emerging applications. doctoralthesis, Ruhr-Universität Bochum, Universitätsbibliothek. https://doi.org/10.13154/294-8588 (2022)

  26. Zhang, W., Rijmen, V.: Division cryptanalysis of block ciphers with a binary diffusion layer. IET Inf. Secur. 13(2), 87–95 (2018)

    Article  Google Scholar 

  27. Hu, K., Wang, Q., Wang, M.: IACR transactions class documentation. IACR Trans. Symm. Cryptol. 2020(1), 396–424 (2020). https://doi.org/10.13154/tosc.v2020.i1.396-424

    Article  Google Scholar 

  28. 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

  29. Lambin, B., Derbez, P., Fouque, P. -A.: Linearly equivalent S-boxes and the division property. Des. Codes Crypt. 88(10), 2207–2231 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  30. Derbez, P., Fouque, P.-A.: Increasing precision of division property . IACR Trans. Symm. Cryptol. 2020(4), 173–194 (2020). https://doi.org/10.46586/tosc.v2020.i4.173-194

    Article  Google Scholar 

  31. 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. https://doi.org/10.1007/3-540-46035-7_34 (2002)

  32. 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. https://doi.org/10.1007/978-3-642-21702-9_15 (2011)

  33. Perrin, L., Udovenko, A.: Algebraic insights into the secret Feistel network. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 378–398. Springer. https://doi.org/10.1007/978-3-662-52993-5_19 (2016)

  34. Carlet, C.: Handling vectorial functions by means of their graph indicators. IEEE Trans. Inf. Theory 66(10), 6324–6339 (2020). https://doi.org/10.1109/TIT.2020.2981524

    Article  MathSciNet  MATH  Google Scholar 

  35. 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)

  36. 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. https://doi.org/10.1007/978-3-030-92062-3_13 (2021)

  37. Todo, Y., Morii, M.: Compact representation for division property. In: Foresti, S., Persiano, G. (eds.) CANS 16. LNCS, vol. 10052, pp. 19–35. Springer. https://doi.org/10.1007/978-3-319-48965-0_2 (2016)

  38. 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. https://doi.org/10.1007/978-3-319-63697-9_9 (2017)

  39. 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)

  40. 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. https://doi.org/10.1007/978-3-030-34618-8_14 (2019)

  41. 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)

    Article  Google Scholar 

  42. 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. https://doi.org/10.1007/978-3-030-99277-4_13 (2022)

  43. 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. https://doi.org/10.1007/978-3-030-90567-5_6 (2021)

  44. 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. https://doi.org/10.1007/978-3-319-70694-8_5 (2017)

  45. 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. https://doi.org/10.1007/978-3-030-01950-1_38 (2018)

  46. 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. https://doi.org/10.1007/978-3-030-10970-7_6 (2019)

  47. 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. https://doi.org/10.1007/978-3-030-12612-4_21 (2019)

  48. 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)

Download references

Acknowledgements

The authors thank Claude Carlet for proposing the idea of this survey and the anonymous reviewers for their valuable suggestions which helped to greatly improve this work. The work was supported by the Luxembourg National Research Fund’s (FNR) and the German Research Foundation’s (DFG) joint project APLICA (C19/IS/13641232).

Funding

The work was supported by the Luxembourg National Research Fund’s (FNR) and the German Research Foundation’s (DFG) joint project APLICA (C19/IS/13641232).

Author information

Authors and Affiliations

  1. Ruhr-Universität Bochum, Bochum, Germany

    Phil Hebborn & Gregor Leander

  2. SnT, University of Luxembourg, Esch-sur-Alzette, Luxembourg

    Aleksei Udovenko

  3. CryptoExperts, Paris, France

    Aleksei Udovenko

Authors
  1. Phil Hebborn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gregor Leander
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Aleksei Udovenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Phil Hebborn wrote Section 6 and part of Section 3. Gregor Leander wrote Section 1, Section 7 and parts of Section 2 and Section 3. Aleksei Udovenko wrote Section 4, Section 5 and parts of Section 2 and Section 3. Gregor Leander and Aleksei Udovenko edited the final manuscript.

Corresponding author

Correspondence to Aleksei Udovenko.

Ethics declarations

Ethics approval and consent to participate

This work raises no ethical concerns.

Consent for Publication

All authors give consent for publication of this work.

Competing interests

The authors have no relevant financial or non-financial interests to disclose.

Availability of supporting data

This work has no supporting data.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hebborn, P., Leander, G. & Udovenko, A. Mathematical aspects of division property. Cryptogr. Commun. 15, 731–774 (2023). https://doi.org/10.1007/s12095-022-00622-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-022-00622-2

Keywords

Mathematics Subject Classification (2010)

Search

Navigation