Бент-функции, аффинные на подпространствах, и их метрические свойства тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Коломеец, Николай Александрович

• Коломеец, Николай Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Коломеец, Николай Александрович

Оглавление

Введение

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к от функции из к • •

5.1 Верхняя оценка для произвольной бент-функции

5.2 Нижняя оценка для бент-функций из класса Мэйорана—МакФарланда

Заключение

Литература

А Программное обеспечение для проведения численных экспериментов

А. 1 Двоичные векторы

А.2 Линейные подпространства

А.З Поля Галуа

А.4 Итераторы

А.5 Представления булевых функций

А.5.1 Вектор значений

А.5.2 Алгебраическая нормальная форма

А.5.3 Трейс-форма

А.6 Бент-функции

Введение диссертации (часть автореферата) на тему «Бент-функции, аффинные на подпространствах, и их метрические свойства»

Введение

Работа посвящена исследованию важного класса булевых функций, обладающих максимальной нелинейностью. Это класс бент-функций. Бент-функции интересны не только из-за экстремального значения нелинейности, но и из-за большого числа приложений в криптографии, теории кодирования, алгебре, теории символьных последовательностей.

Приведем необходимые определения.

Функция вида / : —> называется булевой функцией от п переменных, х Е — двоичным вектором длины п, х = (х\,..., хп)Т. Через Тп обозначим множество всех булевых функций от п переменных. Для х, у Е Щ определим х © у = (х\ ф яд,..., хп ф Уп)Т, где ф — сложение по молулю 2. Введём аналог скалярного произведения по модулю 2:

(х, у) = Х1У1 ф Х2У2 Ф . . . Ф Хпуп.

Отметим, что (х, у) не является скалярным произведением в полном смысле этого понятия, поскольку не все свойства скалярного произведения верны в двоичном случае.

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

¿а,с{х) = (а5х) © с для некоторых а Е с Е Ъ2.

Через Лп обозначается множество всех аффинных функций от п переменных. Расстоянием Хэмминга между двумя двоичными векторами .г, у Е называется число координат, в которых х и у различаются. Расстоянием между двумя булевыми функциями называется расстояние Хэмминга между векто-

рами их значений, оно обозначается как сЦб 1;(/, <?). Булевы функции /, д Е Тп называются аффинно эквивалентными, если существует невырожденная двоичная матрица А размера п х п, вектор Ь Е и аффинная функция £ Е Лп, такие что

/(ж) = д(Ах ф Ъ) ф £{х) для всех х Е

Нелинейностью Nf булевой функции / £ Тп называется расстояние от / до множества всех аффинных функций:

деЛп

Булева функция / £Е Тп называется максимально нелинейной, если ^ принимает максимальное возможное значение. В случае чётного п максимальное Nf известно:

тахЛ^ = 2п~1-2п/2~1. 1етп 1

Все булевы функции, обладающие такой нелинейностью, называются бент-функциями. Таким образом, бент-функции существуют только для чётного числа переменных, и в этом случае являются максимально нелинейными. В случае нечётного п точное значение максимальной нелинейности неизвестно.

Преобразованием Уолша—Адамара функции / € Тп называется функция : Щ —> Ъ, заданная равенством

и'/Ы = Е ("1)Л

ж)® (х,у)

при этом сами числа Wf(y) называются коэффициентами Уолша—Адамара. Коэффициенты Уолша—Адамара однозначно определяют функцию /. Также они тесно связаны с расстоянием от функции / до аффинных функций:

(Н81(/Л,о) = 2 "-1 - 1^/(2,). Поскольку (Нб^/, ^д) = 2п — (Иб^/, то справедливо

Щ = так Щ(у)\.

Для коэффициентов Уолша—Адамара справедливо равенство Парсеваля:

£ Щу) = 22п.

у&Щ

Из него следует, что Nf < 2п~г — 2П/2-1. Так как коэффициенты Уолша—Адамара являются удобным инструментом для подсчёта нелинейности, бент-функции часто определяют следующим образом: д € Т^к называется бент-функцией, если = 2к для всех у £ Множество всех бент-функций от 2к переменных обозначают через Оба приведенных определения бент-функций являются эквивалентными.

Нелинейность — одно из важнейших криптографических свойств булевых функций. В частности, алгоритм симметричного шифрования DES (Data Encryption Standard), бывший американский стандарт блочного шифрования, был заменён на AES (Advanced Encryption Standard) в том числе из-за низкой нелинейности некоторых булевых функций его S-блоков (узлов замены), и, как следствие, уязвимости к линейному криптоанализу, см. [65,70]. Помимо нелинейности, к криптографическим свойствам относится уравновешенность, критерий распространения, строгий лавинный критерий, корреляционная иммунность, алгебраическая иммунность, см., работу О. А. Логачева, А. А. Сальникова, В. В. Ященко [16], работу Б. Пренеля и др. [73], книгу Г. П. Агибало-ва [1]. Некоторые из перечисленных свойств похожи, например, строгий лавинный критерий является частным случаем критерия распространения; функции, удовлетворяющие критерию распространения максимального порядка, являются максимально нелинейными. Некоторые же свойства могут противоречить друг другу: максимально нелинейные булевы функции от чётного числа переменных не могут быть ни сбалансированными, ни корреляционно иммунными. Зачастую в криптографических приложениях востребованы как раз те булевы функции, которые удовлетворяют нескольким нужным свойствам. Приведём примеры работ, посвященных исследованию как отдельных свойств, так и их сочетаний: нелинейность [64, 76, 77], корреляционная иммунность [78] (см. также обобщение корреляционной иммунности [2]), высокая нелинейность, уравновешенность и корреляционная иммунность [43,57,79], нелинейность и алгебраическая иммунность [8,12,58,81,82].

