Свойства объединенных булевых функций квадратичных функций APN | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/24

Свойства объединенных булевых функций квадратичных функций APN

For a function F : Fn ^ Fn, it is defined the associated Boolean function yf in 2n variables as follows: yf(a, b) = 1 if a = 0 and equation F(ж) + F(x + a) = b has solutions. A vectorial Boolean function F from Fn to Fn is called almost perfect nonlinear (APN) if equation F(ж) + F(ж + a) = b has at most 2 solutions for all vectors a, b Е Fn, where a is nonzero. In case when F is a quadratic APN function its associated function has the form yf(a, b) = (a) · b + (a) + 1 for appropriate functions $F : Fn ^ Fn and : Fn ^ F2. We study properties of functions $F and , in particular their degrees.

Properties of associated Boolean functions of quadratic APN functions.pdf 1. Introduction Let Fn be the n-dimensional vector space over F2. Let 0 denote the zero vector of Fn; x • y - x1y1 + ... + xnyn denote the inner product of vectors x,y G Fn. A set M С Fn form a linear subspace if x + y G M for any x,y G M. Here + denotes the coordinate-wise sum of vectors modulo 2. A mapping f : Fn ^ F2 is a Boolean function of n variables. The Hamming weight of f is the number wt(f) - |{x G Fn : f (x) - 1}|. We consider a vectorial Boolean function F : Fn ^ Fn, F - (f1,..., fn), where f is the i-th coordinate function of F; a function v • F is a component function of F for a nonzero v G Fn. The algebraic 'normal form (ANF) of F is the following unique representation: F (x) - £ a/(n x,), where P (N) is the power set of N - {1,...,n} and each a/ belongs to Fn. The algebraic degree of F is degree of its ANF: deg(F) - max{|11 : a/ - 0, 1 G P(N)}. Functions of algebraic degree 2 are called quadratic. A function F from Fn to itself is called almost perfect nonlinear (APN) (according to K. Nyberg [1]) if for any a, b G Fn, a - 0, equation F(x) + F(x + a) - b has at most 2 solutions. APN functions are of special interest for using as S-boxes in block ciphers due to their optimal differential characteristics. Despite to fact that APN functions are intensively studied (see, for example, survey [2] of M. M. Glukhov), there are a lot of open problems on finding new constructions, classifications, etc. In [3] C. Carlet, P. Charpin, and V. Zinoviev introduced the associated Boolean function YF (a, b) in 2n variables for a given vectorial Boolean function F from Fn to itself. It takes value 1 if a - 0 and equation F(x) + F(x + a) - b has solutions. It is easy to see that F is APN if and only if wt(V) - 22n-1 - 2n-1. Two functions are called differentially equivalent [4] (or y-equivalent according to K. Boura et al. [5]) if their associated functions coincide. The problem of describing the differential equivalence class of an APN function remains open even for quadratic case. That is why we are interested in obtaining some properties of yf . We will focus on quadratic APN functions. Let F be a quadratic APN function. Then yf is of the form yf(a, b) - ФF (a) • b + + (a) + 1, where ФF : Fn ^ Fn, : Fn ^ F2 are uniquely defined from {F(x) + F(x + a) : x G Fn} - {y G Fn : ФF(a) • y - (a)} for all a - 0 and ФF(0) - 0, ^f(0) - 1. 2. Properties of ФF and In this section, we summarize known results and present new ones about properties of ФF and . As it usually happens the cases of even and odd number of variables are different. Property 1: the image set of ФF. Theorem 1 [3, 6]. Let F be a quadratic APN function in n variables. 1) If n is odd, then ФF is a permutation. 2) If n is even, then the preimage ФF of any nonzero vector is a linear subspace of even dimension together with the zero vector. Corollary 1. Let F be a quadratic APN function. Then Ф^ takes an odd number of distinct nonzero values. Property 2: the degree of Ф^. Theorem 2 [4]. Let F be a quadratic APN function in n variables, n ^ 3, n is odd. Then deg^F) < n - 2. Theorem 3. Let F be a quadratic APN function in n variables, n ^ 4, n is even. Then each coordinate function of Ф^ is represented as (Ф^)j(x) = fj(x) + Aj(x2... xn + + xix3 ... xn + ... + xix2 ... xn-i + xi... xn), where deg(fj) < n - 2 and Aj Е F2. Remark 1. For all known quadratic APN functions in not more than 11 variables, we computationally verified that - for even n, the case deg(^F)j) = n is not realized; - any component function of Ф^ has degree exactly n - 2. Based on computational experiments we can formulate the following Hypothesis 1. Let F be a quadratic APN function in n variables, n ^ 3. Then deg(v ■ Ф^) = n - 2 for any nonzero v Е Fn. Property 3: the degree of . Proposition 1. Let F be a quadratic APN function in n variables, n is even. Then deg(^F) = n, or, equivalently, wt(^F) is odd. The case of odd n remains open, but based on our computational experiments we can formulate the following Hypothesis 2. Let F be a quadratic APN function in n variables, n is odd. Then deg(^F) < n, or, equivalently, wt(^F) is even.

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

APN functions, associated Boolean functions, differential equivalence

Авторы

ФИООрганизацияДополнительноE-mail
Городилова Анастасия АлександровнаИнститут математики им. С. Л. Соболева СО РАН; Новосибирский государственный университеткандидат физико-математических наук, научный сотрудник; старший преподавательgorodilova@math.nsc.ru
Всего: 1

Ссылки

Nyberg K. Differentially uniform mappings for cryptography. EUROCRYPT'93, LNCS, 1994, vol. 765, pp. 55-64.
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)
Carlet C., Charpin P., and Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography, 1998, vol.15, iss.2, pp. 125-156.
Gorodilova A. On the differential equivalence of APN functions. Cryptography and Communications, 2019. https://link.springer.com/article/10.1007/ s12095-018-0329-y.
Boura C., Canteaut A., Jean J., and Suder V. Two notions of differential equivalence on S-boxes. Designs, Codes and Cryptography, 2019, vol. 87, iss. 2-3, pp. 185-202.
Gorodilova А. Lineynyy spektr kvadratichnykh APN-funktsiy [The linear spectrum of quadratic APN functions]. Prikladnaya Diskretnaya Matematika, 2016, no4(34), pp. 5-16. (in Russian)
 Свойства объединенных булевых функций квадратичных функций APN | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/24

Свойства объединенных булевых функций квадратичных функций APN | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/24