Криптографические свойства простой конструкции S-блока на основе на булевой функции и перестановки | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/13

Криптографические свойства простой конструкции S-блока на основе на булевой функции и перестановки

Предложен метод построения векторных булевых функций с использованием булевых функций и перестановок с целью упрощения построения S-блоков с определенными криптографическими свойствами, такими как высокая нелинейность, сбалансированность, низкая дифференциальная равномерность и высокая алгебраическая степень.

Cryptographic properties of a simple S-box construction based on a Boolean function and a permutation.pdf S-boxes play the crucial role for providing resistance of a block cipher to different types of attacks. The major reason for this is that in classical and modern block ciphers the main complicated and nonlinear layer is presented namely by S-boxes. Mathematically, S-box is a vectorial Boolean function that maps n bits to m bits. Usually, n coincides with m. It is well known that some special mathematical properties of S-boxes, such as high nonlinearity, low differential uniformity, high algebraic immunity, etc. make a cipher with such S-boxes be resistant to linear, differential, algebraic and other methods of cryptanalysis. The cryptographic properties of a Boolean (vectorial) function contradict to each other [1, 2]. That is why we try to find vectorial Boolean functions that reach a tradeoff between different cryptographic properties and are constructed using mathematical methods (and not a direct computer search) for their constructing. In the paper, we propose a simple method of constructing S-boxes using Boolean functions. Let n be an arbitrary permutation on n elements, n G Sn. If x = (x1,... ,xn) is a binary vector, then let n(x) be a vector n(x) = (xn(1),..., xn(n)). Let f be a Boolean П : Fn ^ Fn function in n variables. Define a vectorial Boolean function Fn : Fn -> Fn as follows Fn(x) = (f (x), f (n(x)),f (n2(x)),..., f (nn-1(x))). We would like to study cryptographic properties of the vectorial Boolean function Fn in dependence on properties of the Boolean function f and the permutation n. Note that this way of constructing vectorial Boolean functions was already mentioned before but only for obtaining some examples. Thus, A. Udovenko proposed a vectorial Boolean function of this type in 5 variables with the maximal possible algebraic immunity 3. It is a unique known solution of the previously unsolved problem from NSUCRYPTO 2016 [3]. So functions Fn can have good crypto properties. Separately, we consider the special case of a permutation. Let An be the set of all full cycle permutations for n elements. For example, A4 consists of 6 permutations: (2, 3, 4,1), (2, 4,1, 3), (3,1, 4, 2), (3, 4, 2,1), (4,1, 2, 3), (4, 3,1, 2) presented as vectors or (1234), (1243), (1342), (1324), (1432), (1423) in cyclic representation. Let us recall definitions of several cryptographic properties. A Boolean function f in n variables is called balanced if it takes every value (0 or 1) the same number of times [4]. A vectorial Boolean function F : Fn ^ Fn is balanced if it takes every value of Fn equally often [2] . Let A = |(a,x) ф b : a G Fn,b G F2} be the class of all affine Boolean functions in n variables [5]. The nonlinearity nl(f) of a Boolean function f in n variables is the Hamming distance between f and the set of all affine Boolean functions in n variables [5]. The nonlinearity nl(F) of a vectorial Boolean function F is the minimal nonlinearity of all its component Boolean functions: nl(F)= min nl(Fv)= min d((v,F), A«) = min min d((v,F),g). veFn\\{0} veFn\\{0} veFn\\{0} geAn The algebraic degree of a vectorial Boolean function is the maximal algebraic degree of its component functions [2]. Note that for our construction deg(F) = deg(f) for any n, since all coordinate functions of F have degree deg(f). For a vectorial Boolean function F : Fn ^ Fn let 5F denote the maximal number of solutions for the equation F(x) ф F(x ф a) = b while a, b run through Fn and a is nonzero. Then F is called differential 5F-uniform [2]. Note that the minimal possible value of 5F, where F maps from Fn to Fn, is 2. We consider cryptographic properties of Fn for small n in relation to f and n. All of the following propositions are obtained via computer search. 1. Case n = 2 • For any permutation n G S2 there exists a Boolean function f in 2 variables such that 5Fn = 2. Moreover, such Boolean functions are constructed as f (x) = x1x2фa1x1 фa2x2фa0, where a0, a1, a2 G F2. 2. Case n = 3 For any Boolean function f in 3 variables nl(f) ^ 2. • For any permutation п G A3 there exists a balanced Boolean function f in 3 variables such that vectorial Boolean function Fn is balanced. • For any permutation п G A3 it holds nl(Fn) = nl(f). Note that if nl(Fn) = 2, i.e., is maximal, then 8Fn = 2, i.e., is minimal possible. The number of such funstions f is 48. • For an arbitary permutation п G A3 and Boolean function f in 3 variables 8Fn ^ 4. 3. Case n = 4 Let us introduce the notation for permutations from the set A4: ni = (2, 3, 4,1), п2 = = (4,1, 2, 3), пз = (2, 4,1, 3), П4 = (3,1,4, 2), п = (3,4, 2,1), п = (4, 3,1, 2). Note that n-i = П2, n-i = П4, n-i = Пб. • For any permutation п G A1 and a balanced Boolean function f in 4 variables such that 8Fn = 2, Fn is not balanced. • For any permutation п A41 there exists a Boolean function f in 4 variables such that if 8Fn = 2 and nonlinearity of f and Fn are the same, then 8F _1 = 2. Moreover, nonlinearity of Fn_i and f coincide. • For any permutation п G A4 for an arbitary Boolean function f in 4 variables 8Fn ^ 4. Based on the results, we suppose that it is possible to construct vectorial Boolean functions in the arbitrary number of variables with cryptographic properties good enough using our simple construction for necessary Booleans functions and permutations. We plan to use our program for studying vectorial Boolean functions with larger number of variables, now this work is in progress.

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