Бент-функции были предложены О. Ротхаусом в 60-х годах прошлого века, хотя его работа [77] была опубликована только в 1976 г. Известно, что и в СССР в 60-х занимались исследованием бент-функций, В. А. Елисеев и О. П. Степ-ченков называли их минимальными. Интерес к бент-функциям в первую очередь обусловлен их максимальной нелинейностью. Тем не менее, бент-функции не обладают рядом других важных криптографических свойств, например, не являются сбалансированными. Булева функция называется сбалансированной или уравновешенной, если она принимает значения 0 и 1 одинаково часто. Отсутствие сбалансированности препятствует использованию бент-функций как координатных функций во взаимно однозначных ¿'-блоках блочных шифров. Одним из путей решения проблемы является построение криптографических булевых функций путем модификации имеющейся бент-функции, поскольку во многих случаях можно гарантировать, что нелинейность функции по прежнему оста-

нется высокой. Ещё один путь — использование различных обобщений бент-функдий, см., например, полу-бент-функции [46].

Бент-функции в явном виде используются в 8-блоках канадского блочного шифра СА8Т-128 (а также в шифре СА8Т-256). Поскольку данный шифр является сетью Фейстеля, он не требует взаимной однозначности от используемых Б-блоков. Прямая сумма бент-функции и аффинной функции (сумма булевых функций от непересекающихся переменных) используется в хэш-функции НАУАЬ. В качестве бент-функций для НАУАЬ выбраны представители четырёх различных классов аффинной эквивалентности бент-функций от 6 переменных. В поточном шифре ОЯАШ в качестве функции обратной связи в нелинейном регистре сдвига используется прямая сумма квадратичной бент-функции и линейной функции от подмножества битов.

Помимо криптографических приложений, бент-функции связаны с такими комбинаторными объектами как матрицы Адамара (см. [77]), разностные множества (в частности, Р. Л. МакФарланд [66] и Дж. Диллон [50] исследовали бент-функции в терминах разностных множеств), сильно регулярные графы (см. [31]). Последовательности, построенные по бент-функциям, обладают предельно низкой автокорреляцией и взаимной корреляцией, см. работы [71,85].

Несмотря на большой интерес к бент-функциям, до сих пор остаётся множество открытых вопросов в этой области. Неизвестно точное число бент-функций, нет даже его приемлемых оценок. Существует множество различных конструкций бент-функций. Одни из самых первых — класс Мэйорана—МакФарланда [66] и частичное расщепление [50], см. также [37]. Помимо них предложены итеративные конструкции [35,77], алгебраические конструкции (подход к булевым функциями через функции вида 2й) —2)) [34,50-54,62,63]. Исследуются такие подклассы класса бент-функций как нормальные бент-функции [52], однородные бент-функции [44, 68, 74, 83], мономиальные бент-функции [28,34,51,62,63], квадратичные бент-функции [9,50,72]. Предлагаются алгоритмы порождения бент-функций [56,67]. При этом не ясно, насколько известные конструкции покрывают весь класс бент-функций.

Множество статей посвящено обобщениям бент-функций. Большой интерес представляют гипер-бент-функции, которые определяются как функции, находящиеся на максимальном возможном расстоянии от множества собственных мо-номиальных функций [84], см. также работы [10,11,42]. Ценные практические приложения имеют векторные обобщения, см. [69].

Существует не так много обзорных работ и монографий, затрагивающих тему бент-функций: работа Дж. Диллона 1972 г. [49], работа X. Доббертина и

Г. Леандра 2004 г. [55], главы [40] и [41] К. Карле для книги «Boolean Models and Methods in Mathematics, Computer Science and Engineering», монография российских специалистов О. А. Логачева, А. А. Сальникова, С. В. Смышляева, В. В. Ященко, переизданная в 2012 г. [18], книга Т. Кузика и П. Станицы 2009 г. [47], обзоры [23] и [24], а также книги [26] и [27] Н. Н. Токаревой, учебные пособия И. А. Панкратовой [20] и Ю. В. Таранникова [22].

Целью данной работы является исследование метрических свойств класса бент-функций, а именно, исследование расположения двух бент-функций на минимальном возможном расстоянии друг от друга. В работе доказано, что две бент-функции от 2к переменных находятся на минимальном возможном расстоянии 2к тогда и только тогда, когда они различаются на аффинном подпространстве размерности к и обе функции на нём аффинны. Таким образом, расположение бент-функций на минимальном возможном расстоянии связано с аффинностью бент-функций на аффинных подпространствах. В работе получена классификация всех бент-функций на минимальном расстоянии от квадратичной бент-функции. Подсчитано число таких бент-функций. Получена точная верхняя оценка числа бент-функций на расстоянии 2к от произвольной бент-функции от 2к переменных. Введено понятие полной аффинной расщепляемости булевой функции. Доказано, что все полностью аффинно расщепляемые булевы функции являются либо аффинными, либо квадратичными. Доказано, что точная верхняя оценка числа бент-функций на расстоянии 2к от бент-функции от 2к переменных достигается только для полностью аффинно расщепляемых бент-функций, т.е. только для квадратичных бент-функций. Получена нижняя оценка числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана— МакФарланда.

Отметим, что задача нахождения метрической структуры ставилась для различных классов булевых функций, например, для кодов Рида—Маллера, см. [19,61], симметричных функций, см. [7].

Поскольку расположение бент-функций на минимальном возможном расстоянии друг от друга связано с аффинностью булевой функции на аффинном подпространстве, введём необходимые определения.

Линейным подпространством Z?> называется непустое множество L С Zij, если для любых а, Ь 6 L верно, что а 0 6 е L. Обозначим через 5фД где s £ "Щ и D С Щ, сдвиг множества D, а именно s ® D = {s ф х \ х Е D}. Аффинным подпространством 'Щ (или просто подпространством) называется сдвиг линейного подпространства Z?>. Размерностью аффинного подпространства называется размерность соответствующего линейного подпространства. Отметим,

