О соотношениях между алгебраической иммунностью и нелинейностью булевых функций.

• Автор: Лобанов, Михаил Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 64 с. : ил.

Оглавление
Введение
Глава 1. Предварительные сведения
Глава 2. Сведение задачи к оценке размерности определенных линейных пространств булевых функций
Глава 3. Точная нижняя оценка для нелинейности (г = 1) и построение функций, на которых она достигается
Глава 4. Алгебраическая иммунность и нелинейность второго порядка
4.1 Точное значение (Ит{В!,■{/)) для бесповторных полиномов .
4.2 Точное соотношение между алгебраической иммунностью и
нелинейностью второго порядка
Глава 5. Оценка нелинейности третьего и выше порядка через значение алгебраической иммунности
Глава 6. Приложения
6.1 Сравнение оценок на п^/)
6.2 Сравнение оценок на п1г(/) при г >
Список литературы

Введение
Многие потоковые шифры состоят из линейной части, порождающей последовательность с большим периодом, обычно состоящей из одного или нескольких регистров сдвига с линейной обратной связью (linear feedback shift registers, LFSR), и нелинейной комбинирующей функции /, которая порождает выходную последовательность по данным линейным входам. Исследования криптографической устойчивости таких шифров большей частью сводятся к исследованию нелинейной функции /, в частности, к исследованию этой функции с точки зрения того, удовлетворяет или не удовлетворяет она некоторым критериям, необходимым для того, чтоб успешно противостоять различным криптографическим атакам.
Для того, чтобы противостоять этим атакам (таким, как атакам Берлекэм-па-Мэсси, различным типам корреляционных и линейных атак [47, 38, 20] и алгебраической атаке (см. [26])), функция должна удовлетворять следующим критериям:
1. Уравновешенность. Булева функция должна выдавать нули и единицы с одинаковой вероятностью.
2. Хорошая корреляционная иммунность (порядка т). Выход булевой функции должен быть статистически независим от комбинации любых т ее входов. Уравновешенная корреляционно-иммунная порядка т булева функция называется т-устойчивой.
3. Хорошая нелинейность различных порядков. Булева функция плохо

приближается полиномами невысокой степени. Особо выделим нелинейность первого порядка. Булева функция должна находиться на достаточно большом расстоянии от любой аффинной функции.
4. Высокая алгебраическая степень.
5. Высокая алгебраическая иммунность. Ни функция, ни ее дополнение не должно иметь аннигиляторов низкой степени.
Также важными критериями являются низкая автокорреляция, простая схемная реализация и т.д.
Критерии зачастую конфликтуют друг с другом, выяснению их взаимосвязей посвящена обширная литература. Например, упомянем работу [13], в которой приведена последовательность функции с высокой корреляционой иммунностью, высокой нелинейностью и неплохой алгебраической иммунностью.
Настоящая работа посвящена взаимосвязи алгебраической иммунности и нелинейности различных порядков.
Пусть / является булевой функцией над Рф. Известно, что / единственным образом представляется полиномом. Степенью булевой функции называется длина самого длинного слагаемого в ее полиноме (количество переменных в этом слагаемом). Булева функция д над Р£ называется аннигилятором булевой функции / над Р2", если /д = 0. Очевидно, что аннигиляторы / образуют линейное подпространство в пространстве всех булевых функций от п переменных.
Определение 1 Алгебраической иммунностью А1(/) булевой функции / над К2П называется ст,епень булевой функции д над Р%, где у не равная тождественно нулю функция с минимальной степенью, такая что фд = 0 или (/ + 1) Известно [26, 42], что для любой / над выполнено

-г соответствует пункту 3, произведение / на /5 имеет степень не больше к, т.к. в противном случае г Е За1,...,ая(.к). Пусть 5 соответствует пункту 4, тогда представим / как сумму двух функций / = Д + /2, где в Д входят I, Д,..., Ьи по счету мономы из записи /, а в /2 все остальные. Несложно проверить, что произведение /2 на Д равно тождественно нулю, а произведение Д на Д равно Д, т.к. Д входит как один из сомножителей (последний) в Д. С учетом того, что с1ед(/г) = ги1(г), из вышесказанного следует, что для любого г = {г,..., гп) Е 5а 1,...,а,1{к) соответствующая Д принадлежит -ВД/).
Утверждения 13 и 14 можно объединить в следующую теорему: Теорема 2 Пусть /(щ,..., хп) — это (ах,..., ач)-бесповториый полином.
Для довольно широкого класса функций мы свели проблему вычисления размерности пространства /Д(/) к несложному комбинаторному подсчету. Более того, для этого класса из доказательства утверждения 14 можно получить метод построения базиса в В*(/). Проиллюстрируем это следующим примером.
Значит сЫт(Вк{,/)) > |Да1,...,а,(А:)| = £ъ=о (") - |5в11...1в,(А)|. □
Тогда