|
Article information
2019 , Volume 24, ¹ 5, p.4-12
Abdurakhimov B.F., Sattarov A.B., Yuldashev Z.K.
Algebraic immunity of Boolean function
The algebraic method of cryptanalysis, based on solving systems of equations over a finite field, is one of the modern methods that is widely used in the process of assessing the strength of a stream encryption algorithm. In practice, as part of the majority of stream encryption algorithms, Boolean functions are used as the main transformations. The algebraic immunity of this Boolean function is one of the main parameters determining the strength of the encryption algorithm. In the article, a method for determining the index of algebraic immunity of a Boolean function is proposed, and an algorithm for calculating this function is constructed. To determine the index of algebraic immunity of a Boolean function, the operation of calculating the rank of a specially constructed matrix is used. A number of examples are given for calculation of the algebraic immunity of a Boolean function and construction of annihilator functions. Also, the results of the experiments are shown, by the definition of the algebraic immunity of all balanced and unbalanced Boolean functions over a finite field ℱn (1 < n < 6). The method may be used in the process of algebraic cryptanalysis in order to assess the strength of stream encryption algorithms.
[full text]
Keywords: encryption, stream encryption algorithm, Boolean function, annihilator, algebraic immunity, algebraic cryptanalysis
doi: 10.25743/ICT.2019.24.5.002
Author(s):
Abdurakhimov Bakhtier Fayzievich
Dr. , Professor
Position: Professor
Office: National University of Uzbekistan
Address: 100174, Uzbekistan, Tashkent, University str., 4
Phone Office: (99893)-5143137
E-mail: a_bakhtiyor@mail.ru
Sattarov Alizhon Bozorboevich
Office: National University of Uzbekistan
Address: 100174, Uzbekistan, Tashkent, University str., 4
Phone Office: (99893)-5143137
E-mail: asb2602@mail.ru
Yuldashev Ziyaviddin Khabibovich
Dr. , Professor
Position: Professor
Office: National University of Uzbekistan
Address: 100174, Uzbekistan, Tashkent, University str., 4
Phone Office: (99893)-5826150
References:
[1] Abdurakhimov, B.F., Sattarov, A.B. An algorithm for constructing S-boxes for block symmetric encryption. Universal Journal of Mathematics and Applications. 2018; 1(1):29–32.
[2] Abdurakhimov, B.F., Sattarov, A.B. The method of constructing S-boxes with maximum algebraic immunity. Transactions of the Intern. Sci. Conf. “Modern Problems of Applied Mathematics and Information Technologies-Al-Khorezmiy 2016”. Tashkent; 2016: 130–132.
[3] Courtois, N. Fast algebraic attacks on stream ciphers with linear feedback. Boneh, D. (ed.) CRYPTO 2003. Lecture Notes in Computer Sciences. 2003; (2729):176–194.
[4] Courtois, N., Meier, W. Algebraic attacks on stream ciphers with linear feedback. Biham, E. (ed.) EUROCRYPT. Lecture Notes in Computer Sciences. 2003; (2656):345–359.
[5] Tokaryeva, N.N. Nelineynye bulevy funktsii: bent-funktsii i ikh obobshcheniya [Nonlinear Boolean functions: Bent functions and their generalizations]. Saarbrucken, Germany: Lap Lambert Academic Publishing; 2011: 180. (In Russ.)
[6] Meier, W., Pasalic, E., Carlet, C. Algebraic attacks and decomposition of boolean functions. International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT 2004: Advances in Cryptology - EUROCRYPT 2004. Lecture Notes in Computer Sciences. 2004. Vol. 3027. P. 474–491.
[7] Baev, V.V. Effektivnye algoritmy polucheniya otsenok algebraicheskoy immunnosti bulevykh funktsiy [Effective algorithms for obtaining estimates of algebraic immunity of Boolean functions: Dis. ... kand. fiz.-math. nauk]. Moscow: MGU im. M.V. Lomonosova; 2007: 101. (In Russ.)
[8] Lobanov, M.S. O sootnosheniyakh mezhdu algebraicheskoy immunnost'yu i nelineynost'yu bulevykh funktsiy [On the relationship between algebraic immunity and nonlinearity of Boolean functions: Dis. ... kand. fiz.-math. nauk]. Moscow: MGU im. M.V. Lomonosova; 2009: 64. (In Russ.)
[9] Armknecht, F., Carlet, C., Gaborit, P., Künzli, S., Meier, W., Ruatta, O. Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT 2006: Advances in Cryptology — Eurocrypt 2006. Lecture Notes in Computer Science. 2006; (4004):147–164.
[10] Didier, F., Tillich, J.-P. Computing the algebraic immunity efficiently. Robshaw, M. (ed.) FSE 2006. Lecture Notes in Computer Sciences. 2006; (4047):359–374.
Bibliography link:
Abdurakhimov B.F., Sattarov A.B., Yuldashev Z.K. Algebraic immunity of Boolean function // Computational technologies. 2019. V. 24. ¹ 5. P. 4-12
|
