Сильно нелинейные булевы функции: бент-функции и их обобщения

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

Оглавление
Введение
1 Бент-функции и их обобщения
1.1 Определения и обозначения
1.2 Конструкции и свойства
1.3 О числе бент-функций и двоичных кодов
1.4 Обобщения бент-функций
1.4.1 Платовидные функции
1.4.2 Частично бент-функции
1.4.3 Частично определенные бент-функции
1.4.4 1.4.5 Обобщенные булевы бент-функции
1.4.6 Полу-бент-функции (semi-bent functions)
1.4.7 Ненормальные бент-функции (nonnormal bent functions)
1.4.8 Бент-функции на конечной абелевой группе
1.4.9 Однородные бент-функции (homogeneous bent functions)
1.4.10 Гипер-бент-функции (hyper-bent functions)
1.4.11 Z-бент-функции
1.4.12 Нега-бент-функции, бент-функции, I-бент-функции
1.5 Векторные бент-функции
1.6 Другие направления
2 Понятие fc-бент-функции
2.1 Определения и обозначения
2.2 Коды с параметрами кодов Адамара
2.3 Бинарная операция (u, v)а,
2.4 Понятие /с-аффиниой функции

2.5 Понятие fc-бент-функции
3 Построение Æ-бент-функций и их свойства
3.1 fc-Бент-функции от малого числа переменных
3.1.1 Описание
3.1.2 Замечания
3.2 Индуктивный способ построения А;-бент-функций
3.3 Взаимосвязь fc-бент-функций с бент-функциями
4 Квадратичные аппроксимации в блочных шифрах
4.1 Линейный криптоанализ и его модификации
4.1.1 Линейный криптоанализ
4.1.2 Проблемы нелинейного криптоанализа
4.1.3 Квадратичный криптоанализ
4.2 Класс аппроксимирующих функций Ат
4.3 Квадратичные аппроксимации в блочных шифрах
4.4 Анализ четырехразрядных подстановок в S-блоках алгоритмов ГОСТ, DES, s3DES
4.5 Замечания и дополнения
4.6 Приложение
5 Приложение. Доказательство Теоремы
5.1 Равномерно упакованные коды
5.2 Три леммы
5.3 Верхняя оценка
Заключение
Благодарности
Список литературы
Предметный указатель

Введение
Bent functions deserve our bent to study them
Работа относится к такой области дискретной математики, как булевы функции и их приложения в комбинаторике, теории кодирования и криптографии. Исследуется важный класс булевых функций, обладающих сильными свойствами нелинейности: бент-функции и их обобщения.
Мера нелинейности является важной характеристикой булевой функ- . ции. Линейность и близкие к ней свойства часто свидетельствуют о простой (в определенном смысле) структуре этой функции и, как правило, представляют собой богатый источник информации о многих других ее свойствах. Задача построения булевых функций, обладающих нелинейными свойствами, естественным образом возникает во многих областях дискретной математики. И часто (что является типичной ситуацией в ма- t тематике) наибольший интерес вызывают те функции, для которых эти свойства экстремальны. Такие булевы функции называются максимально-нелинейными (или бент-) функциями2.
Приведем ряд определений.
Пусть и = (щ
(u, v) = U]Vi ф ... 0 umvm,
где ф означает сложение над Булевой функцией от т переменных называется произвольная функция из в Ъч- Булева функция / от переменных Vi
/(v) = (u, v) Ф а
хИгра слов: «Бент-функции заслуживают нашего стремления изучить их...» (англ.)
2В литературе встречается также термин совершенно нелинейные функции.

ют, равно двум1, и это — APN функции. Дифференциально 4-равномерные функции (см., например [41]) используются в S-блоках симметричного алгоритма блочного шифрования AES (или Rijndael), являющегося с 26 мая 2002 года американским стандартом шифрования.
АВ, APN, 5-равномерные функции и вопросы их эквивалентности широко исследуются. В частности [43], уже выдвинута гипотеза, что все степенные АВ и APN функции найдены (X. Доббертин, 1999, [74]) и обозначена проблема существования новых комбинаторных конструкций таких функций, см. подробнее [53, 42]. При т 25 для APN функций и при m < 33 для АВ функций гипотеза Доббертина уже подтвердилась [75, 98].
За пределами данного обзора, к сожалению, остались скрюченные функции (crooked functions) — специальный подкласс APN функций, введенный в 1998 году Т. Бендингом и Д. Г. Фон-дер-Флаассом [32]. С помощью таких функций оказалось возможно строить новые дистанционно регулярные графы, симметричные схемы отношений, и равномерно упакованные коды типа БЧХ и Препараты, [67, 68], см. также на эту тему работу [45].
1.6 Другие направления
В настоящем обзоре мы не коснулись очень многих тем, прямо или косвенно относящихся к теории бент-функций. Среди них:
/ группы автоморфизмов бент-функций;
/ представления бент-функций с помощью строго регулярных графов; / криптографические свойства смежных классов кода Рида—Маллера первого порядка и их связь с нелинейными булевыми функциями [46];
/ бент-функции, дуальные к данным (а также вопросы самодуальности [55] и эквивалентности бент-функций [96]);
/ корреляционно-иммунные (correlation-immune), устойчивые (resilient) и др. функции, см. на эти темы работы [128, 131, 78, 12] и др.;
/ обобщение: профиль нелинейности булевой функции [51];
S асимптотическая нелинейность булевых функций [120];
/ корреляционные свойства бент-функций [137];
•/ почти бент-функции (near bent) и их сужения на гиперплоскости [72].
1Интересно, что при рассмотрении -значных векторных функций, дф 2, возможно и (5=1.