Lower bound for the number of bent functions at the minimum distance from Majorana - McFarland bent functions.pdf Введение Пусть Fn - линейное пространство над полем F2, состоящее из двоичных векторов размерности п. Множество всех булевых функций от п переменных f : Fn F2 обозначим через Fn. Расстоянием dist(f, g) между двумя булевыми функциями f, g G Fn называется число позиций, в которых векторы значений этих функций различаются. Булева функция от чётного числа переменных 2n, расстояние от которой до множества всех аффинных функций максимально и равно 22n-1 - 2n-1, называется бент-функцией. Везде далее будем рассматривать бент-функции от 2n переменных. Обозначим множество всех бент-функций от 2n переменных через B2n. Класс бент-функций Мэйорана - МакФарланда M2n состоит из функций вида f (x,y) = (х,п(У)) ф р(у), где р G Fn и п - перестановка на Fn. Напомним, что функции f, g G Fn называются EA-эквивалентными^ если существуют аффинная функция h, невырожденная матрица A размера п х п с элементами из F2 и b G Fn, такие, что f (x) = g(xA ф b) ф h(x) для всех x G F2n. Через индикатор IndS обозначим характеристическую функцию множества S С F2n. Бент-функции введены О. Ротхаусом в [1]. Они интересны как своими экстремальными значениями нелинейности, так и приложениями в криптографии, теории кодирования, теории символьных последовательностей. Однако есть много открытых вопросов об устройстве множества всех бент-функций, о соотнесении различных известных классов бент-функций. Например, классы C и D, введённые в [2], лежат вне замыкания класса M2n относительно EA-эквивалентности. Но это известно благодаря построенным примерам [2, 3] и непонятно, какая часть бент-функций из C и D лежит вне замыкания M2n. Для построения бент-функции на некотором расстоянии от исходной бент-функции f G B2n можно воспользоваться универсальной конструкцией f f ф Inds. При этом часто удобно рассматривать не произвольное множество S С F22n, а, например, некоторое подпространство U. Так, в работе [2] для случая, когда U - аффинное подпространство F2n размерности п, доказано, что f ф IndU - бент-функция. Для двух различных f,g G B2n известно, что dist(f,g) > 2n. В [4] показано, что все бент-функции на минимально возможном расстоянии 2n от заданной бент-функции f могут быть выражены как f фIndU, где U - аффинное подпространство F2n, dim U = п. Иными словами, в поиске всех бент-функций на расстоянии 2n достаточно ограничиться прибавлением индикатора аффинного подпространства размерности п. В [5] приведён вид всех бент-функций из M2n, лежащих на расстоянии 2n от исходной бент-функции из M2n. Число таких бент-функций может быть использовано в качестве следующей оценки. Утверждение 1 (Н. Коломеец, 2017). Число всех бент-функций на минимальном расстоянии от бент-функций из M2n можно оценить снизу как 22n+1-2n. При этом все бент-функции, учитывающиеся в этой оценке, также лежат в классе M2n. 1. Число бент-функций на минимально возможном расстоянии 2n от бент-функций из M2n Рассмотрим f G M2n и конструкцию f f ф IndU, где U - аффинное подпространство F22n, dim U = п. Сначала построим критерий того, что f ф IndU является бент-функцией. Пусть E - линейное подпространство Fn размерности k. Тогда для E существует единственная GJB-матрица M - приведённая ступенчатая матрица полного ранга размера k х п, строки которой составляют базис E. Через (M) обозначим линейную оболочку строк матрицы M. В следующей теореме приведён критерий для функций f (x,y) = (y,n(x)) ф ^(x), другими словами, f G/ M2n, а h(x, y) = f(y, x) G M2n. Такой переход нужен для удобного представления базисов подпространств с помощью GJB-матриц. Критерий для бент-функций из M2n является следствием этой теоремы. Теорема 1. Пусть f (x,y) = (y,n(x)) ф ^(x), такая, что h(x,y) = f (y,x) G M2n; U = (a, b) ф E - аффинное подпространство F2n, dim U = n, где a, b G Fn; линейное подпространство E имеет GJB-матрицу вида где L является GJB-матрицей размера (п - k) х п. Тогда g(x y) = (у, n(x))ф

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