«БЕНТ-ФУНКЦИИ, АФФИННЫЕ НА ПОДПРОСТРАНСТВАХ, И ИХ МЕТРИЧЕСКИЕ СВОЙСТВА ...»

Федеральное государственное бюджетное учреждение наук

и

Институт математики им. С. Л. Соболева

Сибирского отделения Российской академии наук

(ИМ СО РАН)

На правах рукописи

УДК 519.7

Коломеец Николай Александрович

БЕНТ-ФУНКЦИИ, АФФИННЫЕ НА ПОДПРОСТРАНСТВАХ, И ИХ

МЕТРИЧЕСКИЕ СВОЙСТВА

Специальность 01.01.09 — «Дискретная математика и математическая кибернетика»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель:

к.ф.-м.н., с.н.с.

Токарева Н.Н.

Новосибирск — Оглавление Введение...................................... 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 от функции из B2.. 5.1 Верхняя оценка для произвольной бент-функции........... 5.2 Нижняя оценка для бент-функций из класса Мэйорана—МакФарланда Заключение.................................... Литература.................................... A Программное обеспечение для проведения численных экспериментов A.1 Двоичные векторы............................. A.2 Линейные подпространства....................... A.3 Поля Галуа................................. A.4 Итераторы................................. A.5 Представления булевых функций.................... A.5.1 Вектор значений.......................... A.5.2 Алгебраическая нормальная форма................ A.5.3 Трейс-форма............................. A.6 Бент-функции............................... Введение

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

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

Функция вида : Z Z2 называется булевой функцией от переменных, Z2 — двоичным вектором длины, = (1,..., ). Через обозначим множество всех булевых функций от переменных. Для, Z определим = (1 1,..., ), где — сложение по молулю 2. Введём аналог скалярного произведения по модулю 2:

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

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

Расстоянием Хэмминга между двумя двоичными векторами, Z называется число координат, в которых и различаются. Расстоянием между двумя булевыми функциями, называется расстояние Хэмминга между векторами их значений, оно обозначается как dist(, ). Булевы функции, называются аффинно эквивалентными, если существует невырожденная двоичная матрица размера, вектор Z и аффинная функция, такие что Нелинейностью булевой функции называется расстояние от до множества всех аффинных функций:

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

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

Преобразованием Уолша—Адамара функции называется функция :

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

Поскольку dist(,,1 ) = 2 dist(,,0 ), то справедливо Для коэффициентов Уолша—Адамара справедливо равенство Парсеваля:

Из него следует, что 21 2/21. Так как коэффициенты Уолша—Адамара являются удобным инструментом для подсчёта нелинейности, бент-функции часто определяют следующим образом: 2 называется бент-функцией, если | ()| = 2 для всех Z2. Множество всех бент-функций от 2 переменных обозначают через B2. Оба приведенных определения бент-функций являются эквивалентными.

Нелинейность — одно из важнейших криптографических свойств булевых функций. В частности, алгоритм симметричного шифрования 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-x годах прошлого века, хотя его работа [77] была опубликована только в 1976 г. Известно, что и в СССР в 60-x занимались исследованием бент-функций, В. А. Елисеев и О. П. Степченков называли их минимальными. Интерес к бент-функциям в первую очередь обусловлен их максимальной нелинейностью. Тем не менее, бент-функции не обладают рядом других важных криптографических свойств, например, не являются сбалансированными. Булева функция называется сбалансированной или уравновешенной, если она принимает значения 0 и 1 одинаково часто. Отсутствие сбалансированности препятствует использованию бент-функций как координатных функций во взаимно однозначных -блоках блочных шифров. Одним из путей решения проблемы является построение криптографических булевых функций путем модификации имеющейся бент-функции, поскольку во многих случаях можно гарантировать, что нелинейность функции по прежнему останется высокой. Ещё один путь — использование различных обобщений бентфункций, см., например, полу-бент-функции [46].

Бент-функции в явном виде используются в S-блоках канадского блочного шифра CAST-128 (а также в шифре CAST-256). Поскольку данный шифр является сетью Фейстеля, он не требует взаимной однозначности от используемых S-блоков. Прямая сумма бент-функции и аффинной функции (сумма булевых функций от непересекающихся переменных) используется в хэш-функции HAVAL. В качестве бент-функций для HAVAL выбраны представители четырёх различных классов аффинной эквивалентности бент-функций от 6 переменных.

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

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

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

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

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

[19, 61], симметричных функций, см. [7].

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

Линейным подпространством Z называется непустое множество Z, если для любых, верно, что. Обозначим через, где Z и Z2, сдвиг множества, а именно = { | }. Аффинным подпространством Z (или просто подпространством) называется сдвиг линейного подпространства Z. Размерностью аффинного подпространства называется размерность соответствующего линейного подпространства. Отметим, что линейное подпространство также является аффинным подпространством.

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

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

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

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

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

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

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

(ii) Функция является полностью аффинно расщепляемой порядка, /2 < и не является полностью аффинно расщепляемой порядка + 1 тогда и только тогда, когда аффинно эквивалентна функции Таким образом, аффинно расщепляемыми могут быть только аффинные и квадратичные булевы функции.

