A METHOD OF CONSTRUCTING A BLOCK CIPHERS ROUND FUNCTION’S POLYNOMIAL OVER A FINITE FIELD
Abstract
The work outlines the method of construction of round function as a polynomial of one variable over the finite field. The proposed method is based on the calculation of the initial cryptographic transformation at special points of the finite field and the subsequent inversion of Vandermonde matrix. For this class of matrices, there are algorithms for calculating the inverse matrix, which are much more efficient than the standard algorithm of inversion using the Gauss method. In the proposed work, the Traub algorithm is used. The computational complexity of Traub algorithm is proportional to the square of the size of a given matrix. The method is applicable to block iterative ciphers of special type (SP-network). For this type of ciphers, mathematical evaluations of algebraic parameters of polinomials of round functions over the finite fields are provided. Quantative values of estimations are calculated for Russian encryption standard "Kuznechik". The estimates of computational complexity of the proposed method are provided. The article contains practical results of estimations of work time for polynomials notation for finite fields of varying dimensions. The proposed method is used for explicit calculation of the polynomial of one variable over the finite field of round function of block cipher PRESENT.
References
[2] Matsui M. Linear cryptanalysis method for DES cipher. Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1993. Pp. 386-397. DOI: 10.1007/3-540-48285-7_33
[3] Jakobsen T., Knudsen L.R. The interpolation attack on block ciphers. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1997. Pp. 28-40. DOI: 10.1007/BFb0052332
[4] Nyberg K., Knudsen L.R. Provable security against a differential attack. Journal of Cryptology. 1995; 8(1):27-37. DOI: 10.1007/BF00204800
[5] Rijmen V. et al. The cipher SHARK. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1996. Pp. 99-111. DOI: 10.1007/3-540-60865-6_47
[6] Moriai S., Shimoyama T., Kaneko T. Interpolation attacks of the block cipher: SNAKE. International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 1999. Pp. 275-289. DOI: 10.1007/3-540-48519-8_20
[7] Althaus H., Leake R. Inverse of a finite-field Vandermonde matrix (Corresp.) IEEE Transactions on Information Theory. 1969; 15(1):173-173. DOI: 10.1109/TIT.1969.1054253
[8] Kleibanov S.B., Norkin K.B., Prival'skii V.B. Inversion of the Vandermond matrix. Automation and Remote Control. 1977; 38(4):600-601. Available at: http://mi.mathnet.ru/eng/at7343 (accessed 10.05.2018).
[9] Traub J.F. Associated polynomials and uniform methods for the solution of linear problems. Siam Review. 1966; 8(3):277-301. DOI: 10.1137/1008061
[10] Parker F.D. Inverses of Vandermonde matrices. The American Mathematical Monthly. 1964; 71(4):410-411. DOI: 10.2307/2313246
[11] Björck Ȧ., Pereyra V. Solution of Vandermonde systems of equations. Mathematics of Computation. 1970; 24(112):893-903. DOI: 10.1090/S0025-5718-1970-0290541-1
[12] Gohberg I., Olshevsky V. The fast generalized Parker-Traub algorithm for inversion of Vandermonde and related matrices. Journal of Complexity. 1997; 13(2):208-234. DOI: 10.1006/jcom.1997.0442
[13] Yan S., Yang A. Explicit algorithm to the inverse of Vandermonde matrix. 2009 International Conference on Test and Measurement. Hong Kong, 2009. Pp. 176-179. DOI: 10.1109/ICTM.2009.5413083
[14] Bayev V.V. Some lower bounds on the algebraic immunity of functions given by their trace forms. Problems of Information Transmission. 2008; 44(3):243-265. DOI: 10.1134/S0032946008030071
[15] Kuzmin A.S., Markov V.T., Nechaev A.A., Shishkov A.B. Approximation of Boolean functions by monomial functions. Discrete Mathematics and Applications. 2006; 16(1):7–28. DOII: 10.1515/156939206776241255
[16] Kuzmin A.S., Nozdrunov V.I. Relationship between the coefficients of polynomials over GF(2n) and weights of Boolean functions represented by them. Prikladnaya Diskretnaya Matematika. 2014; 4(26):28-46. Available at: https://elibrary.ru/item.asp?id=22636126 (accessed 10.05.2018). (In Russian)
[17] Carlet C. Boolean Functions for Cryptography and Error-Correcting Codes. Y. Crama, P. Hammer (Eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Encyclopedia of Mathematics and its Applications). Cambridge: Cambridge University Press, 2010. Part III. Pp. 257-397. DOI: 10.1017/CBO9780511780448.011
[18] Feistel H. Cryptography and computer privacy. Scientific American. 1973; 228(5):15-23. DOI: 10.1038/scientificamerican0573-15
[19] Bogdanov A. et al. PRESENT: An Ultra-Lightweight Block Cipher. P. Paillier, I. Verbauwhede (Eds.) Cryptographic Hardware and Embedded Systems – CHES 2007. CHES 2007. Lecture Notes in Computer Science. Vol. 4727. Springer, Berlin, Heidelberg, 2007. Pp. 450-466. DOI: 10.1007/978-3-540-74735-2_31
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
