Содержание к диссертации
Введение
Глава 1. Алгоритмические вопросы поиска аннигиляторов булевых функций 21
1.1 Поиск аннигиляторов для различных способов представления булевой функции 21
1.1.1 Для представления функции в виде многочлена Жегалкина 21
1.1.1.1 Алгоритм AM 1 поиска базиса пространства аннигиляторов 22
1.1.1.2 Явный вид системы уравнений, задающей аннигиляторы 25
1.1.1.3 Алгоритм AM 1Б поиска статических соотношений для быстрых алгебраических атак
1.1.1.4 Один способ улучшения алгоритма AM 1 — алгоритм АМ12 30
1.1.2 Для представления функции в виде ДНФ 3 5
1.1.3 Для представления функции в виде формулы или схемы из функциональных элементов
1.1.3.1 Алгоритмы АФ1 и АС 1 поиска аннигиляторов 3 7
1.1.3.2 Дополнение: О линейных аннигиляторах произведения булевых функций 40
1.1.3.3 Дополнение: Структура пространства аннигиляторов для булевых функций с фиктивными переменными 42
1.1.4 Для представления функции в виде трэйс представления 44
1.1.4.1 Алгоритм ATI поиска базиса пространства аннигиляторов 47
1.1.4.2 Алгоритм АТ1Б поиска статических соотношений для быстрых алгебраических атак 50
1.1.4.3 Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции 51
1.1.4.4 Алгебраическая иммунность фильтрующей функции генератора WG 53
1.1.5 О поиске аннигиляторов для частично определённых функций 55
1.2 Алгоритмы проверки отсутствия ненулевых аннигиляторов 58
1.2.1 Проверка отсутствия ненулевых аннигиляторов низкой степени у многочлена Жегалкина 59
1.2.1.1 Основной вариант алгоритма АМ2 59
1.2.1.2 Возможные пути модификации алгоритма АМ2 62
1.2.2 Проверка отсутствия ненулевых аннигиляторов низкой степени у ДНФ 63
Глава 2. Нижние и верхние оценки алгебраической иммунности булевых функций, заданных трэйс представлением 65
2.1 Алгебраическая иммунность линейных функций от инверсии 65
2.2 Нижние оценки алгебраической иммунности более широких классов функций 72
2.3 Верхние оценки алгебраической иммунности более широких классов функций 85
Глава 3. Исследование метода быстрых алгебраических атак (БАА) 88
3.1 Предварительные сведения 8 8
3.2 Полиномиальный алгоритм получения тождеств для метода БАА по трэйс представлению функции 90
3.3 Полиномиальный алгоритм получения нелинейных рекуррентных соотношений для фильтрующего генератора по трэйс представлению фильтрующей функции 93
3.4 Явное выражение для минимальной линейной комбинации предварительного шага метода БАА 95
Список литературы 97
- Алгоритм AM 1 поиска базиса пространства аннигиляторов
- Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции
- Нижние оценки алгебраической иммунности более широких классов функций
- Полиномиальный алгоритм получения тождеств для метода БАА по трэйс представлению функции
Введение к работе
В теории конечных автоматов, теории кодирования и криптологии возникают задачи изучения и решения систем булевых уравнений. Как известно, задача решения произвольной системы полиномиальных булевых уравнений является NP-трудной (см. [GJ82]), и в настоящее время для решения таких систем не известно алгоритма, который бы имел сложность по порядку меньшую, чем 2 , где п — число булевых переменных в системе. Но поскольку в теории NP-полных задач сложность оценивается «в худшем случае», то можно ставить задачи разработки более эффективных алгоритмов для конкретных классов систем булевых уравнений.
Анализ некоторых конечных автономных автоматов (см. [КАР85]) в ряде случаев сводится к исследованию систем булевых уравнений, описывающих функционирование этих автоматов и поэтому имеющих определённую структуру.
Основным предметом исследования данной диссертации является показатель алгебраической иммунности булевой функции и связанное с ним понятие аннигилятора (обнуляющего множителя) булевой функции. Знание аннигилятора низкой степени для функции выхода конечного автомата иногда позволяет повысить эффективность решения системы полиномиальных булевых уравнений, описывающих функционирование этого автомата.
В диссертации разработан ряд алгоритмов поиска аннигиляторов низкой степени, получены оценки их сложности. Также разработан комбинаторный метод получения нижних оценок алгебраической иммунности. С помощью этого метода получены оценки для функций из некоторых классов. Для этих же классов получены верхние оценки, имеющие ту же асимптотику что и нижние оценки при количестве переменных функций стремящемся к бесконечности.
Будем обозначать deg/ — степень булевой функции / € Тп — степень её многочлена Жегалкина (см. [Yabl03]). При этом считаем degO = 0. Введём обозначения для линейного пространства аннигиляторов степени d: 4/(/) ••= AJ(f) := {g€Fn\fg = 0, degg d} с Ann(f).
Верхний индекс п в обозначении этого пространства будем указывать, когда нам будет нужно явно акцентировать внимание на пространстве Fn, в
котором мы рассматриваем аннигиляторы.
Множество {0} мы для краткости будем также обозначать 0, но только в тех случаях, когда контекст допускает единственную трактовку. Например, «F2ra\0»H« (/) = 0».
Одним классом конечных автономных автоматов являются фильтрующие генераторы. Фильтрующий генератор (ФГ) состоит из двоичного регистра сдвига длины п с линейной обратной связью и фильтрующей булевой функции / Є Тп. На г-ж шаге функционирования на
выход фильтрующего генератора выдаётся значение f(Lls), где s Є Ef — начальное состояние регистра, a L : F — F — линейное преобразование
регистра, совершаемое на каждом шаге.
Фильтрующие генераторы используются в качестве генераторов псевдослучайных двоичных последовательностей, в частности, в потоковых шифрах (см. также [AZKCH], [MOV]).
В 2003 г. в работе [СМ03] был предложен метод анализа фильтрующих генераторов (а также других типов псевдослучайных генераторов), основанный на понижении степени исходной совместной системы полиномиальных булевых уравнений относительно начального состояния генератора. Этот метод был назван авторами алгебраической атакой (АА).
Введём следующее обозначение для суммы биномиальных коэффициентов:
Основным требованием для эффективного применения метода АА является существование булевой функции д низкой степени, ограничивающей фильтрующую функцию / сверху или снизу. В силу (0.1) и (0.2) д должна принадлежать либо линейному пространству
Таким образом, для анализа ряда псевдослучайных генераторов двоичных последовательностей стали нужны методы эффективного поиска аннигиляторов наименьшей степени d для фильтрующей функции / (в случае, когда AI(f) мало) либо поиска значения AI(f), если оно достаточно велико. Основная часть диссертации посвящена этому вопросу.
Следующая теорема является переформулировкой теоремы 2 из [D05] в терминах двух предыдущих теорем.
Теорема ([D05], Theorem 2). Пусть случайная величина Fn равномерно
распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда для любого действительного числа а из интервала (0;21п2) существует следующий предел вероятности. Р {і - $W AI(Fn) Щ 1, up noo.
To есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п/2 —
максимально возможный.
Предыдущие теоремы дают некоторое представление о функции AI: [J _ Тп — Z и о распределении значения минимальной степени аннигилятора на множестве. Они в рамках своей выразительности
характеризуют свойство алгебраической иммунности сразу для группы функций. Другая сторона исследования этого свойства — алгоритмический подход, разработка алгоритмов вычисления функции AI и поиска аннигиляторов низкой степени для заданной функции. То есть, когда мы хотим (имея один или несколько алгоритмов) находить аннигиляторы или алгебраическую иммунность для одной конкретной функции, а не для широкого класса.
Далее при описании алгоритмов в качестве модели вычислителя мы будем использовать RAM-машину (однопроцессорную машину с прямым доступом к памяти). То есть время получения доступа к ячейке памяти по её номеру ограничено сверху некоторой константой. Подразумеваем также, что алгоритм получает некоторые данные конечной длины в алфавите {0,1} на вход и выполняет некоторую последовательность базовых операций в зависимости от входных данных, формируя при этом выходные данные. Ответом алгоритма будем называть набор выходных данных, сформировавшихся после останова алгоритма. Базовыми операциями мы будем называть битовые операции и операцию получения значения из ячейки памяти по номеру этой ячейки. Считаем, что время работы алгоритма пропорционально количеству проделанных им базовых операций. Под сложностью алгоритма будем понимать функцию времени работы алгоритма, зависящую от входных данных этого алгоритма.
Впервые в работе [МРС04] были представлены 2 алгоритма (алгоритм 1 и алгоритм 2), получающих на вход число d и вектор (таблицу) значений функции / Є Тп на всех 2п векторах пространства Ef. Алгоритм вычисляет базис пространства Ad(f) за время 0(wt(f)-(Sn) ). Для некоторых уравновешенных функций с количеством переменных п 20 время работы этого алгоритма очень велико. Алгоритм 2 вероятностный. Он выдаёт базис некоторого линейного пространства Ud(f) С Тп, содержащего в себе пространство аннигиляторов Ad(f). Если получилось, что Ud(f) = 0, то это значит, что и Ad(f) = 0. Если же Ud(f) 0, то ничего более определённого, чем Ad(f) С Ud(f), утверждать нельзя. В частности, остаётся неизвестным, тривиально ли пространство Ad(f). Сложность этого алгоритма оценивается 0((Sn) ), что расширяет область его применимости по сравнению с первым алгоритмом.
Алгоритм 2 из [DT06] является небольшой модификацией алгоритма 1 из [МРС04]. Новый алгоритм позволяет для некоторых функций существенно сократить вычисления за счёт использования некоторой информации о решаемой системе линейных уравнений. Общая оценка сложности осталась таже-ОИС/И )2).
Все упомянутые алгоритмы из работ [МРС04] и [DT06] работают с табличным представлением функции /, а их сложность пропорциональна весу функции. Это значит, что, в частности, для уравновешенных функций / Є Тп эти алгоритмы будут иметь экспоненциальную от п сложность. В
связи с этим замечанием возникает задача разработки алгоритмов поиска аннигиляторов для других способов представления функции /.
В главе 1 данной диссертации разработаны алгоритмы поиска аннигиляторов из пространства Ad(f) для некоторых способов представления функции /, отличных от табличного. Часть алгоритмов универсальны, т.е. для любой функции на входе они выдают базис пространства Ad(f), а другая часть алгоритмов для некоторых функций может выдать неопределённый ответ или базис некоторого подпространства Н С Ad(f) • На вход каждому алгоритму из 1-й главы подаются числа п и d, а также булева функция / € Тп, заданная в виде некоторого представления.
В разделе 1.1.1.1 предложен алгоритм AMI поиска базиса пространства Ad(f). На вход алгоритму подаётся многочлен Жегалкина ,функции /. На выходе — многочлены Жегалкина базисных функций пространства Ad(f). Оценка сложности алгоритма AMI — 0(Mf(Sn) ), где Mt — длина многочлена Жегалкина функции / (количество мономов). В разделе 1.1.1.4 изложен приём, позволяющий для некоторых функций существенно сократить вычисления. Результатом применения этого приёма к алгоритму AMI является алгоритм АМ12. В разделе 1.1.5 рассказано, что даёт алгоритм AMI для частично определённых функций / : F \ 0 — F2.
В разделе 1.1.2 предложен алгоритм АД1, получающий на входе дизъюнктивную нормальную форму (ДНФ, см. [Yabl03]) функции /. Он вычисляет многочлены Жегалкина базисных функций пространства Ad(f) за
время 0(Df(Sn) ), где Dj — количество элементарных конъюнкций в ДНФ,
задающей функцию /. Также доказана следующая теорема.
Теорема 1.14. Для любых чисел n,dN таких, что O d n, задача вычисления базиса линейного пространства Ad(f) для функции f Є Тп, заданной в виде конъюнктивной нормальной формы (КНФ, см. [Yabl03]), является NP-трудной.
В разделе 1.1.3.1 предложены алгоритмы АФ1 и АС1, которые по формуле либо схеме из функциональных элементов (СФЭ, см. [Yabl03]) в базисе операций {-i,&,V} находят многочлены Жегалкина базисов пары пространств G,HcFn. Причём G cAd(f + 1), HcAd(f). Однако, при
Отметим, что все рассмотренные представления (носитель, многочлен, ДНФ, ТП) булевых функций, для которых построены полиномиальные алгоритмы, не сводятся полиномиально друг к другу. Это значит, что ни один из соответствующих алгоритмов (алгоритм 1 из [МРС04], АМ12, АД1, ATI) вычисления базиса пространства Ad(f) не является лишним, каждый ориентирован на своё представление функции .
Среди алгоритмов получения оценок алгебраической иммунности булевых функций выделяется группа алгоритмов, которые предназначены для проверки тривиальности пространства Ad(f). Коротко будем называть их алгоритмами проверки. Эти алгоритмы выдают один из двух ответов: «Ad(f) = О» или «неопределённость». Первый ответ выдаётся только в тех случаях, когда вычисления, проделанные алгоритмом проверки, доказывают тривиальность пространства -4/(/)- В случаях, когда не удаётся это доказать, выдаётся второй ответ. Преимущество такого класса алгоритмов над универсальными алгоритмами, описанными выше, заключается в том, что их сложность гораздо меньше. Недостатки же очевидны. Если Ad(f) 0, то алгоритм проверки обязательно выдаст ответ «неопределённость» и не найдёт ни одного ненулевого аннигилятора (в этом случае можно применить один из упомянутых ранее алгоритмов поиска аннигиляторов). Более того, не всегда, когда пространство Ad(f) тривиально, алгоритм проверки может вычислительно это доказать. Доля тех функций, для которых выдаётся первый ответ, характеризует качество алгоритма проверки. Алгоритмы 1 и 2 из [МРС04], о которых было рассказано выше, как раз являются примером пары (универсальный алгоритм, алгоритм проверки).
Алгоритм 1 из [DT06], предложенный в 2006 г., также относится к классу алгоритмов проверки тривиальности пространства Ad(f) для табличного представления функции / Є Тп. Про этот детерминированный алгоритм была доказана следующая теорема.
Теорема ([DT06], Theorem 2). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда математическое ожидание времени работы алгоритма для входной функции Fn можно оценить 0(п ), а вероятность того, что на выходе будет ответ «неопределенность» оценивается 0{е п"+°{ "). В указанных оценках d считается константой, а асимптотика рассматривается при п — оо. (Для сравнения, время работы алгоритма из [МРС04] оценивается 0{{Sdnf) = 0(пы).) В разделе 1.2 предложены алгоритмы проверки АМ2 и АД2, являющиеся модификациями алгоритма 1 из [DT06] для представления входной функции в виде многочлена Жегалкина и в виде ДНФ соответственно. Сложность этих двух алгоритмов есть 0(М-п ) при М, п — оо, где М — количество мономов в многочлене Жегалкина (для алгоритма АМ2) или количество элементарных конъюнкций в ДНФ (для алгоритма АД2). Причём, в отличие от оценки сложности алгоритма 1 из [DT06] оценка сложности алгоритмов АМ2 и АД2 имеет место для каждой входной функции, размер представления которой равен М. Получая на вход соответствующие представления одной и той же булевой функции, алгоритмы АМ2 и АД2, а также алгоритм 1 из [DT06] всегда выдают одинаковые ответы. Это значит, что доля уравновешенных функций из Тп, для которых алгоритмы АМ2 и АД2 выдают ответ «неопределённость», также оценивается 0(е п +0 ).
Кроме алгоритмического поиска аннигиляторов и значения алгебраической иммунности булевой функции особенный интерес представляют:
1. получение верхних и нижних оценок значения алгебраической иммунности для различных классов булевых функций,
2. соотношение алгебраической иммунности булевой функции с другими её характеристиками, которые также важны при анализе ФГ.
В работе [ВР05] приводится алгоритм вычисления алгебраической иммунности симметричных булевых функций. Описываются классы симметричных булевых функций из Тп, которые имеют максимальное
значение алгебраической иммунности, равное \п / 2.
В работах [DMS05], [DGM05], [QFL05], [DM06], [CQ6], [АК06], [LQ06] приводятся различные конструкции классов булевых функций, на которых также достигается максимум значения алгебраической иммунности.
В [BotDis] доказано, что для последовательностей функций, построенных с помощью ряда конструкций из [Т02], имеет место нижняя оценка их алгебраической иммунности вида fi(Vn), где п — количество
переменных в этих функциях. Кроме того, в [BotDis] приводится новое семейство функций, алгебраическая иммунность которых также оценивается снизу fi(Vn).
Глава 2 данной диссертации посвящена получению верхних и нижних оценок алгебраической иммунности некоторых классов булевых функций, заданных в виде трэйс представления.
Поле GF(2n) (поле Галуа из 2п элементов, [LSYa], [LN88]) является линейным пространством над полем F2. Зафиксируем произвольный изоморфизм (р : GF(2n) —» F2n линейных пространств над полем F2. Ниже мы будем его регулярно использовать. ц задаёт также отождествление Тп с пространством функций GF(2n) — F2. Функции / Є Тп соответствует функция fo p: GF(2n) -+ F2.
Вернёмся к обсуждению методов анализа фильтрующих генераторов. В 2003 г. в работе [СОЗ] был предложен метод быстрых алгебраических атак (БАА), являющийся усовершенствованием метода АА. Он в ряде случаев эффективнее и предполагает существование более общего вида соотношений низкой степени, связывающих значения фильтрующей функции / и значения её аргументов. А именно, для применения метода БАА нужно знать тождества следующего вида.
Функция h может быть задана многочленом Жегалкина. Однако, в [HR04] предложен приём, позволяющий при применении метода БАА вообще не использовать функцию h — достаточно знать, что её степень не превосходит некоторого известного числа d. Говоря о тождествах вида (0.3) для БАА, будем полагать, что d = degh, а степень функции д : F2n xF2 — F2 по первым п булевым аргументам равна е. На числа d,e накладывается ограничение d е.
Если известно хотя бы одно тождество (0.3) для малых значений чисел d и е, то метод БАА позволяет (в некоторых случаях) находить начальное состояние s фильтрующего генератора по сплошному куску некоторой длины Т выходной последовательности {f{Lls) }г Х+г
где wt(i) — количество единиц в двоичной записи числа г, а а Є GF(2n) — корень примитивного характеристического многочлена матрицы L. В работе [HR04] показано, как получить а за время 0(S (hgSn) ), а также как, используя быстрое преобразование Фурье над полем GF(2n), снизить сложность подстановочного шага (без решения системы (0.10)) с 0(5 (5 )2)
В 2005 г. на открытом конкурсе поточных шифров eSTREAM был представлен фильтрующий генератор WG, [NG05]. Десятки учёных, занимающихся анализом поточных шифров1, публиковали на сайте конкурса свои статьи, в которых они анализировали ту или иную систему шифрования, представленную на этом конкурсе. В частности, про генератор WG его авторами было доказано, что выходная последовательность этого генератора обладает рядом хороших характеристик (большой период, высокая линейная сложность, одинаковость частот встречаемости наборов из нулей и единиц длины 11, один хороший автокорреляционный показатель), но про значение алгебраической иммунности фильтрующей функции .
Алгоритм AM 1 поиска базиса пространства аннигиляторов
В теории конечных автоматов, теории кодирования и криптологии возникают задачи изучения и решения систем булевых уравнений. Как известно, задача решения произвольной системы полиномиальных булевых уравнений является NP-трудной (см. [GJ82]), и в настоящее время для решения таких систем не известно алгоритма, который бы имел сложность по порядку меньшую, чем 2 , где п — число булевых переменных в системе. Но поскольку в теории NP-полных задач сложность оценивается «в худшем случае», то можно ставить задачи разработки более эффективных алгоритмов для конкретных классов систем булевых уравнений. Анализ некоторых конечных автономных автоматов (см. [КАР85]) в ряде случаев сводится к исследованию систем булевых уравнений, описывающих функционирование этих автоматов и поэтому имеющих определённую структуру.
Основным предметом исследования данной диссертации является показатель алгебраической иммунности булевой функции и связанное с ним понятие аннигилятора (обнуляющего множителя) булевой функции. Знание аннигилятора низкой степени для функции выхода конечного автомата иногда позволяет повысить эффективность решения системы полиномиальных булевых уравнений, описывающих функционирование этого автомата.
В диссертации разработан ряд алгоритмов поиска аннигиляторов низкой степени, получены оценки их сложности. Также разработан комбинаторный метод получения нижних оценок алгебраической иммунности. С помощью этого метода получены оценки для функций из некоторых классов. Для этих же классов получены верхние оценки, имеющие ту же асимптотику что и нижние оценки при количестве переменных функций стремящемся к бесконечности. Введём обозначения. F2 — поле из двух элементов. Тп — множество всех отображений Ff — F2 (множество всех булевых функций от п переменных). Функция д є Тп называется аннигилятором функции / Тп, если / = 0. Множество всех аннигиляторов функции / обозначим Ann(f):={gefn\f.g = 0}. Мы будем использовать стандартное отношение частичного порядка " " на множестве Тп. Для пары функций f,g еТп 1 9 & f(x) g(x) Vz6F2n. Понятие аннигилятора тесно связано с этим отношением. А именно, если в следующей цепочке эквивалентных утверждений g h&g = hg&g(h-l) = 0 подставить / вместо д, то получим, что f h&h + lAnn(f), (0.1) а если подставить / вместо h, то получим, что g f&geAnn(f + l). (0.2) Будем обозначать deg/ — степень булевой функции / Тп — степень её многочлена Жегалкина (см. [Yabl03]). При этом считаем degO = 0. Введём обозначения для линейного пространства аннигиляторов степени d: 4/(/) = AJ(f) := {gFn\fg = 0, degg d} с Ann(f). Верхний индекс п в обозначении этого пространства будем указывать, когда нам будет нужно явно акцентировать внимание на пространстве Fn, в котором мы рассматриваем аннигиляторы. Множество {0} мы для краткости будем также обозначать 0, но только в тех случаях, когда контекст допускает единственную трактовку. Например, «F2ra\0»H« (/) = 0». Одним классом конечных автономных автоматов являются фильтрующие генераторы. Фильтрующий генератор (ФГ) состоит из двоичного регистра сдвига длины п с линейной обратной связью и фильтрующей булевой функции / Є Тп. На г-ж шаге функционирования на выход фильтрующего генератора выдаётся значение f(Lls), где s Є Ef — начальное состояние регистра, a L : F — F — линейное преобразование регистра, совершаемое на каждом шаге. Фильтрующие генераторы используются в качестве генераторов псевдослучайных двоичных последовательностей, в частности, в потоковых шифрах (см. также [AZKCH], [MOV]).
В 2003 г. в работе [СМ03] был предложен метод анализа фильтрующих генераторов (а также других типов псевдослучайных генераторов), основанный на понижении степени исходной совместной системы полиномиальных булевых уравнений относительно начального состояния генератора. Этот метод был назван авторами алгебраической атакой (АА).
Модификация алгоритма АТ1Б, ориентированная на короткое трэйс представление входной функции
Основным требованием для эффективного применения метода АА является существование булевой функции д низкой степени, ограничивающей фильтрующую функцию / сверху или снизу. В силу (0.1) и (0.2) д должна принадлежать либо линейному пространству Ann(f + l) = {gefn\g f}: либо аффинному пространству l + Ann(f) = {hefn\f h}. В 2004 г. в работе [МРС04] было введено понятие алгебраической иммунности булевой функции / є Тп. Значение алгебраической иммунности AI(j) равно минимальному значению числа d, для которого существует ненулевая булева функция д Є Тп степени d такая, что fg = 0 или (/ +1) ? = 0. Формально можно записать так: AI(f) := min{d I Ad(f) 0 или Ad(f +1) 0}.
Таким образом, для анализа ряда псевдослучайных генераторов двоичных последовательностей стали нужны методы эффективного поиска аннигиляторов наименьшей степени d для фильтрующей функции / (в случае, когда AI(f) мало) либо поиска значения AI(f), если оно достаточно велико. Основная часть диссертации посвящена этому вопросу. Заметим, что если мы имеем алгоритм вычисления базисов линейных пространств Ad(f) и Ad(f + 1), то мы можем вычислить значение A 1(f). А именно, мы можем последовательно перебирать все значения d 0 и вычислять базисы пространств Ad(f) и Ad(f + l) до тех пор, пока мы не получим хотя бы одно ненулевое пространство. Вычисление же базиса одного конкретного пространства Ad(f) может дать нам оценку значения AI(f): если оказалось, что Ad(f) 0, то это означает, что AI(f) d. В [МРС04] приведена следующая теорема, являющаяся модификацией теоремы 6.0.1 из [СМ03]. Теорема ([МРС04], Theorem 6.0.1). Для любой функции / є Fn существует ненулевая функция д.Тп такая, что degg [n/2j и deg(fg) fn/2. Из этой теоремы следует, что AI(f) \n/2] для любой функции Для дальнейшего изложения нам понадобятся следующие обозначения. Для подмножества А С Тп положим mindeg(i4) := minjdeg/ / А}. Носителем функции / Є Тп называется множество supp(/) := {х Є F2n f(x) = 1}. Бесом функции / Є Тп называется мощность её носителя wt(/) := supp(/). Функция /6 , называется уравновешенной, если wt(/) = 2п . Множество функций степени d будем обозначать 1Z(d,n)-{fefn\degf d}. В [А04Е] минимальная степень аннигилятора булевой функции / оценивается через вес функции /. А именно, доказаны следующие 2 теоремы.
Теорема ([А04Е], Corollary 1). Если для функции / Тп и числа d Є {0,...,n} выполнено неравенство Sn wt(/), то mmdeg(Ann(f)) d. Теорема ([А04Е], Corollary 2). Если для функции / Тп и числа d є{0,...,п} выполнено неравенство wt(/) (2 —1)2" , то mmdeg(Ann(f)) d. В 2004 г. в [МРС04] были доказаны следующие 2 теоремы о распределении значения алгебраической иммунности на множестве уравновешенных булевых функций. Теорема ([МРС04], Theorem 3). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Рассмотрим произвольную последовательность {dn}n натуральных чисел такую, что dn fin, где = 2(1+-V(1+)2-1) 0-22 Тогда существует предел вероятности того, что AI{Fn) dn: P{AI(Fn) dn} - 0, при п - оо. Теорема ([МРС04], Theorem 4). Зафиксируем числа п и d такие, что О d п. Количество функций веса w из 7Z(d, п) обозначим Aw:=\{feU(d,n)\wt(f) = w}\. Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда имеет место следующая оценка вероятности того, что AI(Fn) d: nil пП—d пП—1 tyll—d nti-d+1 )П—d+l г"-1- T-V) P{AI(Fn) d} Aw 2n г,П—1 „„ r n-d І 2n_1 -w Следующая теорема является переформулировкой теоремы 2 из [D05] в терминах двух предыдущих теорем. Теорема ([D05], Theorem 2). Пусть случайная величина Fn равномерно распределена на множестве всех уравновешенных булевых функций от п переменных. Тогда для любого действительного числа а из интервала (0;21п2) существует следующий предел вероятности. Р {і - $W AI(Fn) Щ 1, up noo. To есть алгебраическая иммунность почти всех уравновешенных булевых функций от п переменных имеет асимптотический порядок п/2 — максимально возможный.
Предыдущие теоремы дают некоторое представление о функции AI: [J _ Тп — Z и о распределении значения минимальной степени аннигилятора на множестве Тп. Они в рамках своей выразительности характеризуют свойство алгебраической иммунности сразу для группы функций. Другая сторона исследования этого свойства — алгоритмический подход, разработка алгоритмов вычисления функции AI и поиска аннигиляторов низкой степени для заданной функции. То есть, когда мы хотим (имея один или несколько алгоритмов) находить аннигиляторы или алгебраическую иммунность для одной конкретной функции, а не для широкого класса.
Нижние оценки алгебраической иммунности более широких классов функций
Далее при описании алгоритмов в качестве модели вычислителя мы будем использовать RAM-машину (однопроцессорную машину с прямым доступом к памяти). То есть время получения доступа к ячейке памяти по её номеру ограничено сверху некоторой константой. Подразумеваем также, что алгоритм получает некоторые данные конечной длины в алфавите {0,1} на вход и выполняет некоторую последовательность базовых операций в зависимости от входных данных, формируя при этом выходные данные. Ответом алгоритма будем называть набор выходных данных, сформировавшихся после останова алгоритма. Базовыми операциями мы будем называть битовые операции и операцию получения значения из ячейки памяти по номеру этой ячейки. Считаем, что время работы алгоритма пропорционально количеству проделанных им базовых операций. Под сложностью алгоритма будем понимать функцию времени работы алгоритма, зависящую от входных данных этого алгоритма.
Впервые в работе [МРС04] были представлены 2 алгоритма (алгоритм 1 и алгоритм 2), получающих на вход число d и вектор (таблицу) значений функции / Є Тп на всех 2п векторах пространства Ef. Алгоритм 1 вычисляет базис пространства Ad(f) за время 0(wt(f)-(Sn) ). Для некоторых уравновешенных функций с количеством переменных п 20 время работы этого алгоритма очень велико. Алгоритм 2 вероятностный. Он выдаёт базис некоторого линейного пространства Ud(f) С Тп, содержащего в себе пространство аннигиляторов Ad(f). Если получилось, что Ud(f) = 0, то это значит, что и Ad(f) = 0. Если же Ud(f) 0, то ничего более определённого, чем Ad(f) С Ud(f), утверждать нельзя. В частности, остаётся неизвестным, тривиально ли пространство Ad(f). Сложность этого алгоритма оценивается 0((Sn) ), что расширяет область его применимости по сравнению с первым алгоритмом.
Алгоритм 2 из [DT06] является небольшой модификацией алгоритма 1 из [МРС04]. Новый алгоритм позволяет для некоторых функций существенно сократить вычисления за счёт использования некоторой информации о решаемой системе линейных уравнений. Общая оценка сложности осталась таже-ОИС/И )2).
Все упомянутые алгоритмы из работ [МРС04] и [DT06] работают с табличным представлением функции /, а их сложность пропорциональна весу функции. Это значит, что, в частности, для уравновешенных функций / Є Тп эти алгоритмы будут иметь экспоненциальную от п сложность. В связи с этим замечанием возникает задача разработки алгоритмов поиска аннигиляторов для других способов представления функции /.
Отметим, что все рассмотренные представления (носитель, многочлен, ДНФ, ТП) булевых функций, для которых построены полиномиальные алгоритмы, не сводятся полиномиально друг к другу. Это значит, что ни один из соответствующих алгоритмов (алгоритм 1 из [МРС04], АМ12, АД1, ATI) вычисления базиса пространства Ad(f) не является лишним, каждый ориентирован на своё представление функции /. Среди алгоритмов получения оценок алгебраической иммунности булевых функций выделяется группа алгоритмов, которые предназначены для проверки тривиальности пространства Ad(f). Коротко будем называть их алгоритмами проверки. Эти алгоритмы выдают один из двух ответов: «Ad(f) = О» или «неопределённость». Первый ответ выдаётся только в тех случаях, когда вычисления, проделанные алгоритмом проверки, доказывают тривиальность пространства -4/(/)- В случаях, когда не удаётся это доказать, выдаётся второй ответ. Преимущество такого класса алгоритмов над универсальными алгоритмами, описанными выше, заключается в том, что их сложность гораздо меньше. Недостатки же очевидны. Если Ad(f) 0, то алгоритм проверки обязательно выдаст ответ «неопределённость» и не найдёт ни одного ненулевого аннигилятора (в этом случае можно применить один из упомянутых ранее алгоритмов поиска аннигиляторов). Более того, не всегда, когда пространство Ad(f) тривиально, алгоритм проверки может вычислительно это доказать. Доля тех функций, для которых выдаётся первый ответ, характеризует качество алгоритма проверки. Алгоритмы 1 и 2 из [МРС04], о которых было рассказано выше, как раз являются примером пары (универсальный алгоритм, алгоритм проверки).
Полиномиальный алгоритм получения тождеств для метода БАА по трэйс представлению функции
Кроме алгоритмического поиска аннигиляторов и значения алгебраической иммунности булевой функции особенный интерес представляют: 1. получение верхних и нижних оценок значения алгебраической иммунности для различных классов булевых функций, 2. соотношение алгебраической иммунности булевой функции с другими её характеристиками, которые также важны при анализе ФГ. В работе [ВР05] приводится алгоритм вычисления алгебраической иммунности симметричных булевых функций. Описываются классы симметричных булевых функций из Тп, которые имеют максимальное значение алгебраической иммунности, равное \п / 2. В работах [DMS05], [DGM05], [QFL05], [DM06], [CQ6], [АК06], [LQ06] приводятся различные конструкции классов булевых функций, на которых также достигается максимум значения алгебраической иммунности. В [BotDis] доказано, что для последовательностей функций, построенных с помощью ряда конструкций из [Т02], имеет место нижняя оценка их алгебраической иммунности вида fi(Vn), где п — количество переменных в этих функциях. Кроме того, в [BotDis] приводится новое семейство функций, алгебраическая иммунность которых также оценивается снизу fi(Vn). В 2005 г. на конкурсе поточных шифров eSTREAM был представлен фильтрующий генератор WG, [NG05]. Десятки учёных, занимающихся анализом поточных шифров, публиковали на сайте конкурса свои статьи, в которых они анализировали ту или иную систему шифрования, представленную на этом конкурсе. В частности, про генератор WG его авторами было доказано, что выходная последовательность этого генератора обладает рядом хороших характеристик (большой период, высокая линейная сложность, одинаковость частот встречаемости наборов из нулей и единиц длины 11, один хороший автокорреляционный показатель), но про значение алгебраической иммунности фильтрующей функции fWQ Fn высказывались только предположения и приводились некоторые оценки. Функция f\YQ задаётся трэйс представлением. В работе [BLP06] был описан подход, позволяющий в некоторых случаях находить тождества (1.15) для булевой функции / Є Тп, заданной в виде вектора значений. Предложенный подход основан на поиске ступенчатого вида матрицы решаемой системы линейных булевых уравнений. Полученные таким образом алгоритмы работают в некоторых случаях эффективнее, чем соответствующие им аналоги из статьи [МРС04] (алгоритмы 1 и 2). В статье [BLP06] была также оценена ожидаемая сложность применения нового подхода к вычислению тождеств (1.15) для функции fWg. Для нескольких значений пары чисел (d,r) была приведена следующая таблица двоичных логарифмов сложностей поиска таких тождеств с помощью предложенного подхода.
Тождество (3.1) означает, что нужно наложить ограничение на степень многочлена Жегалкина функции, заданной многочленом (3.11). В очередной раз отметим, что мы зафиксировали отождествление у?: GF(2n)«-»Ef, которое позволяет нам однозначно переходить от многочленов из кольца GF(2n)[x)/(x —х), задающих функции GF(2n) —» F2, к многочленам Жегалкина. Предложение 1.22 говорит нам, что ограничение на степень многочлена Жегалкина эквивалентно ограничению на вес степеней мономов интерполяционного многочлена (3.11). То есть, приведя подобные в многочлене (3.11), нужно приравнять к нулю выражения для коэффициентов перед теми мономами Xs, для которых wt(s) d. Естественно, что для циклически эквивалентных степеней s (из одного и того же циклотомического класса) мы получим равносильные уравнения. То есть достаточно помещать в систему уравнение для какого-то одного представителя циклотомического класса, а остальных представителей этого класса игнорировать.
