×

An algorithm for finding the minimum degree of a polynomial over a finite field for a function over a vector space depending on the choice of an irreducible polynomial. (Russian. English summary) Zbl 1466.12001

Summary: The transformations of the vector space of \(p\)-ary vectors of length \(n\), where \(p\) is a prime number, are considered. Each such a transformation is assigned to a polynomial over a finite field \(\text{GF}(p^n)\). The finite field is represented by a residue ring modulo an irreducible polynomial. In general, depending on the choice of the irreducible polynomial, different polynomials over the finite field will correspond to the transformation over the vector space. In this paper, we propose an algorithm for finding the minimal degree of such a polynomial and an irreducible polynomial at which this degree is achieved. The algorithm is based on the calculation of expressions for polynomial coefficients through its values. In the process of the algorithm, the elements of finite fields are treated as polynomials. To compute specific irreducible polynomials, the Euclid algorithm computes the greatest common divisor of these expressions and the polynomial, which is the product of all irreducible polynomials of degree \(n\). To work up to degree \(d\), the algorithm requires storage of \(O(p^nn)\) elements from GF \((p)\) and \(O(p^nn^2d^4w)\) operations of addition and multiplication modulo \(p\) where \(w\) is the number of elements on which the polynomial is nonzero. Thus, the algorithm is especially effective for functions that have many zero values. The minimal degree polynomials for the S-boxes of block ciphers (GOST 28147-89, ICEBERG, LUFFA, LUCIFER, SERPENT, AES, PRESENT, GOST 34.12-2015) as well as the irreducible polynomials at which this degree is achieved have been computed.

MSC:

12-08 Computational methods for problems pertaining to field theory
94C11 Switching theory, applications of Boolean algebras to circuits and networks
94A60 Cryptography

Software:

ICEBERG; Serpent; PRESENT
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] Youssef A. M., Gong G., “On the interpolation attacks on block ciphers”, Intern. Workshop on Fast Software Encryption, Berlin-Heidelberg, 2000, 109-120 · Zbl 0999.94546
[2] Lidl R., Niederreiter H., Finite Fields, v. 20, Cambridge University Press, Cambridge, 1997
[3] McWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, Elsevier, N.Y., 1977
[4] Sorenson J., “An analysis of Lehmer”s Euclidean GCD algorithm”, Proc. Intern. Symp. on Symbolic and Algebraic Computation (Montreal, Canada, 1995), 257-397
[5] Carlet C., “Boolean functions for cryptography and error correcting codes”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, eds. Y. Crama, P. Hammer, Cambridge University Press, Cambridge, 2010, 257-397 · Zbl 1209.94035 · doi:10.1017/CBO9780511780448.011
[6] Jakobsen T., Knudsen L. R., “The interpolation attack on block ciphers”, Intern. Workshop on Fast Software Encryption, Springer, 1997, 28-40 · Zbl 1385.94047 · doi:10.1007/BFb0052332
[7] GOST 28147-89. Information Processing Systems. Cryptographic Protection. Algorithm of Cryptographic Transformation, Standards Publ., M., 1989 (in Russian)
[8] Popov V., Kurepkin I., Leontiev S., RFC 4357: Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 Algorithms, IETF, M., 2006
[9] Standaert F. X., Piret G., Rouvroy G., et al., “ICEBERG: An involutional cipher efficient for block encryption in reconfigurable hardware”, Intern. Workshop on Fast Software Encryption, Berlin-Heidelberg, 2004, 279-298 · Zbl 1079.68563 · doi:10.1007/978-3-540-25937-4_18
[10] De Canniere C., Sato H., Watanabe D., Hash Function Luffa: Specification. Submission to NIST SHA-3 Competition,
[11] Sorkin A., “Lucifer, a cryptographic algorithm”, Cryptologia, 8:1 (1984), 22-42 · doi:10.1080/0161-118491858746
[12] Biham E., Anderson R., Knudsen L., “Serpent: A new block cipher proposal”, Intern. Workshop on Fast Software Encryption, Berlin-Heidelberg, 1998, 222-238 · Zbl 1385.94015 · doi:10.1007/3-540-69710-1_15
[13] Daemen J., Rijmen V., The Design of Rijndael. AES — the Advanced Encryption Standard, Springer Science & Business Media, Berlin-Heidelberg, 2013 · Zbl 1065.94005
[14] Bogdanov A., Knudsen L. R., Leander G., et al., “PRESENT: An ultra-lightweight block cipher”, Intern. Workshop on Cryptographic Hardware and Embedded Systems, Berlin-Heidelberg, 2007, 450-466 · Zbl 1142.94334
[15] Information Technology. Cryptographic Protection of Information. Block Ciphers, Standartinform Publ., M., 2015 (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.