Отметим, что именно полностью аффинно расщепляемые бент-функции от 2 переменных имеют наибольшее число бент-функций на расстоянии 2 (см.

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

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

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

К. Карле в работе [36] предложил следующую конструкцию бент-функций:

пусть — бент-функция от 2 переменных, — аффинное подпространство Z2 размерности и аффинна на. Тогда также является бентфункцией. Таким образом, по теореме 2 все бент-функции на расстоянии 2 от описываются с помощью приведенной выше конструкции, а именно, все бентфункции на расстоянии 2 от можно построить по множеству всех аффинных подпространств размерности, на которых аффинна, т.е. имеется прямая связь между бент-функциями на минимальном возможном расстоянии и аффинностью бент-функции на подпространстве.

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

Отметим симметрию расстояний между функциями в классе бент-функций т.е. расстояния симметричны относительно 221. Следовательно, результаты для минимального возможного расстояния естественным образом обобщаются на максимальное возможное, не равное 22.

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

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

В Теореме 3 найдены базисные матрицы для всех линейных подпространств, на которых 0 аффинна. Этого достаточно, чтобы в явном виде получить все бент-функции на минимальном расстоянии от любой квадратичной бентфункции. Доказана Теорема 4. Любая квадратичная бент-функция от 2 переменных имеет ровно 2 · (21 + 1) ·... · (2 + 1) бент-функций на расстоянии 2.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях: Международный симпозиум по теории информации (ISIT’2011), Современные тенденции в криптографии (CTCrypt’2013), Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (SIBECRYPT, 2009 — 2013 гг.), Молодежная научная школа по дискретной математике и её приложениям (2009 и 2013 гг.), Мальцевские чтения (2013 г.). Результаты представлялись на семинарах «Дискретный анализ» и «Криптография и криптоанализ» Института математики им.

С. Л. Соболева и кафедры Теоретической кибернетики НГУ, семинаре отдела теоретической кибернетики ИМ СО РАН и семинаре «Модели и методы дискретной математики» кафедры дискретной математики МГУ.

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

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

Функция вида : Z Z2 называется булевой функцией от переменных, = (1,..., ) Z2 — двоичным вектором длины. Через обозначим множество всех булевых функций от переменных. Расстоянием Хэмминга между двумя двоичными векторами, Z называется число координат, в которых и различаются. Расстоянием dist(, ) между двумя булевыми функциями, называется число векторов из Z, на которых значения функций различаются.

молулю 2. Также введем аналог скалярного произведения по модулю 2:

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

Булева функция называется уравновешенной (или сбалансированной), если ( ) = 21. Уравновешенность также обобщают на ограничения булевых функций: функция называется уравновешенной на множестве, Z, || чётна, если принимает значение 1 ровно на половине элементов множества.

Ограничение булевой функции на множество будем обозначать через |.

1,..., Z2, обозначим функцию из, полученную из подстановкой Представление булевой функции в виде называется алгебраической нормальной формой (АНФ) или полиномом Жегалкина, 1... — мономом степени, 1..., 0 — коэффициентами при мономах.

Степенью deg функции называется длина монома наибольшей степени с ненулевым коэффициентом (или 0, если все коэффициенты нулевые). Известно, что любая булева функция может быть представлена в виде АНФ, причём единственным способом.

Производной функции по направлению Z называется функция () (). Заметим, что если deg > 0, то deg < deg для любого Непустое множество Z называется линейным подпространством Z, если для любых, верно, что. Обозначим через, где Множество Z называется аффинным подпространством Z (или просто подпространством), если оно является сдвигом некоторого линейного подпространства. Размерностью аффинного подпространства называется размерность соответствующего линейного подпространства. Размерность обозначается через dim. Отметим, что линейное подпространство также является аффинным подпространством. Далее в тексте будем часто опускать слово «аффинное», т.е. будем называть аффинное подпространство просто подпространством. Будем говорить, что является подпространством, если и являются подпространствами Z и.

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

Преобразованием Уолша—Адамара функции называется функция :

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

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

Из равенства Парсеваля следует, что Для произвольной булевой функции, аффинного подпространства, и, Z справедлива следующая формула:

Также для произвольных, верна формула свертки:

Бент-функцией называется булева функция от 2 переменных, все коэффициенты Уолша—Адамара которой по модулю равны 2. Множество всех бентфункций от 2 переменных обозначается через B2. Заметим, что для бентфункции B2 справедливо С бент-функцией связывают дуальную функцию, определяемую равенством Функция тоже является бент-функцией. Для бент-функции формула (1.1) имеет более простой вид:

где — линейное подпространство Z2,, Z2.

Булевы функции, называются аффинно эквивалентными, если существует невырожденная двоичная матрица размера, вектор Z и аффинная функция, такие что Преобразование ( ) () функции называется аффинным преобразованием булевой функции. Отметим, что для произвольных, и для произвольного аффинного преобразования (,, ) справедливо Класс бент-функций замкнут относительно аффинных преобразований булевой функции.

Булева функция называется квадратичной, если её степень равна 2. Для квадратичных функций справедлива теорема Диксона: любую квадратичную булеву функцию можно привести невырожденным аффинным преобразованием координат (преобразование вида ( ), где —невырожденная двоичная матрица, — двоичный вектор) к виду Через, Z, обозначим булеву функцию от переменных, принимающую значение 1 на всех элементах множества (и только на них).

Определение 1. Функция аффинна на подпространстве, если Для бент-функции B2 справедлива следующая конструкция. Пусть — подпространство Z2 размерности и аффинна на. Тогда Данная конструкция была предложена К. Карле в работе [36].

Более подробную информацию о булевых и бент-функциях можно узнать в книгах [18, 26, 47].

1.2 Аффинность булевых функций на подпространстве Рассмотрим существующие понятия, связанные с аффинностью булевой функции на подпространстве.

Определение 2. Функция называется -аффинной, если для некоторых Заметим, что функция является -аффинной, если она аффинна на некоторой грани размерности. Уровнем аффинности называется минимальное возможное, такое что является -аффинной. Эти определения ввели О. А. Логачев, А. А. Сальников и В. В. Ященко в работе [17] 2004 г. (труды конференции «Математика и безопасность информационных технологий» 2003 г.). Аффинные функции обладают нулевым уровнем аффинности (и только они). Также уровень аффинности не превышает 1. В работе М. Л. Бурякова и О. А. Логачева [6] 2005 г. было доказано, что уровнем аффинности 1 обладают исключительно квадратичные булевы функции, АНФ которых содержит все мономы степени 2.

М. Л. Буряков в работе [4] доказал, что задача нахождения уровня аффиности булевой функции, если число мономов в её АНФ не превосходит, где – некоторая константа, является -трудной. Более подробную информацию об уровне аффинности см. в работе М. Л. Бурякова [5] (оценки уровня аффинности для почти всех булевых функций) и его кандидатской диссертации [3].

Определение 3. Функция называется -нормальной (-слабо нормальной), если она постоянна (аффинна) на некотором подпространстве размерности Определение 4. Функция называется нормальной (слабо нормальной), если она /2-нормальна (/2-слабо нормальна).

Через обозначена целая часть сверху числа R.

Определение нормальности было предложено Х. Доббертином в работе [52] 1994 г. Он ввел его для функций от чётного числа переменных. Данное понятие тесно связано с классом бент-функций. Многие первичные конструкции бент-функций (класс Мэйорана—МакФарланда, один из подклассов частичного расщепления), а также все бент-функции от двух, четырех и шести переменных являются нормальными. Вопрос о существовании бент-функций, не являющихся нормальными, на тот момент оставался открытым. П. Шарпин в 2004 г. в работе [45] обобщила определение нормальности на случай произвольного числа переменных и ввела понятие -нормальности. В 2006 г. вышла работа А. Канто, М. Даума, Х. Доббертина и Г. Леандра [33], где авторы привели пример бентфункции от 10 переменных, не являющейся нормальной и бент-функции от переменных, не являющейся слабо нормальной (обе бент-функции — мономиальные функции с показателем Касами). Также в этой работе была предложена конструкция, позволяющая по произвольной не нормальной (не слабо нормальной) бент-функции от 2 переменных построить не нормальную (не слабо нормальную) бент-функцию от 2 + 2 переменных.

Отметим, что любая -нормальная функция является -слабо нормальной.

Любая -аффинная функция является ( )-слабо нормальной.

Обобщённым уровнем аффинности называется минимальное возможное, такое что аффинна на подпространстве размерности. Оценками обобщённого уровня аффинности для почти всех булевых функций занимался О. А. Логачев, см. работы [13, 14]. В работе [14] доказано, что для почти всех булевых функций от переменных обобщённый уровень аффинности лежит в интервале 1.3 Булевы функции, аффинные на подпространстве и всех В этом разделе рассмотрим аффинность булевой функции на подпространстве и всех его сдвигах.

Определение 5. Функция сильно -аффинна, если для некоторых 1 <... < и произвольных 1,..., Z2 функция 11,..., аффинна.

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

Определение 6. Булева функция задана в виде линейного разветвления, такие что Подробную информацию об этом представлении можно найти в монографии [18]. Представлением бент-функций в виде линейного разветвления занимался В. В. Ященко в работе [30] 1997 г.

Нетрудно доказать следующую лемму.

Лемма 1. Пусть аффинна на некотором подпространстве размерности и на каждом его сдвиге. Тогда она аффинно эквивалентна булевой функции, представленной в виде линейного разветвления с параметром, а именно функции Доказательство данной леммы можно найти, например, в работе [33].

Введем естественное обобщение приведенного выше определения.

Определение 7. Функция является аффинно расщепляемой по подпространству, если функция аффинна на каждом сдвиге.

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

В следующей главе рассмотрим еще более сильное понятие аффинности.

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

Результаты главы опубликованы в работах [90,97]. В работах [88,89,96] опубликованы результаты о полностью аффинно расщепляемых булевых функциях порядка /2, где — число переменных.

Определение 8. Функция называется полностью аффинно расщепляемой порядка, 2, если она аффинна на некотором подпространстве Z размерности и аффинно расщепляема по всем подпространствам размерности, на которых она аффинна.

Порядок 0 и 1 рассматривать не имеет смысла, поскольку тогда бы все булевы функции удовлетворяли определению.

Тривиально доказывается следующие утверждение.

Утверждение 1. Пусть, — аффинно эквивалентные булевы функции.

Тогда является полностью аффинно расщепляемой порядка тогда и только тогда, когда является полностью аффинно расщепляемой порядка.

Все аффинные и квадратичные булевы функции обладают следующим свойством.

Утверждение 2. Пусть — аффинная или квадратичная. Тогда если аффинна на подпространстве Z, то аффинна на каждом сдвиге.

Доказательство. Пусть Z. Функция аффинна на тогда и только тогда, когда ( ) аффинна на. Отметим, что ( ) = () (), при этом из условия утверждения следует, что deg 1. Следовательно, аффинна на тогда и только тогда, когда аффинна на.

Докажем вспомогательные леммы об аффинности булевой функции на подпространстве.

Лемма 2. Пусть аффинна на подпространстве Z ненулевой размерности. Тогда для некоторого подпространства и, таких что Доказательство. Без ограничения общности можно считать, что — линейное подпространство Z. Тогда для любого Z решением системы уравнений, = 0, является либо все множество, либо его подпространство размерности dim 1. Лемма доказана.

Лемма 3. Пусть, — подпространство Z и постоянна на. Тогда аффинна на подпространстве ( ), Z2 тогда и только тогда, когда постоянна на.

Доказательство. Без ограничения общности можно считать, что — линейное подпространство Z. (=) Если постоянна на ( ), то утверждение очевидно. Пусть очевидно. Пусть 1 = 2, т. е. 2 = 1 1. Рассмотрим. Для некоторого Утверждение 3. Если булева функция является полностью аффинно расщепляемой порядка, то она также полностью аффинно расщепляема порядка для Для его доказательства достаточно воспользоваться следующей леммой.

Лемма 4. Пусть является полностью аффинно расщепляемой порядка.

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

База индукции dim = 0 очевидно следует из условия леммы.

Предположим, что для всех подпространств размерности меньшей, чем, 1, утверждение леммы верно. Докажем, что оно верно и для размерности Представим как ( ), где — подпространство размерности,. Тогда по предположению индукции существует размерности, и аффинна на. Без ограничения общности можно считать, что | = 0, поскольку прибавление аффинной функции не влияет на наличие или отсутствие аффинности. Тогда по лемме 3 верно, что | =, где Z2. Поскольку по условию леммы аффинна на, то по лемме 2 существует аффинное | =. А так как | = 0, то по лемме 3 функция аффинна на линейном подпространстве ( ) размерности, которое содержит.

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

Лемма 5. Пусть, > 2, и = {,,, } — подпространтво Z размерности 2. Тогда аффинна на тогда и только тогда, когда Доказательство леммы очевидно.

Лемма 6. Пусть, > 2. Тогда существует подпространство размерности 2, на котором аффинна.

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

В алгебраической нормальной форме может присутствовать четыре монома степени 2 и 3: 1 2 3, 1 2, 1 3 и 2 3. Рассмотрим два случая.

Случай 1. Моном 1 2 3 не присутствует. Имеем два подслучая.

1. Не все мономы степени 2 присутствуют в АНФ. Тогда, очевидно, у присутствующих мономов есть общая переменная, 1 3. Следовательно, 0 — аффинная, т.е. подпространство найдено.

2. Мономы 1 2, 1 3 и 2 3 присутствуют в АНФ. Заметим, что 1 2 1 2 3 = 1 (2 3 ) 2 3, поэтому аффинна на подпространстве = Случай 2. Моном 1 2 3 присутствует. Также имеем два подслучая.

1. В АНФ нет мономов степени 2. Тогда, очевидно, 0 — аффинная. Подпространство найдено.

2. В АНФ есть моном степени 2, без ограничения общности положим, что там присутствует 1 2. Тогда 1 аффинна, поскольку у неё 1 2 3 и сократятся, а мономы 1 3 и 2 3 содержат 3.

Приведенная лемма также следует из того, что уровнем аффинности обладают только квадратичные функции, содержащие все мономы степени (М. Л. Буряков, О. А. Логачев, [6]).

Лемма 7. Пусть является полностью аффинно расщепляемой порядка 2. Тогда либо аффинная, либо квадратичная.

Доказательство. Воспользуемся индукцией по числу переменных.

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

Предположим, что если, < является полностью аффинно расщепляемой порядка 2, то deg 2. Докажем, что deg 2.

Рассмотрим линейное подпространство Тогда все сдвиги можно представить следующим образом:

Поскольку полностью аффинно расщепляема порядка 2, то она либо аффинна на всех сдвигах, либо не аффинна ни на одном. Поэтому по лемме 5 для некоторой константы Z2 верно Разложим по последним двум переменным.

(x,, ) = (1)(1) (x, 0, 0)(1) (x, 0, 1)(1) (x, 1, 0) (x, 1, 1).

Или Пусть (x, ) = (x,, 0) и (x, ) = (x, 0, ), т.е. это подфункции, и = (0, 1) Z2. Тогда Пусть — любая из функций, или (x, 0, 0). Если от 3-х и более переменных, то по лемме 6 она аффинна на некотором подпространстве размерности 2, при этом — подфункция, следовательно, она как и является полностью аффинно расщепляемой порядка 2. Таким образом, по предположению индукции deg 2.

Отсюда deg (x, 0, 0) 2, а deg, deg 1. Исходя из равенства (2.1) получаем, что deg 2. Лемма доказана.

Лемма 8. Бент-функция B2 не может быть аффинна на подпространстве размерности большей, чем.

Доказательство. Пусть | () =,, — подпространство размерности + 1. Тогда бент-функция () = (), равна 0 на. Так как размерность больше, то существуют два различных подпространства и, содержащиеся в. Тогда = тоже является бентфункцией по конструкции (1.3), при этом () = ( ) + 2+1. Приходим к противоречию, поскольку вес бент-функций может быть только 221 ± 21.

Доказательство данной леммы также можно найти в [36].

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

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

(ii) Функция является полностью аффинно расщепляемой порядка, /2 < и не является полностью аффинно расщепляемой порядка + тогда и только тогда, когда аффинно эквивалентна функции Доказательство. Заметим что если является полностью аффинно расщепляемой порядка, то она либо аффинная, либо квадратичная: это следует из утверждения 3 и леммы 7.

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

По теореме Диксона любая квадратичная функция аффинно эквивалентна Таким образом, аффинна на грани 2 = 4 =... = 2 = 0 размерности, т. е. пункт (i) доказан. Для доказательства пункта (ii) достаточно воспользоваться тем, что функция (1,..., 22 ) = 1 2 3 4... 221 22 является бент-функцией и по лемме 8 не может быть аффинна на подпространстве размерности большей, чем : тогда функция не может быть аффинна на подпространстве размерности большей, чем + (2 2) =.

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

Бент-функции на минимальном В главе получен критерий нахождения двух бент-функций на минимальном возможном расстоянии. Основные результаты опубликованы в работах [86,91].

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

Будем говорить, что (, ) — это множество разногласий функций и. Заметим, что |(, )| = dist(, ). Через обозначим размерность линейной оболочки векторов из.

3.1 Критерий расположения бент-функций на минимальном Для функций, введем следующее обозначение:

Утверждение 4. Для любого Z справедливо |, ()| |(, )|, причем равенство достигается тогда и только тогда, когда функция (), является постоянной на (, ).

Утверждение 5. Пусть,. Тогда для любого из Z выполняется Доказательство. Запишем коэффициенты Уолша функций и следующим образом:

Отсюда разность этих коэффициентов равна () () = (,) (1) (), (,) (1)(), = 2, ().

Имеет место следующая нижняя оценка минимального расстояния.

Лемма 9. Для, B2, =, верно, что dist(, ) 2.

Доказательство. Воспользуемся симметрией расстояний. Достаточно доказать, что dist(, ) 22 2 для = 1, поскольку класс бент-функций замкнут относительно отрицания функций.

Поскольку = 1, то существует Z2, для которого () = ().

Следовательно, для Z2, такого что 2 · (1) = () верно Следовательно, dist(, ) dist(,, ) + dist(,, ) = 22 2. Лемма доказана.

Следующие леммы потребуются для доказательства основной теоремы.

Лемма 10. Пусть, B2. Тогда |(, )| = |(, )|.

Доказательство. Воспользуемся формулой свертки:

отсюда Осталось заметить, что откуда и следует утверждение леммы.

выполняется. Тогда — аффинное подпространство.

Доказательство. Пусть — линейная оболочка, =, 0.

Покажем, что = 0. Понятно, что 0. Также Следовательно, = 0.

Теперь покажем, что — линейное подпространство Z. непусто, следова- тельно, достаточно показать только его замкнутость относительно.

так как по условию леммы для любых, справедливо.

Таким образом, — линейное подпространство Z. И следовательно, — аффинное подпространство.

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

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

Доказательство. (=). Пусть, B2, |(, )| = 2. Для доказательства утверждения достаточно показать, что (, ) — аффинное подпространство и аффинна на (, ). Введем обозначения для следующих множеств:

По утверждению Так как, B2, то, () {0, 2, 2 }. Согласно лемме 10, |=0 | = |(, )|.

Таким образом, все =0 являются решениями одной из следующих систем:

Обозначив 0 за, получаем равносильные системы уравнений:

Видно, что решения систем не пересекаются.

Теперь оценим |=0 |, исходя из того, что обе системы разрешимы:

первая система всегда имеет 22(,) решений, а вторая либо имеет столько же решений, либо вообще не имеет. Отсюда Но, исходя из мощности множества (, ), получаем:

Рассмотрим два случая.

Случай 1: (, ) =. Очевидно, в этом случае (, ) является линейным подпространством.

Случай 2: (, ) = + 1. В этом случае обе системы должны иметь решение, поэтому у второй системы должно существовать частное решение, т. е.

существует 0 Z, такое, что 0, = 1 для всех (, ).

Если существуют, (, ), такие, что (, ), то вторая система будет противоречива. Действительно, с одной стороны, с другой стороны, 0, = 1. Следовательно, выполняется условие леммы для множества (, ). Таким образом, (, ) — аффинное подпространство.

По утверждению 4 если для некоторого Z2 верно, что |, ()| = |(, )| = 2, то |(,) () =, для подходящей константы. Утверждение доказано.

В другую сторону доказательство очевидно.

Воспользуемся конструкцией, предложенной К. Карле в работе [36]: если B2, — аффинное подпространство Z2 размерности и аффинна на, то также является бент-функцией.

Следствие 1. Пусть B2. Тогда 2 является бент-функцией на расстоянии 2 от тогда и только тогда, когда =, где — аффинное подпространство Z2 размерности и аффинна на.

Следствие 2. Справедливо Доказательство. Очевидно, что от бент-функции 1 2 3 4... есть бент-функция на расстоянии 2, поскольку она аффинна на грани 2 = 4 = Отметим, что бент-функции на расстоянии 2 от B2 существуют тогда и только тогда, когда является слабо нормальной.

Несмотря на то, что почти все булевы функции не являются нормальными (см. [52], это также следует из результатов О. А. Логачева [14]), для бентфункций известно мало конструкций, порождающих не нормальные (не слабо нормальные) бент-функции, причем все они являются вторичными. Например, в [33] было доказано, что бент-функция является нормальной (слабо нормальной) тогда и только тогда, когда является нормальной (слабо нормальной). Также К. Карле, Х. Доббертин и Г. Леандр в работе [38] 2004 г. доказали, что если не является нормальной, то для любой нормальной бент-функции B2 бент-функция тоже не является нормальной. Еще одна конструкция была предложена в работе [59] 2006 г.

А. Канто, М. Даум, Х. Доббертин и Г. Леандр с помощью компьютерного перебора (используя алгоритм, предложенный М. Даумом, Х. Доббертином и Г. Леандром, [48], 2003 г.) нашли примеры бент-функций от 10 переменных, которые не являются нормальными, и примеры бент-функций от 14 переменных, которые не являются слабо нормальными, в классе мономиальнымых бент-функций с показателем Касами, см. [33] (статья вышла только в 2006 г.). Подробную информацию о мономиальных бент-функциях с показателем Касами см. в работе Дж. Диллона и Х. Доббертина [51] 2004 г.

3.2 Индикаторы аффинных подпространств Рассмотрим индикаторы аффинных подпространств Z2 размерности.

Рассмотрим, где — линейное подпространство.

Отсюда получаем формулу для индикатора:

Рассмотрим.

Следствие 3. Если для, B2 верно, что dist(, ) = 2, то либо deg =, либо deg =.

Таким образом, если, B2 находятся на минимальном возможном расстоянии друг от друга и одна из них имеет степень меньше, чем, то они не являются аффинно эквивалентными.

В общем случае задача нахождения подпространств, на которых аффинна, достаточно сложна (об этом косвенно свидетельствуют результаты М. Л. Бурякова о сложности нахождения уровня аффинности [4]).

Несмотря на это, в некоторых случаях легко найти грани, на которых бентфункция аффинна.

Пример 1. Пусть 1. Зафиксируем все четные переменные значением 1.

Получилась аффинная функция.

2. Индикатор будет выглядеть следующим образом:

3. Получаем бент-функцию на расстоянии 2 от исходной:

В этом разделе рассматривается существование бент-функций на расстоянии 2 от бент-функций из известных подклассов класса B2.

Класс Мэйорана — Мак-Фарланда содержит булевы функции следующего вида:

где, Z,, — взаимно однозначное отображение из Z в Z. Он обозначается через 2. Все функции из этого класса являются бент-функциями.

Более подробно об этой конструкции можно узнать в [66].

Покажем, что для любой функции из класса 2 существует бент-функция на расстоянии 2. Зафиксируем значение : пусть = 0. Тогда Очевидно, что это аффинная функция.

Класс 2 является простым и достаточно богатым.

Мощность класса 2 часто используется как нижняя оценка мощности класса B2. Если рассматривать функции, аффинно эквивалентные функциям из 2, то идею Мэйорана — Мак-Фарланда можно трактовать следующим образом:

1. Берем линейное подпространство размерности в Z2.

2. Разбиваем Z2 на смежные классы относительно.

3. На каждом смежном классе задаем аффинную функцию.

Класс бент-функций «Частичное расщепление» обозначается как (от Partial Spread). Он состоит из двух подклассов, +, определяемых следующим образом. Пусть Тогда функция Все такие функции являются бент-функциями. Класс был предложен Дж. Диллоном в [50].

Нетрудно убедиться, что от любой бент-функции из класса + есть бентфункция на расстоянии 2 : для всех подпространств из определения функций в этом классе выполняется потому что пространства пересекаются только по нулевому элементу. Кроме того, так как 0 лежит во всех, а их нечетное число. Следовательно, Для произвольной функций из вопрос существования бент-функций на расстоянии 2 остается открытым.

3.4 Аффинная эквивалентность бент-функций и В этом разделе мы рассмотрим известные факты об аффинной классификации бент-функций.

Утверждение 6. Все бент-функции степени 2 аффинно эквивалентны функции Данное утверждение является следствием теоремы Диксона, его также можно в работе Дж. Диллона [50].

Утверждение 7 (О. Ротхаус [77], Дж. Диллон [49], Б. Пренель [72]). Каждая бент-функция от 6 переменных аффинно эквивалентна одной из следующих функций:

Утверждение 8 (А. Брэкен [32], К. Д. Хоу [60]). Каждая бент-функция от переменных степени не больше 3 аффинно эквивалентна одной из следующих функций:

Отметим, что все бент-функции из предыдущих утверждений об аффинной классификации являются аффинно эквивалентными функциям из класса Мэйорана—МакФарланда (см. [32]). Об аффинной классификации булевых функций от 6, 7 и 8 переменных см. также работу А. В. Черемушкина [29] 2001 г.

Так как класс B2 замкнут относительно отрицания функции, то из формулы min,B2, = dist(, ) = 2 следует Утверждение 9. Наибольшее расстояние в классе B2, не равное 22, равно Определение 9. Пусть B2. Тогда вектор из Z2 называется спектром расстояний для бент-функции, если -я компонента вектора равна количеству бент-функций на расстоянии от функции.

Утверждение 10. Спектры расстояний для аффинно эквивалентных бентфункций одинаковы.

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

dist(, ) = dist( ( ), ( )), — невырожденная матрица;

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

Утверждение 11. От любой квадратичной бент-функции от 2 переменных существует бент-функция на расстоянии 2.

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

Утверждение 12. От любой бент-функции из B6 существует бент-функция на расстоянии 23.

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

Утверждение 13. От любой бент-функции из B8 степени не больше 3 существует бент-функция на расстоянии 24.

Доказательство. Также воспользуемся аффинной классификацией из утверждения 8:

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

приложение A).