что линейное подпространство также является аффинным подпространством. Булева функция / £ Тп называется аффинной на подпространстве Ь С если

/\ь(х) = (а, х) ® с для некоторых а £ Щ и с £ Ъ2.

Конструкции бент-функций с помощью подпространств и аффинность бент-функции на подпространстве исследовали многие отечественные и зарубежные авторы. В частности, Дж. Диллон [50] (1972 г.) предложил одну из самых первых конструкций бент-функций с помощью пересекающихся только по нулевому элементу линейных подпространств. К. Карле [36] (1994 г.) исследовал сохранение свойства быть бент-функцией при прибавлении характеристической функции аффинного подпространства. В. В. Ященко [30] (1997 г.) изучал представление бент-функции в виде линейного разветвления, т. е. представление булевой функции в виде набора аффинных функций. Он доказал критерий принадлежности булевой функции, заданной в виде линейного разветвления, к классу бент-функций.

Проблемой, напрямую связанной с существованием бент-функций на расстоянии 2fc от заданной бент-функции / £ ЗЗгь занимались X. Доббертин [52] (1994 г.), М. Даум и др. [48] (2003 г.), П. Шарпин [45] (2004 г.) и А. Канто и др. [33] (2006 г.). Перечисленные авторы исследовали бент-функции, не являющиеся нормальными и слабо нормальными. В частности, А. Канто, М. Даум, X. Доббертин и Г. Леандр в 2006 г. показали, что не все бент-функции нормальны или слабо нормальны. Это означает, что не от любой бент-функции / £ Я$2к существует бент-функция на расстоянии 2к.

Более широко метрические свойства, например, спектр возможных расстояний между двумя бент-функциями, связаны с гипотезой, высказанной Н. Н. Токаревой в 2011 г. [80], о том, что любую булеву функцию от 2к переменных степени не больше к можно представить как сумму двух бент-функций от 2к переменных. Данная гипотеза, в частности, связана с асимптотикой мощности класса бент-функций. В. Н. Потапов в работе [21] 2012 г., опираясь на результаты [61], доказал, что расстояния между двумя бент-функциями от 2к переменных в интервале от 2к до 2к+1 — 1 имеют вид 2к+1 — 2где 1 < Ь < к.

Приведём структуру работы.

В первой главе даны необходимые определения. Приводится обзор понятий и известных результатов, связанных с аффинностью булевой функции на подпространстве. В частности, рассматриваются /с-аффинные булевы функции, уровень аффинности булевой функции, обобщенный уровень аффинности булевой функции (М. Л. Буряков, О. А. Логачев, А. А. Сальников, В. В. Ященко),

нормальные, fc-нормальные, слабо нормальные и к-слабо нормальные булевы функции (X. Доббертин, П. Шарпин), представление булевой функции в виде линейного разветвления (О. А. Логачев, А. А. Сальников, В. В. Ященко).

Во второй главе предлагается усиление аффинных свойств булевой функции, вводится понятие полной аффинной расщепляемости. Булева функция называется полностью аффинно расщепляемой порядка к, к > 2, если для любого аффинного подпространства размерности к верно, что функция либо аффин-на на каждом сдвиге этого подпространства, либо не аффинна ни на одном из сдвигов, при этом функция должна быть аффинна хотя бы на одном аффинном подпространстве размерности к. Доказывается

Теорема 1. Пусть f — булева функция от п переменных. Справедливы следующие утверждения.

(i) Функция f полностью аффинно расщепляема порядка к, 2 < к < \п/2] тогда и только тогда, когда / либо аффинная, либо квадратичная;

(tí) Функция f является полностью аффинно расщепляемой порядка к, \п/2] < к < п и не является полностью аффинно расщепляемой порядка k + 1 тогда и только тогда, когда f аффинно эквивалентна функции g(xi, . . . , Хп) = ХгХ2 0 ХЪХА 0 ... 0 X2n-2k-lX2n-2k-

Таким образом, аффинно расщепляемыми могут быть только аффинные и квадратичные булевы функции.

Отметим, что именно полностью аффинно расщепляемые бент-функции от 2к переменных имеют наибольшее число бент-функций на расстоянии 2к (см. пятую главу). Из теоремы 1 также следует, что бент-функция от 2к переменных является полностью аффинно расщепляемой порядка t, 2 < t < к тогда и только тогда, когда она квадратичная, при этом полностью аффинно расщепляемых бент-функций других порядков не существует.

В третьей главе рассматриваются бент-функции на минимальном возможном расстоянии друг от друга. Минимальное возможное расстояние между двумя бент-функциями от 2к переменных равно 2к. Доказывается следующая теорема.

Теорема 2. Пусть fug— бент-функции от 2к переменных. Тогда dist{/, g) = 2к тогда и только тогда, когда / 0 g = Indb, где L — аффинное подпространство размерности к и обе функции аффинны на L.

К. Карле в работе [36] предложил следующую конструкцию бент-функций: пусть / — бент-функция от 2к переменных, L — аффинное подпространство размерности к и / аффинна на L. Тогда / © Indi также является бент-функцией. Таким образом, по теореме 2 все бент-функции на расстоянии 2к от / описываются с помощью приведенной выше конструкции, а именно, все бент-

функции на расстоянии 2к от / можно построить по множеству всех аффинных подпространств размерности к, на которых / аффинна, т.е. имеется прямая связь между бент-функциями на минимальном возможном расстоянии и аффинностью бент-функции на подпространстве.

В главе рассматриваются бент-функции от 4, 6 переменных, а также от 8 переменных степени не больше 3. От любой из этих бент-функций существуют бент-функции на расстоянии 22, 23 и 24 соответственно. Используя аффинную классификацию этих бент-функций, экспериментально найдено число бент-функций на минимальном расстоянии от каждой из них.

