On the number of symmetric coordinate functions of apn function.pdf Важной частью в конструкции блочных шифров являются векторные булевы функции (S-блоки), которые должны обладать определёнными криптографическими свойствами. Доказанной стойкостью к дифференциальному криптоанализу обладает класс APN-функций - почти совершенно нелинейных функций [1]. В основе данной крипто-атаки лежит анализ пар открытых текстов (P, P') и соответствующих им пар шифр-текстов (C, C'), между которыми существуют разности ДР = P ф P' и AC = C ф C'. Функция F : Fn ^ F^ называется APN-функцией, если для любого а е (F^)* и любого b е Fn уравнение F(x) + F(x + а) = b имеет не более двух решений. В разное время [2] были получены некоторые алгебраические конструкции APN-функций: R. Gold (1968), T. Kasami (1971), H. Dobbertin (1999, 2000), T. Beth и C. Ding (1993), L. Budaghyan, C. Carlet, G. Leander (2008, 2009, 2013) [3], C. Bracken, E. Byrne, N. Markin, G. McGuire (2008, 2011). Исследованию свойств APN-функций посвящено много работ (М. М. Глухов, В. А. Зиновьев, K. Nyberg, C. Carlet, P. Charpin, H. Dobbertin, L. Budaghyan и др.). Тем не менее класс APN-функций до сих пор не описан и мало изучен, поэтому в данной области существует много интересных открытых вопросов, таких, как классификация и оценки количества функций этого класса, поиск конструкций и построение новых APN-функций, в частности взаимно однозначных. В силу сложности описания этого класса естественно рассматривать свойства его наиболее простых представителей, таких, например, как функций с низкой алгебраической степенью, симметрических функции и т. д. Булева функция f от n переменных - симметрическая, если для любой перестановки п е Sn для любых Х1,... , Xn выполнено f (xb ... , xn) f(xn (1), . . . , Xf(n) ). Можно заметить, что значение симметрической булевой функции f (x) зависит только от веса вектора x, следовательно, вектор значений и АНФ такой функции могут быть представлены в более компактном виде, что может быть полезно при аппаратной и программной реализации шифра. 1 Теорема 1. Пусть F - APN-функция от n переменных. Тогда не существует перестановки п е Sn, отличной от тождественной, такой, что F(x) = F(n(x)) для любого x е Fn. Пусть функция F принимает t различных значений yi,... , yt. Определим множество Mi = {x : F(x) = yi}. Заметим, что если F - APN-функция от n переменных и принимает t различных значений yi,... , yt, то множества Mi, i = 1,... , t, не могут все одновременно являться слоями булева куба En. Теорема 2. Пусть F - APN-функция из Fn в F£, F = (fi,... , /n), / - координатные булевы функции. Тогда среди /i,... , /n не более ^(n) симметрических, где a(n)= [n - log2 Cn(n-i)/2jJ . Помимо симметрических булевых функций, интерес в криптографии представляют также функции, которые сохраняют значения на всех циклических сдвигах координат вектора x, т. е. /(xi, x2,..., xn) = /(x2,..., xn, xi) = ... = /(xn, xi,..., xn-i) для любого вектора x из Fn - так называемые rotation symmetric Boolean functions (RotS). Следующее утверждение даёт верхнюю оценку количества координатных RotS-функций у APN-функции. Теорема 3. Пусть F - APN-функция из Fn в F£, F = (/i,..., /n), / - координатные булевы функции. Тогда среди /i,... , /n не более p(n) RotS-функций, где p(n) = Ln - log2 nj. Утверждение 1. Пусть F - APN-функция от n переменных. Тогда: а) F принимает не менее ^(n) различных значений, где . ч 1 + V2n+2 - 7 Mn) = -2-; б) мощность |Mmax| ^ 2n - ^(n) + 1, где Mmax - максимальное по мощности множество M^. Верхняя оценка из утверждения 1, к сожалению, не даёт приближенного значения величины |Mmax| для наиболее распространённых размерностей, однако следующие свойства множеств Mi дают близкие к точным (в некоторых случаях - точные) оценки для малых n. Утверждение 2. Пусть F - APN-функция. Тогда для любого i, для любых попарно различных векторов vr, Vj, v, из Mi верно vr + Vj + v + = 0. В частности, никакое аффинное подпространство L, dim(L) ^ 2, не может быть подмножеством Mi. Из утверждения 2 и свойств линейных пространств следуют оценки размера множества Mmax. Утверждение 3. Пусть F - APN-функция от n переменных, n ^ 9. Тогда мощность |Mmax| не превышает числа £(n), где £(n) имеет следующие значения: n 2 3 4 5 6 7 8 9 £(n) 3 4 6 7 9 11 14 15 На следующих функциях оценка £(n) достигается: n = 2, F =(0 0 0 1); n = 3, F =(0 2 2 2 2 3 6 5); n = 5, F =(0 0 0 1 0 2 4 8 0 3 6 12 7 16 25 23 0 7 3 22 28 19 9 0 19 8 15 28 21 9 29 2). Для следующих функций достижима оценка £(n) - 1: n = 4, F =(0 0 0 1 0 2 4 7 0 4 6 3 8 14 10 13); n = 6, F =(0 0 0 1 0 2 4 7 0 4 6 3 8 14 10 13 0 8 16 25 5 15 17 26 32 44 54 59 45 35 63 48 0 16 26 36 34 48 60 0 45 57 49 11 7 17 31 39 43 28 14 23 12 57 45 54 38 21 5 24 9 56 46 49).

Скачать электронную версию публикации