Advances in the characterization of linear codes and in the cryptanalysis of block ciphers
Keywords:
linear codes, coset leaders, leader codewords, cryptanalysis, block ciphersAbstract
Introduction: There is a need of methodologies that contribute to the characterization of the combinatorial structure of linear and group codes, and to the process of cryptanalysis of block ciphers.
Objective: To characterize large essential sets that allow the development of methodologies for processes involving structures associated with the coset leaders of linear codes and the set of keys of block ciphers.
Methods: The algorithms developed from the designed methodologies, while constructing a list of objects of considerable size, manage to generate a number of elements close to the size of the sets to be constructed. Essential algebraic structures are mathematically characterized, the correctness of algorithms for computing the structures is formulated and demonstrated, the algorithms are built in Computer Algebra systems (Maple and GAP), experiments are carried out, and comparisons and conjectures are made based on the observed patterns.
Results: The characterization and construction of the leader codewords of a linear code, and the design of attack methodologies for block ciphers and the characterization of algebraic structures with applications in cryptography.
Conclusions: The combination of an algebraic study with the design of algorithms and implementation testing on the objects under study has been essential for the characterization and development of the proposed methodologies.
Downloads
References
1. Huffman WC, Pless V. Fundamentals of error-correcting codes. Cambridge, England (United Kingdom): Cambridge University Press; 2003.
2. Menezes A, van Oorschot P, Vanstone S. Handbook of Applied Cryptography. CRC Press; 1996.
3. Sendier N. Finding the Permutation Between Equivalent Linear Codes: The Support Splitting Algorithm. IEEE Trans. Inform. Theory. 2000;46(4):1193-203.
4. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E. On a Gröbner bases structure associated to linear codes. J. Discrete Math. Sci. Cryptogr. 2007;10(2):151-91.
5. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E. Gröbner basis and combinatorics for binary codes. Appl. Algebra Engrg. Comm. Comput. 2008;19(5):393-411.
6. Márquez-Cobella I. A Combinatorial Commutative Algebra Approach to Complete Decoding [tesis doctoral]. Valladolid (España): Universidad de Valladolid; 2013.
7. Aliasgari M, Sadeghi MR, Panario D. Gröbner bases for lattices and an algebraic decoding algorithm. IEEE Trans. on Communications. 2013;61(4):1222-30.
8. Álvarez-Barrientos I, Borges-Quintana M, Borges Trenard MA, Panario D. Computing Gröbner bases associated with lattices. Adv. Math. Commun. 2016; 10(4): 853-862.
9. Mora T. The FGLM problem and Möller’s algorithm on zero-dimensional ideals. Gröbner, Coding, and Cryptography. Springer. 2009:379-84.
10. Dobraunig CE, Eichlseder M, Mendel F. Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates. In: Advances in Cryptology-ASIACRYPT 2015. LNCS;9453. Springer; 2015. Disponible en: https://doi.org/10.1007/978- 3-662-48800-3_20
11. Mora T, Perret L, Sakata S, Sala M, Traverso C, editors. Gröbner, Coding, and Cryptography. Linz (Austria): RISC Book Series, Springer; 2009. Disponible en: https://doi.org/10.1007/978-3-540-93806-4
12. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E. An application of Möller's Algorithm to Coding Theory. In: Mora T, Perret L, Sakata S, Sala M, Traverso C, editors. Gröbner, Coding, and Cryptography. Linz (Austria): RISC Book Series, Springer, 2009;379-84. Disponible en: https://doi.org/10.1007/978-3-540-93806-4_24
13. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E. Gröbner representation of binary matroids. Paper presented at: Bras-Amarós M, Høholdt T, editors. Proceedings of Applied algebra, Algebraic algorithms, and Error Correcting Codes (AAECC’09), Lecture Notes in Comput. Sci. 2009; 5527: 227-230.
14. Borges-Quintana M, Borges-Trenard MA, Galindo C. Improved Evaluation Codes Defined by Plane Valuations. Finite Fields Appl. 2010;16 265-76.
15. Borges-Quintana M, Borges-Trenard MA, Márquez-Corbella I, Martínez-Moro E. Computing coset leaders and leader codewords of binary codes. J. Algebra Appl. 2015;14(8):1-19.
16. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E. Trial set and Gröbner bases for binary codes. Applications of Computer Algebra "ACA 2015". Springer Proc. Math. Stat. 2017;198:21-7. Disponible en: https://doi.org/10.1007/978-3-319- 56932-1_3
17. Borges-Quintana M, Borges-Ternard MA, Martínez-Moro E. On the Weak Order Ideal Associated to Linear Codes. Math. Comput. Sci. 2018;12:339-47. Disponible en: https://doi.org/10.1007/s11786-018-0349-1
18. Borges-Quintana M, Borges-Trenard MA, Martínez-Moro E, Torres-Guerrero G. Computing an Invariant of a Linear Code. In: Slamanig D, Tsigaridas E, Zafeirakopoulos Z, editors. Mathematical Aspects of Computer and Information Sciences (MACIS 2019). Lecture Notes in Comput. Sci., Springer. 2020;11989:218-33.
19. Borges-Quintana M, Ornella-Rodríguez JA. Cálculo de bases de Gröbner completas asociadas a códigos lineales. Ciencias Matemáticas. 2019;33(1):28-35.
20. Moreno-Ramírez J, Borges-Quintana M, Borges-Trenard MA. Choosing TMTO Parameters by means of Linear Optimization. IEEE América Latina. 2015;13(8):2723-27.
21. Mukhopadhyay S. A Study on Time/Memory Trade-Off Cryptanalysis [doctoral thesis]. India: Indian Statistical Institute; 2006.
22. Martínez-Ferrer I, Borges Trenard MA, Borges Quintana M. Criptoanálisis algebraico a cifrados en bloques. Ciencias Matemáticas. 2019;33(1):36-45.
23. Labrada-Claro R, Borges-Trenard MA, Borges-Quintana M. Criptoanálisis algebraico a los cifrados en bloques ligeros SIMON y SIMECK. Revista Cubana de Ciencias Informáticas. 2023;17(1):53-66.
24. Borges-Trenard MA, Borges-Quintana M, Monier-Columbié L. An application of genetic algorithm to cryptanalysis of block ciphers by partitioning the key space. J. Discrete Math. Sci. Cryptogr. 2019. Disponible en: https://doi.org/10.1080/09720529.2019.1649028
25. Tito-Corrioso O, Borges-Trenard MA, Borges-Quintana M, Rojas O, Sosa-Gómez G. Study of Parameters in the Genetic Algorithm for the Attack on Block Ciphers. Symmetry. 2021;13(806):1-12. Disponible en: https://doi.org/10.3390/sym13050806
26. Tito-Corrioso O, Borges-Quintana M, Borges-Trenard MA. Attack to block ciphers by class elimination using the Genetic Algorithm. Revista Investigación Operacional. 2023;44(2):249-63.
27. Tito-Corrioso O, Borges-Quintana M, Borges-Trenard MA, Rojas O, Sosa-Gómez G. On the Fitness Functions Involved in Genetic Algorithms and the Cryptanalysis of Block Ciphers. Entropy. 2023;25(261):1-13. https://doi.org/10.3390/e25020261
28. Donatién-Charón A, Borges-Trenard MA, Borges-Quintana M. Ataque al PRESENT-80 con el Algoritmo Genético mediante aproximaciones sucesivas de componentes fijas. Revista Cubana de Ciencias Informáticas. 2023;17(1):1-15.
29. Tito-Corrioso O, Borges-Quintana M, Borges-Trenard MA. Improving search of solutions of MRHS systems using the Genetic Algorithm. Revista Cubana de Ciencias Informáticas. 2023;17(1):38-52.
30. Ding C, Tang C, Tonchev VD. Linear codes of 2-designs associated with subcodes of the ternary generalized Reed–Müller codes. Des. Codes Cryptogr. 2020; 88: 625- 641.
31. Du X, Wang R, Fan C. Infinite families of 2‐designs from a class of cyclic codes. J Combin. Designs. 2020;28:157-70.
32. Yan H, Liu H, Li Ch, Yang Sh. Parameters of lcd bch codes with two lengths. Adv. Math. Commun. 2018;12(3):579-594.
33. Huang X, Yue Q, Wu Y. Binary primitive LCD BCH codes. Des. Codes Cryptogr. 2020;88:2453-73.
34. Liu L, Zhuang Y, Zhang L, Tang H, Dong S. Proactive correction coset decoding scheme based on SEC-DED code for multibit asymmetric errors in STT-MRAM. Microelectronics Journal. 2018;82:92-100.
35. Liu H, Pan X. Galois hulls of linear codes over finite fields. Des. Codes Cryptogr. 2020;88:241-55.
36. Liu Y, Li R, Fu Q, Lu L, Rao Y. Some binary BCH codes with length n = 2m + 1. Finite Fields Appl. 2019;55:109-33.
37. Biyashev R, Dyusenbayev D, Algazy K, Kapalova N. Algebraic Cryptanalysis of Block Ciphers. Proceedings of the 2019 International Conference on Wireless Communication, Network and Multimedia Engineering (WCNME 2019). Atlantis Press; 2019. p. 129-32.
38. Grari H, Azouaoui A, Zine-Dine K. A cryptanalytic attack of simplified-AES using ant colony optimization. International Journal of Electrical and Computer Engineering. 2019;9(5):4287-95.
39. Hassan F, Riyam A, Jawad N. Using Evolving Algorithms to Cryptanalysis Nonlinear Cryptosystems. Baghdad Science Journal. 2020;17(2).
40. Pavlenko A, Semenov A, Ulyantsev V. Evolutionary Computation Techniques for Constructing SAT-Based Attacks in Algebraic Cryptanalysis. In: Kaufmann P, Castillo P, editors. Applications of Evolutionary Computation. EvoApplications 2019. Lecture Notes in Comput. Sci. Vol. 11454. Springer; 2019.
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Mijail Borges Quintana, Miguel Angel Borges Trenard, Edgar Martínez Moro, Osmani Tito Corrioso
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The journal Anales de la Academia de Ciencias de Cuba protects copyright, and operates with a Creative Commons License 4.0 (Creative Commons Attribution-NonCommercial License 4.0). By publishing in it, authors allow themselves to copy, reproduce, distribute, publicly communicate their work and generate derivative works, as long as the original author is cited and acknowledged. They do not allow, however, the use of the original work for commercial or lucrative purposes.
The authors authorize the publication of their writings, retaining the authorship rights, and assigning and transferring to the magazine all the rights protected by the intellectual property laws that govern in Cuba, which imply editing to disseminate the work.
Authors may establish additional agreements for the non-exclusive distribution of the version of the work published in the journal (for example, placing it in an institutional repository or publishing it in a book), with recognition of having been first published in this journal.
To learn more, see https://creativecommons.org
