Constructing the classes of boolean functions with guaranteed cryptographic properties on the base of coordinate functio.pdf Пусть F2 - поле из двух элементов с единицей e; F2n - его расширение натуральнойn-ь_1 r\t-k степени n; trn (a) = Е a 2 -функция след из поля F2n в его подполе F2t для нату-t k=0рального t, такого, что t|n; ||t||2 -двоичный вес числа t Е N; Fn - множество отображенийполя F2n в поле F2; Bn - множество булевых функций от n переменных.Фиксация базиса векторного пространства (F2n )f устанавливает взаимнооднозначноесоответствие между множествами Bn и Fn. Это позволяет при изучении свойствбулевых функций рассматривать их представления отображениями из множества Fn.При получении результатов в работе использовано приведенное представление булевыхфункций от n переменных многочленами над полем F2n, принимающими значенияв поле F2. В связи с этим предполагается знакомство читателя с работами [1, 2].Для элемента a Е F2n и преобразования Ф поля F2n через Sl$) обозначим отображение,задаваемое равенством Sl$) (х) = trn ^Ф (х)). Заметим, что Sl$) (х) есть линейнаякомбинация координатных функций преобразования Ф.В работе для отображений из множества Fn рассматриваются классы приближенийвида Sl#) (х) + trn (вх), где a, в Е F2n; Ф (х) - некоторое преобразование поля F2n. Полученыусловия на вид преобразования Ф, при выполнении которых построенные классыприближают отображения из множества Fn точнее класса отображений, соответствующихаффинным функциям. Описаны множества показателей степени d монома,задающего преобразование Ф (х) = хй, при которых Ф удовлетворяет этим условиям.В качестве показателя близости отображений F, G Е Fn будем использовать величинуА (F, G) = Е (-1)F(x)+G(x). Если отображение G соответствует линейной буле-x€F2nвой функции, то А (F, G) есть коэффициент Уолша - Адамара функции F [3]. Известно[4], что для любого отображения F Е Fn существует отображение L Е Fn, соответствующеелинейной булевой функции, такое, что |А (F, G)| ^ 2n.Теорема 1. Пусть n - натуральное число, большее двух, Ф (х) Е F2n [х]. Если выполненоодно из условий:а) Ф (х) -редуцированный многочлен, такой, что ind Ф (х) > n/2;б) Ф (х) - подстановочный многочлен [5] над полем F2n, Ф (х) - многочлен над F2n,такой, что для любого х Е F2n выполнено Ф (Ф (х)) = х и индекс нелинейностиредуцированного многочлена приведенного представления функции S,^ большеn /2;в) существуют элементы t1,t2 Е F2n\ {0}, такие, что мощность множестваX = {х Е F2n : Ф (х) + Ф (х + t1) Е {0, t2} } не кратна четырем,то для любой функции F Е Fn выполняется неравенствоmax { | А (F, S ^ + trn (вх)) | : a, в Е F2n } > 2n.Следствие. Пусть n, d - натуральные числа, такие, что n>2, dn/2.Тогда для любой функции F Е F n выполняется неравенствоmax {|Д (F, trn (axd) + trn (ex)) | : а, в Е F2n} > 2n.З а м е ч а н и е . Зафиксируем натуральное n. В качестве примера показателя d,удовлетворяющего условию следствия, можно привести число 2* - 1, где t > n/2. Еслитребуется, чтобы моном x d задавал подстановку на F2n, то t необходимо выбратьвзаимно простым с n. Таким условиям при n > 2 удовлетворяет t, равное n - 1.Теоретический и практический интерес представляют задачи количественной оценкидля натурального n, d Е 1, 2n - 1 и функции F Е Fn величиныmax { | Д (F, trn (axd) + trn (ex)) | : а, в Е F2n }как для всех функций из Fn, так и для отдельных классов таких функций, напримербент-функций [4]. Рассмотрим способ построения бент-функций с помощью координатныхфункций степенных преобразований поля F2n и продемонстрируем эффективностьаппроксимации построенных функций приближениями из рассмотренных классов.Теорема 2. Пусть натуральные числа n и s четны, n/2 нечетно и (n,s) = 2. Положимd = 1 + 2s и выберем натуральное число а таким, что ad = 1 (mod 2n - 1).Пусть значения функции Fa,b Е Fn для! любого элемента x Е F2n определены равенствомFa,b (x) = trn (bCTx) trn (ax) + trn (bxd) , а элементы a, b Е F2n\ {0 } таковы, чтоtrn (ab-CT) = e. Тогда:a) Fa,b является бент-функцией;b) max { | Д (Fa,b (x) , trn (c1 xd ) + trn (c2x)) | : c1, c2 Е F2n, d1 Е 1, 2n - 2} ^ 2n-1.

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