Таблица 3.1 Количество бент-функций на минимальном расстоянии от заданной бент-функции Бент-функции на минимальном расстоянии от квадратичной бент-функции В этой главе рассматриваются бент-функции на минимальном возможном расстоянии от квадратичной бент-функции. Будет подсчитано число всех таких бент-функций, а для бент-функции 1 +1 2 +2... 2 они будут построены в явном виде (от других квадратичных бент-функций бент-функции на минимальном расстоянии можно построить используя тот факт, что все квадратичные бент-функции аффинно эквивалентны). Ближайшая бент-функция от любой квадратичной бент-функции от 2 переменных находится на расстоянии 2. Результаты данной главы опубликованы в работах [87,92,93].

В следующих нескольких разделах построим все бент-функции на расстоянии 2 от бент-функции 1 +1 2 +2... 2 и подсчитаем их количество.

Утверждение 14. (Дж. Диллон [50]) Любая квадратичная бент-функция от переменных аффинно эквивалентна бент-функции Здесь и далее через 0 обозначим функцию из приведенного утверждения.

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

Для рассмотрения бент-функций на расстоянии 2 от функции 0 сделаем следующее: приведем некоторые утверждения об аффинности функций в общем и функции 0 в частности на некотором подпространстве, рассмотрим удобные базисы для представления подпространств, опишем аффинные подпространства размерности, на которых аффинна функция 0, подсчитаем количество таких подпространств и приведем некоторые примеры для малых размерностей.

