Эффективные алгоритмы получения оценок алгебраической иммунности булевых функций

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

Основные результаты диссертации
Глава 1. Алгоритмические вопросы поиска аннигиляторов булевых
функций
1.1 Поиск аннигиляторов для различных способов представления
булевой функции
1.1.1 Для представления функции в виде многочлена Жегалкина
1.1.1.1 Алгоритм АМ1 поиска базиса пространства аннигиляторов
1.1.1.2 Явный вид системы уравнений, задающей аннигиляторы
1.1.1.3 Алгоритм АМ 1Б поиска статических соотношений для быстрых алгебраических атак
1.1.1.4 Один способ улучшения алгоритма АМ 1 — алгоритм
АМ12
1.1.2 Для представления функции в виде ДНФ
1.1.3 Для представления функции в виде формулы или схемы из
функциональных элементов
1.1.3.1 Алгоритмы АФ1 и АС1 поиска аннигиляторов
1.1.3.2 Дополнение: О линейных аннигиляторах произведения булевых функций
1.1.3.3 Дополнение: Структура пространства аннигиляторов для булевых функций с фиктивными переменными
1.1.4 Для представления функции в виде трэйс представления
1.1.4.1 Алгоритм АТ 1 поиска базиса пространства аннигиляторов
1.1.4.2 Алгоритм АТ1Б поиска статических соотношений для быстрых алгебраических атак
1.1.4.3 Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции
1.1.4.4 Алгебраическая иммунность фильтрующей функции генератора
1.1.5 О поиске аннигиляторов для частично определённых
функций

1.2 Алгоритмы проверки отсутствия ненулевых аннигиляторов
1.2.1 Проверка отсутствия ненулевых аннигиляторов низкой
степени у многочлена Жегалкина
1.2.1.1 Основной вариант алгоритма АМ2
1.2.1.2 Возможные пути модификации алгоритма АМ2
1.2.2 Проверка отсутствия ненулевых аннигиляторов низкой
степени у ДНФ
Глава 2. Нижние и верхние оценки алгебраической иммунности
булевых функций, заданных трэйс представлением
2.1 Алгебраическая иммунность линейных функций от инверсии
2.2 Нижние оценки алгебраической иммунности более широких
классов функций
2.3 Верхние оценки алгебраической иммунности более широких
классов функций
Глава 3. Исследование метода быстрых алгебраических атак (БАА)
3.1 Предварительные сведения
3.2 Полиномиальный алгоритм получения тождеств для метода БАА
по трэйс представлению функции
3.3 Полиномиальный алгоритм получения нелинейных рекуррентных соотношений для фильтрующего генератора по
трэйс представлению фильтрующей функции
3.4 Явное выражение для минимальной линейной комбинации
предварительного шага метода БАА
Список литературы

В теории конечных автоматов, теории кодирования и криптологии возникают задачи изучения и решения систем булевых уравнений. Как известно, задача решения произвольной системы полиномиальных булевых уравнений является №-трудной (см. [0182]), и в настоящее время для решения таких систем не известно алгоритма, который бы имел сложность по
порядку меньшую, чем 2°(п где п — число булевых переменных в системе. Но поскольку в теории КР-полных задач сложность оценивается «в худшем случае», то можно ставить задачи разработки более эффективных алгоритмов для конкретных классов систем булевых уравнений.
Анализ некоторых конечных автономных автоматов (см. [КАР85]) в ряде случаев сводится к исследованию систем булевых уравнений, описывающих функционирование этих автоматов и поэтому имеющих определённую структуру.
Основным предметом исследования данной диссертации является показатель алгебраической иммунности булевой функции и связанное с ним понятие аннигилятора (обнуляющего множителя) булевой функции. Знание аннигилятора низкой степени для функции выхода конечного автомата иногда позволяет повысить эффективность решения системы полиномиальных булевых уравнений, описывающих функционирование этого автомата.
В диссертации разработан ряд алгоритмов поиска аннигиляторов низкой степени, получены оценки их сложности. Также разработан комбинаторный метод получения нижних оценок алгебраической иммунности. С помощью этого метода получены оценки для функций из некоторых классов. Для этих же классов получены верхние оценки, имеющие ту же асимптотику что и нижние оценки при количестве переменных функций стремящемся к бесконечности.
Введём обозначения. Р2 — поле из двух элементов. Тп — множество
всех отображений Т2" —> ¥2 (множество всех булевых функций от п переменных). Функция д 6 Тп называется аннигилятором функции / € Тп, если / • д — 0. Множество всех аннигиляторов функции / обозначим
Апп(1) :={де?п{.д = 0}.
Мы будем использовать стандартное отношение частичного порядка " ^" на множестве Тп. Для пары функций /. д е Тп
1^9 & Кх) < 9(х) Vх £
Понятие аннигилятора тесно связано с этим отношением. А именно, если в следующей цепочке эквивалентных утверждений
д ^ к «Ф д = кд д{к +1) = О подставить / вместо д, то получим, что
/ ^ И <£> Н +1 6 Апп(/), (0.1)

Функция д вида (1.33), принадлежит линейному пространству Ад{/), если и только если коэффициенты Ьс (с € /С : \Ч(с) ^ (I) удовлетворяют
следующим условиям:
1. они удовлетворяют системе Л и
пс
2. для каждого с € Зп /£ : (wt(c) ^ ё, с & п) выполнено (Ъс) = Ьс.
В соответствии с этими двумя пунктами составим систему линейных однородных уравнений над полем Р2, которая будет задавать пространство
МЛПункт 1. Преобразуем систему Л разложением по базису е1 ега к системе уравнений относительно координат коэффициентов Ьс в этом базисе. При этом мы получим линейные однородные уравнения, поскольку в систему Л входят только слагаемые вида (1.35), а возведение в квадрат в поле (?.Р(2”) есть линейное преобразование линейного пространства С^(2П) над полем Р2.
Пункт 2. Пусть для элемента Ь € 6Т(2П) задано разложение по базису е1;...,еп: Ь — У"Е-Ае1> а также дана матрица ЦО?*)«!”. линейного
«к <)к г
преобразования 6 6 надполем Р2. Ь - ) ^.^6^ = )

Тогда условие 6 = Ь равносильно следующей системе линейных
однородных уравнений относительно координат Ь1 Ьп € Р2:
■ »у - Е(й)# = °. У/ £ (1.37)
Итого, объединяя линейные уравнения, полученные в обоих пунктах, мы получим систему линейных однородных уравнений Г над полем Р2. Оценим количество уравнений (КУ) и количество переменных (КП) системы Г. В соответствии с построением системы Г по пунктам 1 и 2 получим
ку < & • Е",Ы-" + ^■»= о(Е" «• »»)■
Из определения (1.33) коэффициентов Ьс имеем
КП = {с € /С | ^(с) ^ 4} ^ п ■ в*.
Систему Г можно решить методом Гаусса со сложностью
Аналогично рассуждениям при оценке сложности
алгоритма АМ1 доказывается, что решение системы Г методом Гаусса является доминирующим по сложности шагом алгоритма АТ1. ■