Property of Kasami bent functions multiple derivatives.pdf Одно из криптографических свойств булевой функции - это высокая нелиней-ность. Булевы функции, обладающие экстремальной нелинейностью, при чётном чис-ле переменных называются бент-функциями. Описание класса всех бент-функцийот произвольного числа переменных остается открытой проблемой, однако известнынекоторые конструкции бент-функций [1]. Одна из них - алгебраическая конструк-ция Касами. Булева функция от n переменных рассматривается как функция надконечным полем GF(2n). Любая булева функция f от n переменных может быть пред-ставлена с помощью функции следа tr(e) : GF(2n) ^ GF(2) следующим образом (см.подробнее [2]):2 n - 1 n-1f (в) = t r ( E а, в ' ) , где а, G GF(2n), а tr(^) = Е в 2 ' для любого в G GF(2n).j = 0 i=0Определение 1. Булева функция от n переменных (n чётное) вида f (в) == ^(Авк ) называется булевой функцией Касами, если выполнено условие1) k = 22d - 2d + 1, где (n, d) = 1, 0 < d < n.Если к тому же выполнено условие2) А не принадлежит множеству {73 : 7 G GF(2n) },то f является бент-функцией и называется бент-функцией Касами.Исследование выполнено при поддержке гранта РФФИ, проект №11-01-00997.В работе [3] показано, что при выполнении условия 2 функция Касами являетсябент, однако впервые (при ограничении, что число переменных n не делится на три)это доказано в работе Дж. Диллона и Х. Доббертина в 2004 г. [4]. Бент-функции Ка-сами являются наиболее сложными из мономиальных конструкций (т. е. конструкцийвида f (в) = tr(A,ek)). Степень функции Касами от n переменных может приниматьвсе возможные чётные значения вплоть до n/2 (заметим, что максимальная степеньбент-функции от n переменных равна n/2). Известно, что они не аффинно эквива-лентны своим дуальным функциям и бент-функциям из классов PS и Майорана -МакФарланда. Кроме того, известно, что в классе бент-функций Касами существу-ют функции, не являющиеся нормальными, т. е. тождественно равными константе нанекотором аффинном подпространстве размерности n/2.Однако до сих пор не известна связь между алгебраическим и комбинаторнымпредставлениями бент-функций. В данной работе исследуются комбинаторные свой-ства бент-функций Касами. Получен результат о кратных производных функций Ка-сами, следствием которого является свойство зависимости алгебраической нормальнойформы (АНФ) функции от произведений переменных.Будем рассматривать конечное поле GF(2n) как векторное пространство размер-ности n.Определение 2. Производная по направлению a . GF(2n) булевой функции fопределяется как Da f (в) = f (в) + f (в + а) для любого в . GF(2n).Авторами [5] исследована вторая производная бент-функций Касами и доказанатеорема о том, что для любых ненулевых различных направлений a, b . GF(2n) произ-водная DaDbf бент-функции Касами не равна тождественно нулю при степени функ-ции deg(f) ^ 4 и числе переменных n ^ 8.В данной работе доказана следующаяТеорема 1. Пусть f (в) -булева функция Касами от n переменных вида f (в) == ^(Ав^1), где k = 22d - 2d + 1, 0 < d < n, n чётное. Тогда для любого n ^ 8 справедливыследующие утверждения:(i) при deg(f) = t, где 4 ^ t ^ n/2, производная Da i . . . D a t - 3 f (в) не равна тожде-ственно нулю для любых линейно независимых векторов а1 , . . . , a t - 3 . GF(2n);(ii) при deg(f) = t, где 4 ^ t ^ (n + 3)/3, производная Da i . . . Da t - 2 f (в) не равнатождественно нулю для любых линейно независимых векторов а 1 , . . . , a t - 2 . GF(2n).Вводится следующее понятие.Определение 3. Булева функция называется k-существенно зависимой, еслидля любого произведения из k различных переменных существует моном в АНФ функ-ции, содержащий это произведение.Заметим, что булева функция f является k-существенно зависимой, если для лю-бых различных векторов a1 , . . . , ak . GF(2n) вида ai = (0,... , 0,1, 0 , . . . , 0), содер-жащих 1 в координате Si, где 0 ^ si ^ (n - 1), 1 ^ i ^ k, кратная производнаяDa i . . . Dafc f (в) не равна тождественно нулю.Следствием результата в [5] и теоремы 1 является следующаяТеорема 2. Пусть f (в) -булева функция Касами от n переменных вида f (в) == ^(Ав^1), где k = 22d - 2d + 1, 0 < d < n, n чётное. Тогда для любого n ^ 8 справедливыследующие утверждения:(i) при deg(f) ^ 4 функция f является 2-существенно зависимой;(ii) при deg(f) = t, где 4 ^ t ^ n/2, функция f является (t - 3)-существеннозависимой;(iii) при deg(f) = t, где 4 ^ t ^ (n + 3)/3, функция f является (t - 2)-существеннозависимой.Заметим, что если функция обладает свойством k-существенной зависимости, тоона также является /-существенной зависимой для всех l < k. В силу этого интересенвопрос о максимально возможном k, для которого функция является k-существеннозависимой. По результатам непосредственного исследования функций Касами от ма-лого числа переменных (до 14) и теоремы 2 сформулирована следующаяГипотеза 1. Функция Касами степени t при числе переменных n ^ 8, где t ^ n/2,обладает свойством (t - 2)-существенной зависимости, но не обладает свойством (t - 1)-существенной зависимости.Нетрудно заметить, что для доказательства гипотезы остаётся рассмотреть одинслучай, т. е. доказать, что при ( n + 3 ) / 3 ^ t ^ n / 2 функция является (t-2)-существеннозависимой.

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