Отметим симметрию расстояний между функциями в классе бент-функций *В2к: сНб^/, д 0 1) = 22к - (Цв^/, <?), при этом если д е ЗЗгь то и д ф 1 £ Ъчк, т.е. расстояния симметричны относительно 22к~1. Следовательно, результаты для минимального возможного расстояния естественным образом обобщаются на максимальное возможное, не равное 22к.

В работе [33] были найдены примеры не слабо нормальных бент-функций, это такие бент-функции от 2к переменных, которые не аффинны ни на одном аффинном подпространстве размерности к. Из этого следует, что не от любой бент-функции имеются бент-функции на расстоянии 2к.

В четвертой главе рассматриваются квадратичные бент-функции и бент-функции на минимальном возможном расстоянии от них. Ближайшая бент-функция от любой квадратичной бент-функции от 2к переменных находится на расстоянии 2к. Поскольку известно, что все квадратичные бент-функции от 2к переменных аффинно эквивалентны бент-функции вида /цк(х) = х\Хк+\ Ф х2Хк+2 © • • • то достаточно найти все бент-функции на минимальном рас-

стоянии от /о^, и тогда от любой квадратичной бент-функции все бент-функции на минимальном расстоянии можно построить с помощью аффинных преобразований.

В Теореме 3 найдены базисные матрицы для всех линейных подпространств, на которых /дА: аффинна. Этого достаточно, чтобы в явном виде получить все бент-функции на минимальном расстоянии от любой квадратичной бент-функции. Доказана

Теорема 4. Любая квадратичная бент-функция от 2к переменных имеет ровно 2к • (21 + 1) • ... • (2^ + 1) бент-функций на расстоянии 2к.

Это число можно оценить как

2к(к+1)/2+к <; ■ (21 + 1) • • (2к + 1) < 3 • 2к^к+1^2+к

Заметим, что любая бент-функция на минимальном расстоянии от квадратичной бент-функции аффинно эквивалентна некоторой бент-функции из класса Мэйорана—МакФарланда.

В пятой главе рассматриваются оценки числа функций на расстоянии 2к от заданной бент-функции. Доказана точная оценка сверху.

Теорема 5. Пусть / — бент-функция от 2к переменных. Тогда число бент-фунщий на расстоянии 2к не превосходит 2к(2г + 1) • ... • (2к + 1). При этом данная оценка достигается только на квадратичных бент-функциях.

Достижимость оценки только на квадратичных бент-функциях следует из теоремы 1, т.е. из того, что только квадратичные бент-функции являются полностью аффинно расщепляемыми бент-функциями.

Отметим, что тривиальная оценка сверху числа бент-функций на расстоянии 2к от бент-функции от 2к переменных — это число всех аффинных подпространств Ъ^. Их число можно оценить как

с\к2+к . ок(22к — !)•...• (2к+1 — 1) 0к2+2к 2 < (2^ - 1) (21 - 1) •

Таким образом, доказанная верхняя оценка близка к квадратному корню из тривиальной оценки.

В данной главе также предложена нижняя оценка числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана — МакФарланда.

Теорема 6. Пусть / — бент-функция от 2к переменных, аффинно эквивалентная бент-функции из класса Мэйорана-МакФарланда. Тогда число бент-функций на расстоянии 2к от нее не меньше, чем 22к+1 — 2к.

В Приложении А описано разработанное программное обеспечение для проведения численных экспериментов. С его помощью можно работать с булевыми функциями в различных представлениях (вектор значений, алгебраическая нормальная форма, трейс-представление), двоичными векторами, подпространствами 1*2, полями Галуа СР(2п). Для булевых функций можно подсчитать такие параметры, как степень, коэффициенты Уолша—Адамара, нелинейность, алгебраическую иммунность, а также перебрать все аффинные подпространства, на которых булева функция аффинна.

Публикации. Основные результаты по теме диссертации изложены в 12 печатных изданиях [86 — 97], 5 из которых изданы в журналах, рекомендованных ВАК [86 — 90], 7 — в тезисах и трудах конференций [91 — 97]. Статья [86] опубликована в соавторстве с А. В. Павловым, совместно с которым проводились численные эксперименты, теоретические результаты совместной статьи [86] получены автором лично.

Апробация работы. Основные результаты работы докладывались на следующих конференциях: Международный симпозиум по теории информации (181Т'2011), Современные тенденции в криптографии (СТСгур1'2013), Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (81ВЕСЫУРТ, 2009 — 2013 гг.), Молодежная научная школа по дискретной математике и её приложениям (2009 и 2013 гг.), Мальцевские чтения (2013 г.). Результаты представлялись на семинарах «Дискретный анализ» и «Криптография и криптоанализ» Института математики им. С. Л. Соболева и кафедры Теоретической кибернетики НГУ, семинаре отдела теоретической кибернетики ИМ СО РАН и семинаре «Модели и методы дискретной математики» кафедры дискретной математики МГУ.

Благодарности. Автор выражает глубокую признательность своему научному руководителю Н. Н. Токаревой за постоянное внимание к работе и предложенные интересные направления исследований. Также автор благодарит коллектив комнаты 142 ИМ СО РАН — А. А. Городилову, В. А. Виткуп, Е. П. Корсакову, С. Ю. Филюзина и Г. И. Шушуева — за дружескую атмосферу и отзывчивость, С. В. Августиновича и В. Н. Потапова за интерес к рассматриваемой теме и ценные советы, Д. С. Кротова, взявшего на себя труд прочитать текст диссертации, своего первого научного руководителя А. А. Левина, а также А. А. Евдокимова и других сотрудников лаборатории дискретного анализа Института математики им. С. Л. Соболева СО РАН за поддержку.

Глава 1

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

В этой главе введем базовые определения и приведем обзор известных понятий, связанных с аффинностью булевой функции на подпространстве.

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