Boolean function, vectorial Boolean function, S-box, high nonlinearity, balancedness, low differential 8-uniformity, high algebraic degree, булева функция, векторная булева функция, S-блок, высокая нелинейность, сбалансированность, низкая дифференциальная равномерность, высокая алгебраическая степень

Авторы

ФИООрганизацияДополнительноE-mail
Зюбина Дарья АлександровнаИнститут математики им. С. Л. Соболева СО РАН; Новосибирского государственного университетамладший научный сотрудник; студентка факультета информационных технологий; исследователь лаборатории криптографии JetBrains Researchd.zyubina@g.nsu.ru
Токарева Наталья НиколаевнаИнститут математики им. С. Л. Соболева СО РАН; Новосибирский государственный университеткандидат физико-математических наук, старший научный сотрудник; доцентtokareva@math.nsc.ru
Всего: 2

Ссылки

1. Cusick T. W. and Stanica P. Cryptographic Boolean Functions and Applications. USA, Acad. Press, Elsevier, 2009.
2. Carlet C. Vectorial Boolean functions for cryptography. Y. Crama and P. Hammer (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge, Cambridge University Press, 2010, pp. 398-470.
3. Tokareva N., Gorodilova A., Agievich S., et al. Mathematical methods in solutions of the problems presented at the Third International Students' Olympiad in Cryptography. Prikladnaya Diskretnaya Matematika, 2018, no. 40, pp. 34-58.
4. Carlet C. Boolean functions for cryptography and error-correcting codes. Y. Crama and P. Hammer (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge, Cambridge University Press, 2010, pp. 257-397.
5. Logachev O. A., Salnikov A. A, Smyshlyaev S. V., and Yaschenko V. V. Bulevy funktsii v teorii kodirovaniya i kriptologii [Boolean Functions in Coding Theory and Cryptology]. Moscow, MCCME Publ., 2012. 584p. (in Russian)
 Криптографические свойства простой конструкции S-блока на основе на булевой функции и перестановки | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/13

Криптографические свойства простой конструкции S-блока на основе на булевой функции и перестановки | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/13