О вторичной конструкции квадратичных APN-функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/11

О вторичной конструкции квадратичных APN-функций

APN-функции обладают оптимальной устойчивостью к дифференциальному криптоанализу и широко изучаются. Наиболее известные конструкции APN-функций получаются как функции над конечными полями F_ 2^n, и очень мало известно об их комбинаторных конструкциях. Мы предлагаем способ построения квадратичной APN-функции от (n+1) переменных из заданной квадратичной APN-функции от n переменных.

On a secondary construction of quadratic APN functions.pdf Let us recall some definitions. Let Fn be the n-dimensional vector space over F2. A function F from Fn to F^, where n and m are integers, is called a vectorial Boolean function. If m = 1, such a function is called Boolean. Every vectorial Boolean function F can be represented as a set of m coordinate functions F = (fi,...,fm), where f is a Boolean function in n variables. Any vectorial function F can be represented uniquely in its algebraic normal form (ANF): F(x)= E ai(П xi), /ev (n ) ie/ where P(N) is a power set of N = {1,..., n} and a/ G F^. The algebraic degree of a given function F is the degree of its ANF: deg (F) =max{|11 : a/ = 0,1 G P(N)}. If algebraic degree of a function F is not more than 1, then F is called affine. If for an affine function F it holds F(0) = 0, then F is called linear. If algebraic degree of a function F is equal to 2, then F is called quadratic. Two vectorial functions F and G are extended affinely equivalent (EA-equivalent) if F = A1 о G о A2 + A, where A1} A2 are affine permutations on Fn and A is an affine function. Let F be a vectorial Boolean function from Fn to Fn. For vectors a,b E Fn, where a = 0, consider the value S(a,b) = |{x E Fn : F(x + a) + F(x) = b}|. Denote by AF the following value: AF = max 8(a,b). a=0, be Then F is called differentially AF-uniform function. The smaller the parameter AF is, the better the resistance of a cipher containing F as an S-box to differential cryptanalysis. For the vectorial functions from Fn to Fn, the minimal possible value of AF is equal to 2. In this case, the function F is called almost perfect nonlinear (APN). This notion was introduced by K. Nyberg in [1]. APN fuctions draw attention of many researchers, but there is still a significant list (see, for example, [2-4]) of important open questions. We are especially interested how to find new constructions of APN functions in vector space Fn, since almost all the known constructions of this class are found only as polynomials over the finite fields, and to the best of our knowledge, only a few approaches to such combinatorial constructions was proposed [5, 6]. Since EA-equivalence preserves APNness, it is always possible to omit linear and constant terms in the algebraic normal form of a given APN function. Further we will consider quadratic vectorial Boolean functions that have only quadratic terms in their ANF. The following theorem gives a necessary condition on the ANF of a given APN function. Theorem 1 [7]. Let F = (f\\,..., fn) be an APN function in n variables. Then every quadratic term xixj, where i = j, appears at least in one coordinate function of F. This property motivated us to suggest the following construction of quadratic APN functions. Let G = (g1,...,gn) be a quadratic APN-function in n variables. Consider vectorial function F = (f1;..., fn, fn+1) in n +1 variables such that n f1 = g1 + E «1,ixixn+1, i=1 n fn gn + У ] an,ixixn+1j i=1 n fn+1 = gn+1 an+1,ixixn+1 j i=1 where a1,i ...,an+1,i E F2 for i = 1,...,n and gn+1 = E fijk xj xk for some fixed fij,k E F2. Note that if a1,i,..., an,i are such that each term xixn+1 appears at least in one of the coordinate functions f1,..., fn, then the necessary condition of Theorem 1 is held for the constructed function F. Each quadratic vectorial function G in n variables can be considered as a symmetric matrix G = (gij), where each element gij E Fn is a vector of coefficients corresponding to term XiXj in the algebraic normal form of G and all diagonal elements gii are null. It is necessary to mention that these matrices are essentially the same as so-called QAM matrices that were used in [8, 9] to construct and classify a lot of new quadratic APN functions over finite fields. Using these matrices, the APN property can be formulated in the following way: Proposition 1. Let G be the matrix that corresponds to quadratic vectorial function G. Then function G is APN if and only if x (G ■ a) = 0 for all x = a, where a, x е Fn and a = 0. In terms of matrices, the construction (1) can be considered as an extension of a given G with an extra bit that represents gn+i in every element and an extra pair of row and column that represents a set of new terms xixn+i. Consider a quadratic APN function G and the corresponding n x n matrix G. Denote the vector of nonzero coefficients as a = (ai,..., an). Let us fix gn+i and construct (n + 1) x x (n +1) matrix F by adding (ai,... ,an, 0) as the last column and the last row and adding new bit to every element according to the choice of gn+i. Let us denote as G' the submatrix (fij-) of F, such that i, j < n + 1. Let (X) denote the linear span of X and F be the quadratic vectorial function corresponding to the constructed matrix F. Theorem 2. A function F is APN if and only if a ■ a' does not belong to (G' ■ a') for all a' е F!?, a' = 0. Theorem 2 shows how to choose new coefficients ai,i..., an+i,i е F2 in the construction (1) such that an obtained function F is APN. When n = 3, 4 and 5, for APN functions that are representatives of EA classes, all possible classes of quadratic APNs are obtained for 4, 5 and 6 variables from the classification [10] and large variety of classes for constructing functions in 6 and 7 variables.