Функция вида / : —У Ъ2 называется булевой функцией от п переменных, х = (гг1,..., хп)т еЪ2 — двоичным вектором длины п. Через Тп обозначим множество всех булевых функций от п переменных. Расстоянием Хэмминга между двумя двоичными векторами х,у € Щ называется число координат, в которых х и у различаются. Расстоянием (Иб^/, д) между двумя булевыми функциями

д £ Тп называется число векторов из Щ, на которых значения функций различаются.

Для х, у е Ъ2 определим х 0 у = (х\ 0 ..., хп 0 уп)Т, где 0 — сложение по молулю 2. Также введем аналог скалярного произведения по модулю 2:

(.X, у) = Х1У1 0 Х2У2 © ... 0 Хпуп,

где х^Уг — умножение по модулю 2. Отметим, что (х, у) не является скалярным произведением в полном смысле этого понятия, поскольку не все свойства скалярного произведения верны в двоичном случае. Весом Хэмминга т^и) двоичного вектора и ЕЪ 2 называется число его ненулевых координат. Весом булевой функции / £ Тп называется число векторов из 12^, на которых она принимает значение 1.

Булева функция / £ Тп называется уравновешенной (или сбалансированной), если гу£(/) = 2п~1. Уравновешенность также обобщают на ограничения булевых функций: функция / называется уравновешенной на множестве Д 5 С Ъ2, \0\ четна, если / принимает значение 1 ровно на половине элементов множества И. Ограничение булевой функции / на множество И будем обозначать через

Через fl\Z\tkk, где / е Тп, 0 < к < п, 1 < h < i2 < ... < ik < п и bi,...,bk £ Z2, обозначим функцию из Тп-к-> полученную из / подстановкой вместо Xii:..., Xik констант Ь\,...

Представление булевой функции / Е Тп в виде

п

