A bent function construction by a bent function that is affine on several cosets of a linear subspace.pdf Отображение вида f : Fn ^ F2 называется булевой функцией от n переменных, функция Daf(x) = f(x) ф f (x ф a) -её производная по направлению a Е Fn. Носитель функции f определяется как supp(f) = {x Е Fn : f(x) = 1}. Пусть (w,x) = w1x1 ф ... ф wnxn, где w,x Е Fn. Обозначим через IndS характеристическую булеву функцию множества S С Fn. Бент-функцией называется булева функция, производные которой по всем ненулевым направлениям уравновешены (принимают значения 0 и 1 на одинаковом числе аргументов), это возможно только при чётном числе переменных. Бент-функции предложены О. Ротхаусом [1]. Они имеют приложения в алгебре, комбинаторике, теории кодирования, криптографии [2, 3]. Обозначим через B2fc множество всех бент-функций от 2k переменных. В работе исследуются свойства приведённой в следующей теореме конструкции, порождающей бент-функции путём изменения некоторой имеющейся бент-функции. Теорема 1. Пусть f Е B2k и для некоторого w Е F2k бент-функция f (x) ф (w,x) постоянна на каждом из 22k-2t различных смежных классов a1 ф L,... , a22k-2t ф L некоторого линейного подпространства L С F^ размерности t, где 0 ^ t ^ k. Тогда функция f ф Ind(aieL)U...U(a22k_2t®L) (1) также является бент-функцией. Замечание 1. Конструкция (1) при t = k становится конструкцией, предложенной К. Карле [4] и порождающей все бент-функции на расстоянии 2k от f (это минимальное возможное расстояние Хэмминга между двумя бент-функциями) [5]. Замечание 2. В случае t Е {0,1} конструкция (1) тривиальна и даёт сходный результат для любой бент-функции f: при t = 0 можно получить только функцию f ф 1, а при t =1 порождается в точности семейство функций {f (x ф a) ф c : a Е F2k\{0}, c Е F2}. Замечание 3. Требуемый для конструкции (1) набор смежных классов размерности t всегда найдётся, если бент-функция представлена в виде линейного разветвления с индексом линейности не меньше t [6] или принадлежит классу Мэйорана - МакФарланда [7]. Заметим также, что при разных t конструкция порождает различные бент-функции. При t = 2 теорему 1 можно переформулировать следующим образом. Следствие 1. Пусть f Е B2k и для произвольных u, v Е F^, u = v, и c, d Е F2 U = supp(c ф Duf) П supp(d ф Dvf). Тогда при U С supp(1 ф DMDv f) функция f ф Ind^ является бент-функцией. Для квадратичной бент-функции f множество U = (а1 ф L) U ... U (a22k-2t ф L) всегда является аффинным подпространством. Заметим, что общий подход к получению бент-функций инверсией значений исходной бент-функции на аффинном подпространстве можно найти в [4]. Опишем функции, порождаемые конструкцией (1) из квадратичной бент-функции. Теорема 2. Пусть квадратичная бент-функция f Е B2k постоянна на некотором смежном классе линейного подпространства L С F^ с базисом b1,... , bt Е F2k. Тогда t для U = П supp(Dbif ф сг) при произвольных c1,... , ct Е F2 функция f фIndU является г=1 бент-функцией, а U - аффинным подпространством F2k размерности 2k - t. В силу замечания 1 конструкция (1) является обобщением конструкции бент-функ-ций на расстоянии 2k от заданной бент-функции. Обобщим также некоторые результаты, касающиеся бент-функций, располагающихся на минимально возможном расстоянии друг от друга. Теорема 3. Для произвольной f Е B2k конструкция (1) порождает не более чем t-1 22k-2г _ 1 2t П ^- 11 Ot-г 1 г=0 2 - 1 бент-функций (для фиксированного t). При t ^ 2 оценка достигается, если и только если f является квадратичной бент-функцией.

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