4.2 Аффинность булевой функции на подпространстве Каждому линейном подпространству можно поставить в соответствие некоторую базисную матрицу. Будем считать, что базисом пространства являются столбцы этой матрицы. Также через () обозначим -й столбец матрицы, а через — элемент этой матрицы.

Следующее утверждение позволяет определить, аффинна ли булева функция на некотором подпространстве.

Утверждение 15. Пусть — произвольная булева функция от переменных и — базисная матрица размера для некоторого линейного подпространства размерности в Z. Тогда функция аффинна на подпространстве тогда и только тогда когда функция () = () от переменных аффинна.

Доказательство данного утверждения тривиально.

Следующая лемма содержит критерий аффинности функции 0 на подпространстве с некоторой базисной матрицей.

Лемма 12. Пусть — любая базисная матрица размера 2 для линейного подпространства размерности в Z2, а матрицы = ( ) и = ( ) образованы первыми строками и последними строками матрицы соответственно. Тогда функция 0 аффинна на подпространстве тогда и только тогда когда выполняются соотношения где () и () — -е столбцы матриц и.

Доказательство. По утверждению 15 функция 0 аффинна на подпространстве тогда и только тогда, когда функция () = 0 () от переменных аффинна.

Функция имеет следующую алгебраическую нормальную форму Степень функции, очевидно, будет не больше 2, поэтому для её аффинности достаточно и необходимо, чтобы все коэффициенты при для = были равны 0. Т.е.