Ключевые слова

vectorial Boolean function, APN function, quadratic function, secondary construction, векторная булева функция, APN-функция, квадратичная функция


Калгин Константин ВикторовичИнститут вычислительной математики и математической геофизики СО РАН; Институт математики им. С. Л. Соболева СО РАН; Новосибирский государственный университеткандидат физико-математических наук, научный сотрудник; младший научный сотрудник; старший преподаватель кафедры параллельных вычислений ФИТkalginkv@gmail.com
Идрисова Валерия АлександровнаИнститут математики им. С. Л. Соболева СО РАНнаучный сотрудникvvitkup@yandex.ru
Всего: 2


Nyberg K. Differentially uniform mappings for cryptography. EUROCRYPT'93, LNCS, 1994, vol. 765, pp. 55-64.
Carlet C. Open questions on nonlinearity and on APN Functions. WAIFI 2014, LNCS, 2015, vol.9061, pp. 83-107.
Glukhov M. M. O priblizhenii diskretnykh funktsiy lineynymi funktsiyami [On the approximation of discrete functions by linear functions]. Matematicheskie Voprosy Kriptografii, 2016, vol. 7, no. 4, pp. 29-50. (in Russian)
Tuzhilin M. E. Pochti sovershennye nelineynye funktsii [APN-functions]. Prikladnaya Diskretnaya Matematika, 2009, no. 3(5), pp. 14-20. (in Russian)
Gorodilova A. A. Characterization of almost perfect nonlinear functions in terms of subfunctions. Discrete Math. Appl., 2016, vol.26, iss.4, pp. 193-202.
Idrisova V. A. On an algorithm generating 2-to-1 APN functions and its applications to "the big APN problem". Cryptogr. Commun., 2019, no. 11, pp. 21-39.
Beth T. and Ding C. On almost perfect nonlinear permutations. EUROCRYPT'93, LNCS, 1993, vol.765, pp. 65-76.
Yu Y., Wang M., and Li Y. A matrix approach for constructing quadratic APN functions. Des. Codes Cryptogr., 2014, no. 73, pp. 587-600.
Yu Y., Kaleyski N. S., Budaghyan L., and Li Y. Classification of Quadratic APN Functions with Coefficients in GF(2) for Dimensions up to 9. IACR Cryptol. ePrint Arch.: 1491, 2019.
Brinkmann M. and Leander G. On the classification of APN functions up to dimension five. Des. Codes Cryptogr., 2008, vol.49, iss. 1-3, pp. 273-288.
 О вторичной конструкции квадратичных APN-функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/11

О вторичной конструкции квадратичных APN-функций | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/11