On derivatives of boolean bent functions.pdf Пусть (x.y) -скалярное произведение двоичных векторов по модулю 2. Функция f : Zn Z2 называется булевой функцией от n переменных. Булева функция от чётного числа переменных называется бент-функцией, если она максимально нелинейна [1]. Обозначим через Bn множество бент-функций от n переменных. Шифры, в которых применяются бент-функции, более устойчивы к линейному криптоанализу [2], потому что бент-функции крайне плохо аппроксимируются аффинными функциями. Бент-функции используются в структуре блочного шифра CAST как координатные функции S-блоков [3], а также для построения регистра сдвига с нелинейной обратной связью в поточном шифре Grain [4]; они связаны также с некоторыми объектами теории кодирования, например с кодами Рида - Маллера [5]. Другое определение бент-функции - булева функция f (x) от n переменных (n чётно), такая, что для любого ненулевого вектора у её производная Dyf (x) = f (x)®f (хфу) сбалансирована - принимает значения 0 и 1 одинаково часто [5]. Справедливо ли, что любая сбалансированная функция - производная некоторой бент-функции? В [6] показано, что любая сбалансированная функция g от n С 6 переменных степени не выше n/2 - 1, такая, что g(x) = g(x ф y) для всех x при некотором y, является производной некоторой бент-функции от n переменных. В данной работе эта задача рассмотрена для частного случая сбалансированье функций - аффинных: £a,b(x) = (a.x) ф b, где a G Zn - ненулевой вектор и b G Z2. Теорема 1. Любая неконстантная аффинная функция £a,b(x) от n 4 (n чётно) переменных является производной для (2n-1 - 1)|Bn-2|7 бент-функций. Лемма 1. Для любой бент-функции g и любых y = y' справедливо: Dyg(x) = = Dy/g(x). Лемма 2. Пусть Dyg(x) = la,b(x) для бент-фукции g(x). Тогда при любом y' Dy/g(x) = la,b(x) ф 1. Теорема 1 вместе с леммами 1 и 2 даёт итерационные нижние границы для количества бент-функций от n + 2 переменных (теорема 2). Теорема 2. Для любого чётного n 4 верно |Bn+2| > (2n+2 - 2)|Bn|2. Данная граница хуже представленной в [7], но она, вероятно, может быть улучшена, если рассматривать больше одной аффинной функции или учитывать функции, которые не имеют аффинных производных. Однако задача выделения бент-функций, которые имеют производную ф,ь и не имеют £с^, является непростой. Бент-функции, которые не имеют аффинных произодных, рассмотрены, например, в [8].

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