Лемма доказана.

Будем описывать линейные подпространства с помощью базисных матриц Гаусса—Жордана (или, сокращенно, GJB-матриц). Отметим, что в наших обозначениях базисные векторы являются столбцами базисной матрицы.

Определение 10. Пусть — матрица с столбцами, образованная ненулевыми векторами (1),..., (). Через (() ) обозначим min{ | = 0}. Матрица является GJB-матрицей если выполняются следующие условия:

В этом случае через () обозначим множество {((1) ),..., (() )}. Все строки матрицы с номерами из множества () будем называть ведущими строками.

Все остальные строки будем называть неведущими. Через обозначим подпространство с базисом (1),..., (). Заметим, что столбцы матрицы действительно являются базисными векторами пространства, а матрицу называют также редуцированной ступенчатой матрицей.

Пример 2. Следующая матрица является GJB-матрицей для подпространства размерности 3 в Z с () = {1, 3, 5}.

Заметим, что имеет место следующее утверждение.

Утверждение 16. Любое линейное подпространство имеет единственнную GJB-матрицу.

Доказательство. GJB-матрицу для любого линейного подпространства можно определить следующим образом: любой -й столбец матрицы () — это вектор из пространства, который имеет больше всего младших нулей, а также ( ) = 0 для любого >. Отсюда очевидно следует, что у любого подпространства существует GJB-матрица. Теперь докажем единственность такой матрицы. Предположим, что существует два вектора () и () для некоторого, удовлетворяющие приведенному выше свойству. Тогда вектор () () будет иметь как минимум на один младший ноль больше, а совпадающие координаты векторов () и () у их суммы будут нулевыми. Утверждение доказано.

