Бент-функции, аффинные на подпространствах, и их метрические свойства

• Автор: Коломеец, Николай Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Новосибирск
• Количество страниц: 81 с. : ил.

Оглавление
Введение

1 Аффинность булевых функций

1.1 Определения

1.2 Аффинность булевых функций на подпространстве

1.3 Булевы функции, аффинные на подпространстве и всех его сдвигах

2 Полностью аффинно расщепляемые булевы функции

3 Бент-функции на минимальном расстоянии друг от друга

3.1 Критерий расположения бент-функций на минимальном расстоянии друг от друга

3.2 Индикаторы аффинных подпространств

3.3 Подклассы класса бент-функций
3.3.1 Класс Мэйорана — Мак-Фарланда
3.3.2 Частичное расщепление
3.4 Аффинная эквивалентность бент-функций и минимальное расстояние
4 Бент-функции на минимальном расстоянии от квадратичной бент-функции
4.1 Квадратичные бент-функции
4.2 Аффинность булевой функции на подпространстве
4.3 Представление подпространств
4.4 Построение бент-функций на минимальном расстоянии от квадратичной бент-функции
4.5 Подсчет количества бент-функций на минимальном расстоянии от квадратичной бент-функции
4.6 Примеры для малых размерностей
5 Оценки числа бент-функций на расстоянии 2к от функции из 232*; • •
5.1 Верхняя оценка для произвольной бент-функции
5.2 Нижняя оценка для бент-функций из класса Мэйорана—МакФарланда
Заключение
Литература
А Программное обеспечение для проведения численных экспериментов
А. 1 Двоичные векторы
А.2 Линейные подпространства
А.З Поля Галуа
А.4 Итераторы
А. 5 Представления булевых функций
А.5.1 Вектор значений
А.5.2 Алгебраическая нормальная форма
А.5.3 Трейс-форма
А.6 Бент-функции

Введение
Работа посвящена исследованию важного класса булевых функций, обладающих максимальной нелинейностью. Это класс бент-функций. Бент-функции интересны не только из-за экстремального значения нелинейности, но и из-за большого числа приложений в криптографии, теории кодирования, алгебре, теории символьных последовательностей.
Приведем необходимые определения.
Функция вида / : называется булевой функцией от п переменных,
х Є Щ — двоичным вектором длины п, х — {хі,, хп)2. Через Тп обозначим множество всех булевых функций от п переменных. Для х,у определим
х (В у = [х © г/і,..., хп ф уп)Т, где ® — сложение по молулю 2. Введём аналог скалярного произведения по модулю 2:
{X, у) = ХУ 0 Х2У2 0 ... 0 Хпуп.
Отметим, что {х, у) не является скалярным произведением в полном смысле этого понятия, поскольку нс все свойства скалярного произведения верны в двоичном случае.
Аффинной булевой функцией от п переменных называется функция вида
£а,с(х) = (а> Х) 0 С ДЛЯ некоторых а Є Т>2, сє22'
Через Лп обозначается множество всех аффинных функций от п переменных. Расстоянием Хэмминга между двумя двоичными векторами х,у Є 2^' называется число координат, в которых х и у различаются. Расстоянием между двумя булевыми функциями /, д є Тп называется расстояние Хэмминга между векторами их значений, оно обозначается как бів^/, у). Булевы функции /, д Є Тп называются аффинно эквивалентными, если существует невырожденная двоичная матрица А размера п х п, вектор Ь Є ТЦ и аффинная функция £ Є Лп, такие что
/(а) = д(Ах 0 Ь) 0 £(х) для всех х Є

Данное утверждение является следствием теоремы Диксона, его также можно в работе Дж. Диллона [50].
Утверждение 7 (О. Ротхаус [77], Дж. Диллон [49], Б. Пренель [72]). Каждая бент-функция от 6 переменных аффинно эквивалентна одной из следующих функций:
1. Jf = хгх2 0 х3х4 0 х5х6;
2. /| = ххх2хг ф ххх± 0 х2х5 © х3х6;
3. /| = Х1Х2Х3 0 Ж2Ж4Ж5 0 Х±Х2 © Х1Х4 © Х2Х6 0 Ж3Ж5 0 Ж4Ж5;
4. /| = Ж1Ж2а:з 0Д2^4Ж5 0ЖзЗ:4Хб 0^1^4 0^2^6 0 Ж3Х4 0ЖзЖ5© ХзХб0Ж4Х50Ж4Жб-
Утверждение 8 (А. Брэкен [32], К. Д. Хоу [60]). Каждая бент-функция от 8 переменных степени не больше 3 аффинно эквивалентна одной из следующих функций:
1. Д8 = Х1Х2 0 Х3Х4 0 Х5Х6 0 х7х8;
2. /| = Х1Х2Х3 0 Х1Х4 © х2х5 0 х3Хб 0 х7ж8;
3. /| = Х!Х2х3 © х2х4х5 0 х3х4 0 х2х6 © ХХ7 0 х5х8;
4. /| = Х1Х2х3 0 Х2Х4Х5 0 Х1Х3 © Х1Х5 0 х2х6 0 Х3Х4 0 ж7ж8;
5. /| = Х1Х2Х3 0 х2х4х5 © х3х4х6 0 х3х5 © х2х6 © х2х5 © Ж1Х7 © х4х8;
6. /I = Ж1Ж2Ж3 0 х2х4х5 0 х3х4х6 © Ж3Х5 0 Х4Ж3 0 Х4Х4 ф х2х7 0 х6х8;
7. /8 = Х1Х2Х3 ©Х2Х4Х5 0Х3Х4Х6 0ХзХ5©Х2Х60Х2Х5 0X1X2 0X1X3 ©Х1Х4©Х7Х8; 8- /| = Хх2х3 0 Х2Ж4Х5 0 хзх4х6 0 Ж3Ж5 0 Х1Х6 0 х2х7 © х4х8;
9. /| = ж1ж2ж7 0 Х3Х4Х7 0 ХбХех7 © Ж1Х4 0 х3хб 0 х2Х5 © Х4Ж5 0 х7х8;
10. /80 = Х1Х2Х3 0 Ж2Ж4Ж5 0 Х3Х4Х6 © Ж1Х4Х7 © Ж3Х5 0 х2х7 0 Ж1Ж5 ф Х1Х6 © Х4Х8.
Отметим, что все бент-функции из предыдущих утверждений об аффинной классификации являются аффинно эквивалентными функциям из класса Мэйорана—МакФарланда (см. [32]). Об аффинной классификации булевых функций от 6, 7 и 8 переменных см. также работу А. В. Черемушкина [29] 2001 г.
Так как класс 532/с замкнут относительно отрицания функции, то из формулы пбп},деъ2к'1/д <Н81(/, д) = 2к следует