f(x 1,..., хп) = ад Ф ^^ ^^ aii...ikxii... Х{к, где ао, а^...^ £

fc=l |{ii,...,ife}|=fc

называется алгебраической нормальной формой (АНФ) или полиномом Жегалки-на, Х{г ... Xik — мономом степени к, а^...^, ао — коэффициентами при мономах. Степенью cleg/ функции / называется длина монома наибольшей степени с ненулевым коэффициентом (или 0, если все коэффициенты нулевые). Известно, что любая булева функция может быть представлена в виде АНФ, причём единственным способом.

Производной Daf функции / Е Тп по направлению а; £ Z2 называется функция f{x) © f{xфа). Заметим, что если deg / > 0, то deg Daf < deg / для любого а в Щ.

Непустое множество L С Z2 называется линейным подпространством Z2, если для любых а, Ъ G L верно, что а ф b 6 L. Обозначим через s ф D, где s 6 Z2 и D С Z2, сдвиг множества D, а именно s®D = {s®x\xe D}. Множество U С Z2 называется аффинным подпространством Z2 (или просто подпространством), если оно является сдвигом некоторого линейного подпространства. Размерностью аффинного подпространства называется размерность соответствующего линейного подпространства. Размерность обозначается через dim U. Отметим, что линейное подпространство также является аффинным подпространством. Далее в тексте будем часто опускать слово «аффинное», т.е. будем называть аффинное подпространство просто подпространством. Будем говорить, что L является подпространством U, если L и [/ являются подпространствами Z2 и L С U.

Гранью Z2 называется множество вида

где 1 < ¿1 < ¿2 < • • • < h < п, bi,..., bk £ Z2. Отметим, что грань является подпространством Z2.

Аффинной булевой функцией от п переменных называется булева функция, степень которой не превосходит 1, или, другими словами, функция вида

^а,с(х) = (а, х) ф с для некоторых a £ Z2, с € Z2.

Через Лп обозначается множество всех аффинных булевых функций от п переменных.

Преобразованием Уолша—Адамара функции / Е Тп называется функция : Щ —> Ъ, заданная равенством

щ(у) = Е (-1)/(х)ФМ,

числа называются коэффициентами Уолша—Адамара. Коэффициенты

Уолша—Адамара однозначно определяют функцию /. Также они тесно связаны с расстоянием до аффинных функций:

<ка(/Л>с) = 2п~1 - (-1 Г^Ж/Ы, се%2, у е Щ. Для коэффициентов Уолша—Адамара справедливо равенство Парсеваля:

Список литературы диссертационного исследования кандидат наук Коломеец, Николай Александрович, 2014 год

Литература

1. Агибалов Г. П. Избранные теоремы начального курса криптографии: Учебное пособие / Г. П. Агибалов — Томск: HTJI, 2005. — 116 с.

2. Агибалов Г. П., Панкратова И. А. Элементы теории статистических аналогов дискретных функций с применением в криптоанализе итеративных блочных шифров // Прикладная дискретная математика. — 2010. — №3.— С. 51-68.

3. Буряков М. J1. Алгебраические, комбинаторные и криптографические свойства параметров аффинных ограничений булевых функций: дис. ... канд. физ.-мат. наук. 05.13.19 / Буряков Михаил Леонидович. — М., 2009.

4. Буряков М. Л. О связи уровня аффинности с криптографическими параметрами булевых функций // Дискретная математика. — 2008. — Т. 20, № 2. — С. 3-14.

5. Буряков М. Л. Асимптотические оценки уровня аффинности для почти всех булевых функций // Дискретная математика. — 2008. — Т. 20, № 3. — С. 98107.

6. Буряков М.Л., Логачев O.A. Об уровне аффинности булевых функций // Дискретная математика. — 2005. — Т. 17, № 4. — С. 98-107.

7. Ивченко Г. И., Медведев Ю. И., Миронова В. А. Симметрические булевы функции и их метрические свойства // Математические вопросы криптографии. - 2013. - Т. 4, № 4. - С. 49-63.

8. Коломеец Н. А. О верхней оценке нелинейности некоторого класса булевых функций с максимальной алгебраической иммунностью // Прикладная дискретная математика. — 2013. — № 1. — 14-16.

9. Корсакова Е. П. Классификация графов квадратичных бент-функций от шести переменных // Дискретный анализ и исследование операций. — 2013. — Т. 20, № 5. - С. 45-57.

10. Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишков А. Б. Приближение булевых функций мономиальными // Дискретная математика. — 2006. — Т. 18, № 1. - С. 9-29.

11. Кузьмин А. С., Марков В. Т., Нечаев А. А., Шишкин В. А., Шишков А. Б. Бент-функции и гипербент-функции над полем из 21 элементов // Проблемы передачи информ. - 2008. - Т. 44, № 1. - С. 15-37.

12. Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. — 2006. — Т. 18, № 3. — С. 152-159.

13. Логачев О. А. Нижняя оценка уровня аффинности для почти всех булевых функций // Дискретная математика. — 2008. — Т. 20, № 4. — С. 85-88.

14. Логачев О. А. О значениях уровня аффинности для почти всех булевых функций // Прикладная дискретная математика. — 2010. Т. 9, № 3. С. 17-21.

15. Логачев О. А., Сальников А. А., Ященко В. В. Бент-функции на конечной абелевой группе // Дискретная математика. — 1997. — Т. 9, № 4. — С. 3—20.

16. Логачев О. А., Сальников А. А., Ященко В. В. Криптографические свойства дискретных функций // Материалы конференции «Московский университет и развитие криптографии в России», МГУ, 2002. М.: МЦНМО, 2003. С. 174199.

17. Логачев О. А., Сальников А. А., Ященко В. В. Комбинирующие /с-аффинные функции // Математика и безопасность информационных технологий. М.: МЦНМО, 2004. С. 176-178.

18. Логачев О. А. Булевы функции в теории кодирования и криптологии. 2-е изд. / О. А. Логачев, А. А. Сальников, С. В. Смышляев, В. В. Ященко. — М.: МЦНМО, 2012. - 584 с.

19. Мак-Вильямс Ф. Дж. Теория кодов, исправляющих ошибки: Пер. с англ. / Ф. Дж. Мак-Вильямс, Н. Дж. А. Слоэн. — М.: Радио и связь, 1979. — 744 с.

20. Панкратова И. А. Булевы функции в криптографии: Учебное пособие / Томск: ТГУ, 2014. - 88 с.

21. Потапов В. Н. Спектр мощностей компонент корреляционно-иммунных функций, бент-функций, совершенных раскрасок и кодов // Проблемы передачи информ. — 2012. - Т. 48, № 1. — С. 54-63.

22. Таранников Ю. В. Комбинаторные свойства дискретных структур и приложения к криптологии / М: МЦНМО, 2011. — 152 с.

23. Токарева Н. Н. Бент-функции: результаты и приложения. Обзор работ // Прикладная дискретная математика. — 2009. — №. 1. — С. 15—37.

24. Токарева Н. Н. Обобщения бент-функций. Обзор работ // Дискретный анализ и исследование операций. — 2010. — Т. 17, № 1. — С. 34—64.

25. Токарева Н. Н. Группа автоморфизмов множества бент-функций // Дискретная математика. — 2010. — Т. 22, № 4. — С. 34^2.

26. Токарева Н. Н. Нелинейные булевы функции: бент-функции и их обобщения / Saarbrucken: LAP LAMBERT Academic Publishing, 2011.- 180 с.

27. Токарева H. Н. Симметричная криптография. Краткий курс / Новосибирск: НГУ, 2012. - 234 с.

28. Фролова А. А. Существенная зависимость бент-функций Касами от произведений переменных // Дискретный анализ и исследование операций. — 2013.

- Т. 20, № 1. - С. 77-92.

29. Черемушкин А. В. Методы аффинной и линейной классификации двоичных функций. Труды по дискретной математике. Т. 4. / М.: Физматлит, 2001. — С. 273-314.

30. Ященко В. В. О критерии распространения для булевых функций и о бент-функциях // Проблемы передачи информации. — 1997. — Т. 33, № 1. — С 75— 86.

31. Bernasconi A., Codenotti В., VanderKam J. М. A characterization of bent functions in terms of strongly regular graphs // IEEE Trans. Computers. — 2001.

- V. 50, N 9. - P. 984-985.

32. Braeken A. Cryptographic properties of Boolean functions and S-boxes // Ph. D. thesis, Katholieke Universiteit Leuven, Leuven, Belgium. 2006.

33. Canteaut A., Daum M., Dobbertin H., Leander G. Finding nonnormal bent functions // Discrete Applied Mathematics. - 2006. - V. 154, N 2. — P. 202218.

34. Canteaut A., Charpin P., Kuyreghyan G. A new class of monomial bent functions // Finite Fields and Applications. - 2008. - V. 14, N 1. - P. 221-241.

35. Canteaut A., Charpin P. Decomposing bent functions // IEEE Trans. Inform. Theory. - 2003. - V. 49. - P. 2004-2019.

36. Carlet C. Two new classes of bent functions // Advances in Cryptology — EUROCRYPT'93 Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993. P. 77-101. Proc. (Lecture Notes in Computer Science. 1994. V. 765.)

37. Carlet C. Generalized Partial Spreads // IEEE Trans. Inform. Theory. — 1995. — V. 41, N5. -P. 1482-1487.

38. Carlet C., Dobbertin H., Leander G. Normal Extensions of Bent Functions IEEE Trans. Inform. Theory. - 2004. - V. 50, N 11. - P. 2880-2885.

39. Carlet C. Recursive Lower Bounds on the Nonlinearity Profile of Boolean Functions and Their Applications // IEEE Trans. Inform. Theory. — 2008. — V. 54, N 3. P. 1262-1272.

40. Carlet C. Boolean functions for cryptography and error correcting codes // Boolean Models and Methods in Mathematics, Computer Science and Engineering / Eds. P. Hammer, Y. Crama. Cambridge Univ. Press, 2010. Chapter 8. P. 257 - 397.

41. Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science and Engineering / Eds. P. Hammer, Y. Crama. Cambridge Univ. Press, 2010. Chapter 9. P. 398 - 472.

42. Carlet C., Gaborit P. Hyper-bent functions and cyclic codes // J. Combin. Theory. Ser. A. - 2006. - V. 113, N 3. - P. 466-482.

43. Carlet C., Klapper A. Upper bounds on the numbers of resilient functions and of bent functions // 23rd Symposium on Information Theory, Benelux, Belgium. May, 2002. P. 307-314. Proc.

44. Charnes C., Rotteler M., Beth T. Homogeneous bent functions, invariants, and designs // Designs, Codes and Cryptography. — 2002. — V. 26, N 1-3. P. 139154.

45. Charpin P. Normal Boolean functions // Journal of Complexity. — 2004. — V. 20. P. 245-265.

46. Chee S., Lee S., Kim K. Semi-bent Functions // Advances in Cryptology — ASIACRYPT'94 — 4th International Conference on the Theory and Applications

of Cryptology, Wollongong, Australia. November 28 - December 1, 1994. Proc. Berlin: Springer. 1995. P. 107-118. (Lecture Notes in Computer Science. V. 917.)

47. Cusick T. W., Stanica P. Cryptographic Boolean Functions and Applications. Academic Press. 2009. — 240 p.

48. Daum M., Dobbertin H., Leander G. An algorithm for checking normality of Boolean functions // Discrete Applied Mathematics. — 2003. — P. 133-143.

49. Dillon J. F. A survey of bent functions // The NSA Technical Journal. — 1972. — P. 191-215.

50. Dillon J. F. Elementary Hadamard Difference sets // Ph. D. Thesis, Univ. of Maryland, 1974.

51. Dillon J. F., Dobbertin H. New cyclic difference sets with Singer parameters // Finite Fields and Their Applications. - 2004. - V. 10, N. 3. - P. 342-389.

52. Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // Fast Software Encryption Int. Workshop, Leuven, Belgium, December 14-16, 1994. P. 61-74. Proc. (Lecture Notes in Computer Science. 1994. V. 1008.)

53. Dobbertin H. Almost perfect nonlinear power functions over GF(2n): the Niho case // Inform, and Comput. - 1999. - V. 151, N 1-2. P. 57-72.

54. Dobbertin H. Almost perfect nonlinear power functions over GF(2n): a new case for n divisible by 5 // Finite Fields and Applications FQ5, Augsburg, Germany, 2000. Proc. Springer. Eds: D. Jungnickel, H. Niederreiter. P. 113-121.

55. Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and their applications. - SETA 2004. Third Int. conference, Seul, Korea. October 24-28, 2004. Berlin: Springer, 2005. P. 1-29. (Lecture Notes in Computer Science. V. 3486.)

56. Dobbertin H., Leander G. Cryptographer's Toolkit for Construction of 8-Bit Bent Functions // Cryptology ePrint Archive, Report 2005/089, available at http://eprint.iacr.org/.

57. Fedorova M., Tarannikov Yu. On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Spectral Matrices // INDOCRYPT 2001. P. 254266. (Lecture Notes in Computer Science. V. 2247.)

58. Flori J.-P., Randriam H., Cohen G., Mesnager S. On a Conjecture about Binary Strings Distribution // Sequences and Their Applications (SETA 2010). Paris, France. September, 13-17, 2010. P. 346-358. Proc. (Lecture Notes in Computer Science. 2010. V. 6338.)

59. Gangopadhyay S, Sharma D. On construction of non-normal Boolean functions Cryptology ePrint Archive, Report 2006/118, available at http://eprint.iacr.org/.

60. Hou X. D. Cubic bent functions // Discrete Mathematics. - 1998. - V. 189. — P. 149-161.

61. Kasami T., Tokura N. On the Weight Structure of Reed-Muller Codes // IEEE Trans. Inform. Theory. - 1970. - V. 16, N 6. - P. 752-759.

62. Langevin P., Leander G. Monomial bent functions and Stickelberger's theorem // Finite Fields and Applications. - 2008. - V. 14. P. 727-742.

63. Leander N. G. Monomial bent functions // IEEE Trans. Inform. Theory. — 2006.

- V. 52, N 2. P. 738-743.

64. Maitra S., Sarkar P. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables // IEEE Trans. Inform. Theory. - 2002. - V. 48, N 9.

- P. 2626-2630.

65. Matsui M. Linear cryptanalysis method for DES cipher // Advances in Cryptology — EUROCRYPT'93. Workshop on the theory and application of cryptographic techniques, Lofthus, Norway. May 23-27, 1993. Proc. Berlin: Springer, 1994. P. 386-397. (Lecture Notes in Computer Science. V. 765.)

66. McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory, Ser. A. - 1973. - V. 15. - P. 1-10.

67. Meng Q., Yang M. C., Zhang H. A novel algorithm enumerating bent functions // Cryptology ePrint Archive, Report 2004/274, available at http://eprint.iacr.org/.

68. Meng Q., Zhang H., Yang M. C., Cui J. On the degree of homogeneous bent functions // Discrete Applied Mathematics. — 2007. V. 155, N 5. — P. 665-669.

69. Nyberg K. Perfect nonlinear S-boxes // Advances in cryptology — EUROCRYPT '1991. Int. conference on the theory and application of

cryptographic techniques, Brighton, UK. April 8-11, 1991. Proc. Berlin: Springer, 1991. P. 378-386. (Lecture Notes in Computer Science. V. 547.)

70. Nyberg K. New bent mappings suitable for fast implementation // Fast software encryption'93, Cambridge, December 9-11, 1993. Proc. Berlin: Springer, 1994. P. 179-184. (Lecture Notes in Computer Science. V. 809.)

71. Olsen J. D., Scholtz R. A., Welch L. R. Bent-function sequences // IEEE Trans. Inform. Theory. - 1982. - V. 28, N 6. - P. 858-864.

72. Preneel B. Analysis and design of cryptographic hash functions // Ph. D. thesis, Katholieke Universiteit Leuven, Leuven, Belgium. 1993.

73. Preneel B., Van Leekwijck W., Van Linden L., Govaerts R., Vandevalle J. Propogation characteristics of Boolean functions // Advances in cryptology — EUROCRYPT'1990. Int. conference on the theory and application of cryptographic techniques (Aarhus, Denmark. May 21-24, 1990). Proc. Berlin: Springer, 1991. P. 161-173. (Lecture Notes in Computer Science. V. 473.)

74. Qu C., Seberry J., Pieprzyk J. Homogeneous bent functions // Discrete Appl. Math. - 2000. - V. 102, N 1-2. P. 133-139.

75. Riera C., Parker M. G. Generalised Bent Criteria for Boolean Functions (I) // IEEE Trans. Inform. Theoiy. - 2006. - V. 52, N 9. - P. 4142-4159.

76. Rodier F. Asymptotic nonlinearity of Boolean functions // Designs, Codes and Cryptography. - 2006. - V. 40, N 1. - P. 59-70.

77. Rothaus O. On bent functions // J. Combin. Theory, Ser. A. - 1976. - V. 20, N 3. - P. 300-305.

78. Siegentaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications // IEEE Trans. Inform. Theory. — 1984. — V. 30, N 5. P. 776-780.

79. Tarannikov Yu. On Resilient Boolean Functions with Maximal Possible Nonlinearity // INDOCRYPT 2000 — First International Conference in Cryptology in India, Calcutta, India. December 10-13, 2000. Proc. Springer. 2000. P. 19-30. (Lecture Notes in Computer Science. V. 1977.)

80. Tokareva N. On the number of bent functions from iterative constructions: lower bounds and hypothesis // Adv. Math. Commun. — 2011. — V. 5, N 4. — P. 609621.

81. Tu Z., Deng Y. A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity // Designs, Codes and Cryptography. - 2011. - V. 60, N 1. - P. 1-14.

82. Tu Z., Deng Y. A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity // Cryptology ePrint Archive, Report 2009/272, available at http: //eprint. iacr . org/.

83. Xia Т., Seberry J., Pieprzyk J., Charnes C. Homogeneous bent functions of degree n in 2n variables do not exist for n > 3 // Discrete Applied Mathematics. — 2004. -V. 142, N 1-3.-P. 127-132.

84. Youssef A., Gong G. Hyper-bent functions // Advances in cryptology — EUROCRYPT'2001. Int. conference on the theory and application of cryptographic techniques, Innsbruk, Austria. May 6-10, 2001. Proc. Berlin: Springer, 2001. P. 406-419. (Lecture Notes in Computer Science. V. 2045.)

85. Zhang В., Lti S. I/O correlation properties of bent functions // Science in China Series E: Technological Sciences. - 2000. - V. 43, N 3. - P. 282-286.

Публикации автора по теме диссертации

86. Коломеец Н. А., Павлов А. В. Свойства бент-функций, находящихся на минимальном расстоянии друг от друга // Прикладная дискретная математика. - 2009. - № 4. - С. 5-20.

87. Коломеец Н. А. Перечисление бент-функций на минимальном расстоянии от квадратичной бент-функции // Дискретный анализ и исследование операций. - 2012. - Т. 19, № 1. — С. 41-58 (Перевод: Kolomeets N. А. Enumeration of the bent functions of least deviation from a quadratic bent function // Journal of Applied and Industrial Mathematics. — 2012. — V. 6, N 3. -P. 306-317.).

88. Коломеец H. А. Пороговое свойство квадратичных булевых функций // Дискретный анализ и исследование операций. — 2014. — Т. 21, № 2. — С. 52-58.

89. Kolomeec N. A. On a property of quadratic Boolean functions // Математические вопросы криптографии. — 2014. — Т. 5, № 2. — С. 79-85.

90. Коломеец Н. А. Верхняя оценка числа бент-функций на расстоянии 2к от произвольной бент-функции от 2к переменных // Прикладная дискретная математика. — 2014. — № 3.

91. Kolomeec N. A., Pavlov A. V. Bent functions on the minimal distance // IEEE Region 8 International Conference on Computational Technologies in Electrical and Electronics Engineering (SIBIRCON 2010), Irkutsk, Russia. July, 11-15, 2010. P. 145-149.

92. Kolomeec N. A. Constructions of bent functions on the minimal distance from the quadratic bent function // Proc. IEEE International Symposium on Information Theory (ISIT'2011). Saint-Petersburg, Russia. July, 31 - August, 5, 2011. P. 647-651.

93. Коломеец H. А. Количество бент-фуикций на минимальном расстоянии от квадратичной бент-функции // Прикладная дискретная математика. Приложение. - 2011. - № 4. - С. 9-11.

94. Коломеец Н. А., Павлов А. В. Boolean Functions - система для работы с булевыми функциями // Прикладная дискретная математика. Приложение. -2011.-№4.-С. 67-68.

95. Коломеец Н. А. Об аффинности булевых функций на подпространствах и их сдвигах // Прикладная дискретная математика. Приложение. — 2013. — №6.-С. 15-16.

96. Kolomeec N. A. On a property of quadratic Boolean functions // Proc. of «Mal'tsev meeting» (Novosibirsk, Russia. November, 11-15. 2013). P. 41.

97. Коломеец H. А. Верхняя оценка числа бент-функций на расстоянии 2к от произвольной бент-функции от 2к переменных // Прикладная дискретная математика. Приложение. — 2014. — № 7.