Таким образом, всевозможные GJB-матрицы размера взаимнооднозначно соответствуют всевозможным линейным подпространствам размерности в 4.4 Построение бент-функций на минимальном расстоянии Введем определение допустимой GJB-матрицы. Пусть GJB-матрица для подпространства размерности в Z2 имеет вид где матрица имеет размер (матрица, соответственно, имеет размер ( )). Поскольку — GJB-матрица, то должны выполняться следующие два условия:

, — GJB-матрицы.

Все строки матрицы c номерами из ( ) — нулевые.

Удалим из матриц и все строки с номерами из ( ) и обозначим получившиеся матрицы через и соответственно. Поскольку на строки матрицы c номерами из ( ) уже наложено условие, то будем накладывать дополнительные условия на элементы (т.е. на все остальные элементы матрицы ).

Дополнительные условия:

Элементы матрицы являются решениями следующей системы уравнений:

где матрица системы (здесь и далее будем обозначать её через ) имеет размер (( 1)/2) 2 (если 1, то — любая матрица).

Если верны вышеперечисленные условия, то матрицу назовём допустимой порядка.

Следующая теорема описывает все аффинные подпространства, на которых аффинна квадратичная бент-функция.

Теорема 3. Пусть — аффинное подпространство размерности в Z2. Бентфункция 0 аффинна на тогда и только тогда, когда является линейным подпространством с допустимой GJB-матрицей или смежным классом такого подпространства.

Доказательство. Используя утверждение 2, можно без ограничения общности считать, что — линейное подпространство.

Пусть — GJB-матрица для подпространства. Обозначим верхнюю половину матрицы через, а нижнюю — через. Пусть () и () — -е столбцы матриц и соответственно. По лемме 12 функция 0 аффинна на подпространстве тогда и только тогда, когда выполняется Рассмотрим данные соотношения как систему уравнений относительно переменных () Z и коэффициентов () Z.

Очевидно, что любую GJB-матрицу можно представить в виде где матрицы и — GJB-матрицы размера и ( ) соответственно для некоторого {0,..., }. Тогда для столбцов матрицы система уравнений (4.2) приобретет следующий вид:

Уравнения (4.2) для столбцов матрицы можно разделить на две части:

Но из уравнений (4.3) следует, что (), () = 0. Поэтому уравнения (4.2) превращаются в уравнения (4.3) относительно () и (4.4) относительно ().

Поскольку — GJB-матрица, то строки матрицы с номерами из ( ) являются нулевыми. Следовательно, уравнения (4.4) записываются в виде где () и () — столбцы матриц и соответственно, полученных из и удалением строк с номерами из ( ).

Таким образом, 0 аффинна на тогда и только тогда, когда выполняются соотношения (4.3) и (4.6). Решениями () системы (4.3) являются любые элементы подпространства. Но матрица является GJB-матрицей, поэтому она определяется однозначно по матрице как GJB-матрица для. Уравнения (4.6) можно представить в виде системы линейных уравнений (4.1), если считать ( (1),..., () ) столбцом переменных. Следовательно, соотношения (4.2) выполняются тогда и только тогда, когда матрица является допустимой. Теорема доказана.

Приведем некоторые крайние случаи: при = 0 имеется единственная допустимая GJB-матрица При = допустимые GJB-матрицы имеют вид где — произвольная симметричная матрица. Количество таких матриц равно 2(+1)/2.

Рассмотрим пример построения линейного подпространства, на котором аффинна функция 0 (), т.е. = 4. Общий вид базисной матрицы будет Возьмем в качестве матрицы следующую матрицу ранга 2:

Получим одну из базисных матриц подпространства :

Выберем у подпространства GJB-матрицу (здесь ( ) = {1, 2}):

Отсюда матрица равна и, как следствие, в качестве матрицы получаем матрицу Таким образом, матрица имеет вид Например, для 1, 2, 3 = 1 получим матрицу В итоге получаем GJB-матрицу для подпространства, на котором функция 4.5 Подсчет количества бент-функций на минимальном расстоянии от квадратичной бент-функции Перейдем к подсчету числа бент-функций на расстоянии 2 от произвольной квадратичной бент-функции. Для начала докажем следующую лемму.

Лемма 13. Строки матрицы вида (4.1) являются линейно независимыми.

Доказательство. Пусть матрица образована всеми неведущими строками матрицы. Заметим, что матрица имеет размер. Покажем, что векторы (1),..., () являются линейно независимыми. Заметим также, что из этого утверждения очевидно следует линейная независимость строк матрицы.

Предположим, что существуют различные 1,...,, такие что Тогда для любого = 1,..., верно Также для любого = 1,..., выполняется Поскольку =, то (), ( ) = 0. Поэтому верно Элементы (() ) — это все удаленные элементы из столбцов с номерами 1,...,. Следовательно, мы получаем что но векторы (1),..., () линейно независимы, поэтому мы приходим к противоречию. Следовательно, (1),..., () линейно независимы.

Обозначим через количество линейных подпространств размерности в Z. Заметим, что число можно посчитать по следующей формуле:

Эту формулу можно найти, например, в монографии Мак-Вильямс и Слоэна [19]. Имеет место следующая лемма.

Лемма 14. Для произвольных > 0 и 0 < < верно равенство Для её доказательства достаточно воспользоваться приведенной формулой.

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

Доказательство. Согласно утверждению 14, любая квадратичная бент-функция от 2 переменных аффинно эквивалентна бент-функции 0. Покажем, что эта бент-функция аффинна ровно на размерности. Тогда аффинных подпространств будет ровно в 2 раз больше. И по следствию 1 мы получим количество бент-функций на расстоянии 2.

По теореме 3 достаточно подсчитать количество допустимых GJB-матриц размера 2, т.к. различные GJB-матрицы соответствуют различным линейным подпространствам. Для любой допустимой GJB-матрицы порядка рассмотрим соответствующие ей матрицы,,. Матрица ранга может быть выбрана способами. Тогда матрица определяется однозначно. Для фиксированной матрицы по теореме 3 и лемме 13 мы можем выбрать 2(+1)/2 матриц. Таким образом, мы получили, что любая квадратичная функция аффинна ровно на (+1)/ =0 2 линейных подпространствах. Обозначим это число через и упростим данную формулу.

Докажем, что при > 0 выполняется = (2 + 1)1.

По лемме 14 для каждого, такого что 0 < < выполняется = 1 + 2 1. Заметим, что для крайних значений параметра справедливо = и = 2 1. Отсюда Заметим, что первая сумма равна 1. Во второй сумме заменим на + 1 и получим Так как ( + 1) + ( + 1)( + 2)/2 = + ( + 1)/2, получаем Также 1 = 3. Следовательно, = (21 + 1) ·... · (2 + 1). Теорема доказана.

Нетрудно доказать, что 2 · (21 + 1) ·... · (2 + 1) < 3 · 2 · 2(+1)/2. Поэтому более чем треть бент-функций на расстоянии 2 от квадратичной бент-функции можно получить очень просто, а именно с помощью допустимых GJB-матриц вида где — произвольная симметричная матрица размера.

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

Обозначим через * произвольный элемент Z2. Тогда все допустимые GJBматрицы при = 2 выглядят следующим образом (выделены ведущие элементы): при = 0 одна матрица при = 1 получаем 3 · 2 = 6 матриц вида и при = 2 имеется 1 · 23 = 8 матриц вида где — некоторый элемент Z2. Итого получаем 15 линейных подпространств.

Взяв также все смежные классы подпространств с приведенными выше базисными матрицами, получим 60 аффинных подпространств, на которых 0 аффинна.

Для = 3 функция 0 аффинна на линейных подпространствах со следующими допустимыми GJB-матрицами: при = 0 одна матрица при = 1 получаем 7 · 2 = 14 матриц вида при = 2 имеется 7 · 23 = 56 матриц вида и при = 3 имеется 1 · 26 = 64 матриц вида где,, — некоторые элементы Z2. Таким образом, получаем 135 линейных подпространств. Посчитав также все смежные классы данных подпространств, получим 1080 аффинных подпространств, на которых 0 аффинна.

В следующей таблице приведено количество бент-функций на расстоянии от любой квадратичной бент-функции для малого числа переменных:

Оценки числа бент-функций на расстоянии В этой главе рассматриваются оценки числа бент-функций на расстоянии от B2. Получена верхняя оценка для произвольной бент-функции и нижняя оценка для бент-функции из класса Мэйорана—МакФарланда (или аффинно эквивалентной такой бент-функции). Результаты о верхней оценке опубликованы в работах [90,97], о нижней оценке — в работах [87,92].

5.1 Верхняя оценка для произвольной бент-функции Поскольку любое подпространство размерности, > 0, можно представить как ( ), где — подпространство Z размерности 1, следующее утверждение даёт условие, при котором можно увеличить на 1 размерность подпространства, на котором аффинна булева функция.

Утверждение 17. Пусть, — подпространство Z и | () =, для некоторых Z2 и Z2. Тогда аффинна на подпространстве ( ), Z, тогда и только тогда, когда | () =, для некоторого Доказательство. Рассмотрим функцию () = (),. Очевидно, что | = 0. Следовательно, по лемме 3 аффинна на ( ) тогда и только тогда, когда | = для некоторого Z2.

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

Неполным преобразованием Уолша функции | называется отображение Приведем аналог равенства Парсеваля для неполного преобразования Уолша:

Более подробную информацию о неполном преобразовании Уолша можно найти в монографии О. А. Логачева, А. А. Сальникова, С. В. Смышляева, В. В. Ященко [18].

Лемма 15. Пусть — бент-функция от 2 переменных, — линейное подпространство Z2 размерности, и 1,..., — различные сдвиги.

Пусть для некоторого Z2 верно, что Тогда 222. При этом в случае = 222 функция (), уравновешенна на каждом, где (1 )... ( ).

Доказательство. Известно, что для произвольных бент-функции, линейного подпространства, и, Z2 справедлива формула (1.2):

Пусть =, рассмотрим неполное преобразование Уолша функции | :

() = (1) (),, Z2. Тогда cогласно равенству (5.1) Пусть = (1 )... ( ). Тогда из равенства (5.2) и условия леммы следует, что для всех справедливо | ()| = 2 2 = 2. Так как для частичного преобразования Уолша функции | справедлив аналог равенства Парсеваля, а || = 22 и | | = 2, то Следовательно, 222. Если же = 222, то () = 0 при. Отсюда доказана.

Сформулируем случай = 222 из предыдущей леммы отдельно.

Утверждение 18. Пусть бент-функция B2 постоянна на 222 различных сдвигах подпространства Z2 размерности, 1. Тогда на всех других сдвигах бент-функция является уравновешенной.

Данный случай является обобщением утверждения, доказанного К. Карле.

Утверждение 19 (К. Карле, 1994, [36]). Пусть бент-функция B2 постоянна на некотором подпространстве размерности. Тогда уравновешенна на каждом сдвиге, отличном от самого.

Таким образом, утверждение 18 эквивалентно утверждению 19 в случае =.

Отметим, что Х. Доббертин в работе [52] использовал утверждение 19 как идею для построения большого класса нормальных бент-функций.

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

Лемма 16. Пусть B2 и для некоторого линейного подпространства Z2 размерности,, бент-функция аффинна на каждом сдвиге. Тогда (), является константой ровно на 222 различных сдвигах для любого Z2. Доказательство. Обозначим через множество сдвигов, на которых (), является константой. Заметим, что если | () =,, то для образом, = для. Поскольку аффинна на каждом сдвиге, а число различных сдвигов равно 22, то должно быть справедливо при этом по лемме 15 | | 222. Следовательно, неравенство справедливо только если | | = 222 для всех Z2.

Докажем основную теорему.

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

Доказательство. Обозначим через произвольную квадратичную бентфункцию от 2 переменных. Определим следующее множество:

( ) = { | — линейное подпространство Z2 размерности, По следствию 1 число бент-функций на расстоянии 2 от равно | ( )|. Докажем, что | ( )| | ()|.

Воспользуемся индукцией по, 0 и покажем, что | ( )| | ()|.

База индукции = 0: очевидно, что |0 ( )| = |0 ()| = 22.

Пусть для < верно, что | ( )| | ()|. Докажем, что |+1 ( )| любое () имеет вид = ( ) для некоторого Z2. Тогда поскольку в подпространстве содержится ровно 2(2+1 1) различных подпространств размерности. По утверждению 17 и леммам 15 и 16 для любых |+1 ( )| |+1 ()|.

Таким образом, | ( )| | ()|.

Хотя значение | ()| уже подсчитано в теореме 4, его можно найти исходя из приведенных выше формул. Поскольку | ( )| = 222 dim 1, то Докажем, что оценка достигается только для квадратичных бент-функций.

Пусть не является квадратичной (из этого автоматически следует, что > 2).

Тогда по теореме 1 она не является полностью аффинно расщепляемой порядка, т.е. аффинна на подпространстве размерности и не аффинна на некотором его сдвиге (если не аффинна ни на одном подпространстве размерности, то | ( )| = 0).

Без ограничения общности можем полагать, что — линейное подпространство, и | = 0 (этого можно добиться за счет преобразований вида (), ). Из утверждения 18 следует, что на всех сдвигах, отличных от, функция уравновешена.

Пусть — линейное подпространство размерности 1. Очевидно, что | = 0. Пусть ( ) > 1, т.е. функция аффинна на ( ) для некоторого. Тогда из леммы 3 следует, что | = для некоторого Z2. Но в силу уравновешенности на получаем, что |()( ) = 1 и по лемме аффинна на.

Также заметим, что если и — различные линейные подпространства размерности 1, то не может быть аффинна одновременно на ( ) и на ( ) в силу уравновешенности на. Число различных равно 2 1. Число различных сдвигов, не равных, тоже равно 2 1. Поэтому если ( ) > 1 для всех, то аффинна на всех сдвигах. Следовательно, ( ) = 1 для какого-то, в то время как ( ) = 3 для любого 1 ().

Теорема доказана.

Рассмотрим тривиальную верхнюю оценку для произвольной бент-функции.

Утверждение 20. Пусть B2. Тогда число бент-функций на расстоянии от нее не больше, чем Это число аффинных подпространств Z2 размерности. Его можно оценить как Таким образом, верхняя оценка близка к квадратному корню из тривиальной оценки.

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

Напомним, что класс Мэйорана — МакФарланда содержит функции вида где, Z, — булева функция от переменных, – перестановка на Z.

Для нахождения нижней оценки нам потребуется следующая вспомогательная лемма.

Лемма 17. Пусть, — линейное подпространство Z размерности, Тогда Доказательство. Заметим, что | () =, тогда и только тогда, когда справедливо, =,. Поэтому найдем все, удовлетворяющие равенству. Сделаем замену переменных: =, =.

является решением системы линейных уравнений, = 0, т.е..

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

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

Линейное подпространство содержит ровно 2 1 различных линейных подпространств размерности 1. Таким образом, аффинное подпространство можно выбрать ровно 2+1 · (2 1) способами. Также очевидно, что аффинное подпространство содержится в множестве.

Используя утверждение 17, получаем, что существует ровно 2+1 векторов 1, таких что | () = 1, 1. Но для любого существует ровно 2 векторов 2, таких что | () = 2, 2. Поэтому, в силу леммы 16, существует сдвиг, отличный от, такой что для некоторого вектора и констант 1, 2 выполняется В множестве содержится ровно 2 различных сдвига подпространства, обозначим их через и. Таким образом, по утверждению 17 функция аффинна на аффинных подпространствах ( ) ( ) и ( ) ( ) размерности. С учетом того, что мы выбираем неупорядоченную пару сдвигов, получаем различных аффинных подпространств размерности, на которых функция аффинна. Также аффинна на каждом сдвиге подпространства. Теорема доказана.

Приведем список основных результатов данной работы.

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

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

3. Получена классификация всех бент-функций на минимальном расстоянии от квадратичной бент-функции. Подсчитано число таких бент-функций.

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

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

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

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

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

физ.-мат. наук. 05.13.19 / Буряков Михаил Леонидович. — М., 2009.

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

5. Буряков М. Л. Асимптотические оценки уровня аффинности для почти всех булевых функций // Дискретная математика. — 2008. — T. 20, № 3. — С. 98– 6. Буряков М.Л., Логачев О.А. Об уровне аффинности булевых функций // Дискретная математика. — 2005. — T. 17, № 4. — С. 98–107.

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

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

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

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

Бент-функции и гипербент-функции над полем из 2 элементов // Проблемы передачи информ. — 2008. — Т. 44, № 1. — С. 15–37.

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

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

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

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

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

МЦНМО, 2004. С. 176–178.

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

МЦНМО, 2012. — 584 с.

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

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

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

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

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

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

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

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

27. Токарева Н. Н. Симметричная криптография. Краткий курс / Новосибирск:

НГУ, 2012. — 234 с.

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

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

30. Ященко В. В. О критерии распространения для булевых функций и о бентфункциях // Проблемы передачи информации. — 1997. — Т. 33, № 1. — С 75— 31. Bernasconi A., Codenotti B., VanderKam J. M. 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. 202– 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, N 5. — 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 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. 139– 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 (2 ): the Niho case // Inform. and Comput. — 1999. — V. 151, N 1–2. P. 57–72.

54. Dobbertin H. Almost perfect nonlinear power functions over (2 ): 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. 254– 266. (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. Theory. — 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. 609– 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 T., Seberry J., Pieprzyk J., Charnes C. Homogeneous bent functions of degree in 2 variables do not exist for > 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 B., L S. I/O correlation properties of bent functions // Science in China Series E: Technological Sciences. — 2000. — V. 43, N 3. — P. 282–286.

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

87. Коломеец Н. А. Перечисление бент-функций на минимальном расстоянии от квадратичной бент-функции // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 1. — C. 41—58 (Перевод: Kolomeets N. A.

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. Коломеец Н. А. Пороговое свойство квадратичных булевых функций // Дискретный анализ и исследование операций. — 2014. — T. 21, № 2. — C. 52–58.

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

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