Содержание к диссертации
Введение
1 Аффинность булевых функций 14
1.1 Определения 14
1.2 Аффинность булевых функций на подпространстве 18
1.3 Булевы функции, аффинные на подпространстве и всех его сдвигах 19
2 Полностью аффинно расщепляемые булевы функции 21
3 Бент-функции на минимальном расстоянии друг от друга 27
3.1 Критерий расположения бент-функций на минимальном расстоянии друг от друга 27
3.2 Индикаторы аффинных подпространств 32
3.3 Подклассы класса бент-функций 33
3.3.1 Класс Мэйорана — Мак-Фарланда 33
3.3.2 Частичное расщепление 34
3.4 Аффинная эквивалентность бент-функций и минимальное расстояние 34
4 Бент-функции на минимальном расстоянии от квадратичной бент-функции 39
4.1 Квадратичные бент-функции 39
4.2 Аффинность булевой функции на подпространстве 40
4.3 Представление подпространств 41
4.4 Построение бент-функций на минимальном расстоянии от квадратичной бент-функции 42
4.5 Подсчет количества бент-функций на минимальном расстоянии от квадратичной бент-функции 46
4.6 Примеры для малых размерностей 49
5 Оценки числа бент-функций на расстоянии 2 от функции из B2 . 52
5.1 Верхняя оценка для произвольной бент-функции 52
5.2 Нижняя оценка для бент-функций из класса Мэйорана—МакФарланда 56
Заключение 59
Литература
- Аффинность булевых функций на подпространстве
- Критерий расположения бент-функций на минимальном расстоянии друг от друга
- Аффинная эквивалентность бент-функций и минимальное расстояние
- Построение бент-функций на минимальном расстоянии от квадратичной бент-функции
Аффинность булевых функций на подпространстве
Нелинейность — одно из важнейших криптографических свойств булевых функций. В частности, алгоритм симметричного шифрования 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 одинаково часто. Отсутствие сбалансированности препятствует использованию бент-функций как координатных функций во взаимно однозначных -блоках блочных шифров. Одним из путей решения проблемы является построение криптографических булевых функций путем модификации имеющейся бент-функции, поскольку во многих случаях можно гарантировать, что нелинейность функции по прежнему оста 7 нется высокой. Ещё один путь — использование различных обобщений бент-функций, см., например, полу-бент-функции [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].
Поскольку расположение бент-функций на минимальном возможном расстоянии друг от друга связано с аффинностью булевой функции на аффинном подпространстве, введём необходимые определения.
Критерий расположения бент-функций на минимальном расстоянии друг от друга
Рассмотрим существующие понятия, связанные с аффинностью булевой функции на подпространстве. Определение 2. Функция /Gjn называется к-аффинной, если для некоторых 1 i\ ... ik п и &i,..., bk Є Z2 функция /ь " к аффинна. Заметим, что функция является -аффинной, если она аффинна на некоторой грани размерности п — к. Уровнем аффинности f называется минимальное возможное к, такое что / является -аффинной. Эти определения ввели О. А. Логачев, А. А. Сальников и В. В. Ященко в работе [17] 2004 г (труды конференции «Математика и безопасность информационных технологий» 2003 г). Аффинные функции обладают нулевым уровнем аффинности (и только они). Также уровень аффинности не превышает п - 1. В работе М. Л. Бурякова и О. А. Логачева [6] 2005 г. было доказано, что уровнем аффинности п - 1 обладают исключительно квадратичные булевы функции, АНФ которых содержит все мономы степени 2. М. Л. Буряков в работе [4] доказал, что задача нахождения уровня аффиности булевой функции / є Тп, если число мономов в её АНФ не превосходит сп, где с - некоторая константа, является TVP-трудной. Более подробную информацию об уровне аффинности см. в работе М. Л. Бурякова [5] (оценки уровня аффинности для почти всех булевых функций) и его кандидатской диссертации [3].
Определение 3. Функция / є Тп называется к-нормальной (к-слабо нормальной), если она постоянна (аффинна) на некотором подпространстве размерности к. Определение 4. Функция / є Тп называется нормальной (слабо нормальной), если она \п/2] -нормальна ([п/2]-слабо нормальна). Через \а] обозначена целая часть сверху числа а Є Ш.
Определение нормальности было предложено Х. Доббертином в работе [52] 1994 г. Он ввел его для функций от чётного числа переменных. Данное понятие тесно связано с классом бент-функций. Многие первичные конструкции бент-функций (класс Мэйорана-МакФарланда, один из подклассов частичного расщепления), а также все бент-функции от двух, четырех и шести переменных являются нормальными. Вопрос о существовании бент-функций, не являющихся нормальными, на тот момент оставался открытым. П. Шарпин в 2004 г. в работе [45] обобщила определение нормальности на случай произвольного числа переменных и ввела понятие Анормальности. В 2006 г. вышла работа А. Канто, М. Даума, Х. Доббертина и Г. Леандра [33], где авторы привели пример бент-функции от 10 переменных, не являющейся нормальной и бент-функции от 14 переменных, не являющейся слабо нормальной (обе бент-функции - мономи-альные функции с показателем Касами). Также в этой работе была предложена конструкция, позволяющая по произвольной не нормальной (не слабо нормальной) бент-функции от 2к переменных построить не нормальную (не слабо нормальную) бент-функцию от 2к + 2 переменных.
Отметим, что любая / -нормальная функция является /с-слабо нормальной. Любая -аффинная функция является (п - &)-слабо нормальной.
Обобщённым уровнем аффинности f называется минимальное возможное к, такое что / аффинна на подпространстве размерности п — к. Оценками обобщённого уровня аффинности для почти всех булевых функций занимался О. А. Логачев, см. работы [13,14]. В работе [14] доказано, что для почти всех булевых функций от п переменных обобщённый уровень аффинности лежит в интервале [п — log2 п,п — log2 п + 1].
Булевы функции, аффинные на подпространстве и всех его сдвигах В этом разделе рассмотрим аффинность булевой функции на подпространстве и всех его сдвигах. Определение 5. Функция /GJB сильно к-аффинна, если для некоторых 1 %\ ... ik п и произвольных &!,...,&& є Z2 функция fi 1 " і к аффинна. Таким образом, сильно -аффинная функция аффинна на грани размерности п — к и всех её сдвигах. Данное определение, как и определение -аффинной булевой функции, было предложено О. А. Логачевым, А. А. Сальниковым и В. В. Ященко. Также оно тесно связано со следующим понятием.
Определение 6. Булева функция / є Тп задана в виде линейного разветвления, если существуют число к Є N, 1 к п, функция Ф : Щ к — Ъ\и ф є Fn-k, такие что /(ж, у) = (ж, Ф(у)) 0 ф(у) для всех х Є Z2, у Є Z2_A:. Подробную информацию об этом представлении можно найти в монографии [18]. Представлением бент-функций в виде линейного разветвления занимался В. В. Ященко в работе [30] 1997 г. Нетрудно доказать следующую лемму.
Лемма 1. Пусть f Є Тп аффинна на некотором подпространстве размерности к и на каждом его сдвиге. Тогда она аффинно эквивалентна булевой функции, представленной в виде линейного разветвления с параметром к, а именно функции д(х, у) = (ж, Ф(у)) 0 ф{у), где х Є Z, у Є Zi2 , Ф : 1Т2 — l\ и ф Є J k Доказательство данной леммы можно найти, например, в работе [33]. Введем естественное обобщение приведенного выше определения.
Определение 7. Функция / є Тп является аффинно расщепляемой по подпространству L, если функция / аффинна на каждом сдвиге L.
Отметим, что любая сильно -аффинная функция является аффинно расщепляемой по некоторой грани размерности п — к. В следующей главе рассмотрим еще более сильное понятие аффинности. Глава 2 Полностью аффинно расщепляемые булевы функции
В данной главе вводится понятие полностью аффинно расщепляемой булевой функции. Понятие полной аффинной расщепляемости связывает аффинность булевой функции на одном подпространстве с аффинностью функции на каждом сдвиге этого подпространства. Доказывается, что все полностью аффинно расщепляемые булевы функции являются либо аффинными, либо квадратичными. Результаты главы опубликованы в работах [90,97]. В работах [88,89,96] опубликованы результаты о полностью аффинно расщепляемых булевых функциях порядка п/2], где п — число переменных.
Аффинная эквивалентность бент-функций и минимальное расстояние
Пусть — любая из функций , " или (x, 0, 0). Если от 3-х и более переменных, то по лемме 6 она аффинна на некотором подпространстве размерности 2, при этом — подфункция , следовательно, она как и является полностью аф-финно расщепляемой порядка 2. Таким образом, по предположению индукции deg 2.
Отсюда deg (x, 0,0) 2, а deg a , deg a " 1. Исходя из равенства (2.1) получаем, что deg 2. Лемма доказана. Лемма 8. Бент-функция Є B2fc не может быть аффинна на подпространстве размерности большей, чем .
Доказательство. Пусть \L,( ) = { , )@ , — подпространство размерности + 1. Тогда бент-функция ( ) = ( ) 0 ( , ) 0 равна 0 на . Так как размерность больше , то существуют два различных подпространства и 0 , содержащиеся в . Тогда = 0 [/ 0 au тоже является бент-функцией по конструкции (1.3), при этом ( ) = ( ) + 2k+l. Приходим к противоречию, поскольку вес бент-функций может быть только 22к 1 ± 2к 1. П Доказательство данной леммы также можно найти в [36].
Теорема 1. Пусть - булева функция от переменных. Справедливы следующие утверждения. (i) Функция является полностью аффинно расщепляемой порядка , 2 \ /2] тогда и только тогда, когда либо аффинная, либо квадратичная. (ii) Функция является полностью аффинно расщепляемой порядка , \ /2] и не является полностью аффинно расщепляемой порядка + 1 тогда и только тогда, когда аффинно эквивалентна функции Доказательство. Заметим что если / является полностью аффинно расщепляемой порядка к, то она либо аффинная, либо квадратичная: это следует из утверждения 3 и леммы 7.
Так как для аффинных и квадратичных булевых функций имеет место утверждение 2, для доказательства полной аффинной расщепляемости функции достаточно доказать существование подпространства соответствующей размерности, на котором функция аффинна.
По теореме Диксона любая квадратичная функция аффинно эквивалентна функции g(xi,..., хп) = Х\Х2 0 жз 4 0 ... 0 X2t-i%2t для некоторого t п/2. Таким образом, д аффинна на грани х2 = х4 = ... = x2t = 0 размерности n, т. е. пункт (i) доказан. Для доказательства пункта (ii) достаточно воспользоваться тем, что функция h(x\, . . . , X2n-2k) = Х\Х2 0 Ж3Ж4 0 ... 0 Х2п-2к-\Х2п-2к являет ся бент-функцией и по лемме 8 не может быть аффинна на подпространстве размерности большей, чем п - к: тогда функция д не может быть аффинна на подпространстве размерности большей, чем п — к + п — (2п — 2к) = к. Таким образом, среди бент-функций полностью аффинно расщепляемыми являются только квадратичные бент-функции. Глава 3 Бент-функции на минимальном расстоянии друг от друга В главе получен критерий нахождения двух бент-функций на минимальном возможном расстоянии. Основные результаты опубликованы в работах [86,91]. Введём несколько определений. Обозначим через D(f,g) множество значений аргументов, на которых функции / и д от п переменных отличаются, т. е. D(f,g) = {х Є Щ f(x) Ф д{%)}. Будем говорить, что D(/, д) — это множество разногласий функций /ид. Заметим, что \D(f,g)\ = dist(/,д). Через rkD обозначим размерность линейной оболочки векторов из D. 3.1 Критерий расположения бент-функций на минимальном расстоянии друг от друга Для функций f,geFn введем следующее обозначение: aLg(w) = Yl (-l)f{x)(B{w x). xD(f,g) Утверждение 4. Для любого w Є Щ справедливо \af}9(w)\ \D(f,g)\, причем равенство достигается тогда и только тогда, когда функция f(x) 0 (w,x) является постоянной на D(f,g).
Имеет место следующая нижняя оценка минимального расстояния. Лемма 9. Для f,g Є ЗЗгь f ф д, верно, что dist(f,д) 2к.
Доказательство. Воспользуемся симметрией расстояний. Достаточно доказать, что dist(/, д) 22к — 2к для / ф д 0 1, поскольку класс бент-функций замкнут относительно отрицания функций. Поскольку / ф д 0 1, то существует а Є 1%к, для которого Wj(a) = Wg(a). Следовательно, для с Є Z2, такого что 2к (—1)с = Wj(a) верно dist(/, а с) = dist(g,a c) = 2 — 2 . Следовательно, dist(/, д) dist(f,a c) + dist( ,ac) = 22к — 2к. Лемма доказана.
Если существуют ж, у Є D(f, д), такие, что х 0 у Є D(f, д), то вторая система будет противоречива. Действительно, с одной стороны, (to,x) = 1, (to, у) = 1 == (to,x у) = О, с другой стороны, (to,x(By) = 1. Следовательно, выполняется условие леммы 11 для множества D(/, д). Таким образом, D(/, д) — аффинное подпространство. По утверждению 4 если для некоторого Ъ Є 1%к верно, что \cLf,g(b)\ = \D(f,g)\ = 2к, то f\D(f,g)(x) = (Ь,х) 0 с для подходящей константы с. Утверждение доказано.
В другую сторону доказательство очевидно. Воспользуемся конструкцией, предложенной К. Карле в работе [36]: если / є 2 2Ь L — аффинное подпространство 13 размерности к и / аффинна на L, то / 0 Indi также является бент-функцией.
Следствие 1. Пусть f Є В2к. Тогда g Є Т2к является бент-фушцией на расстоянии 2к от f тогда и только тогда, когда g = f IndL, где L - аффинное подпространство Zf размерности kuf аффинна на L. Следствие 2. Справедливо min dist(f, g) = 2 . Доказательство. Очевидно, что от бент-функции хЛх2 0 x:ix4 0 ... 0 x2k-ix2k есть бент-функция на расстоянии 2к, поскольку она аффинна на грани х2 = х = ... = х2к = 0. П
Отметим, что бент-функции на расстоянии 2к от / є В2к существуют тогда и только тогда, когда / является слабо нормальной.
Несмотря на то, что почти все булевы функции не являются нормальными (см. [52], это также следует из результатов О. А. Логачева [14]), для бент-функций известно мало конструкций, порождающих не нормальные (не слабо нормальные) бент-функции, причем все они являются вторичными. Например, в [33] было доказано, что бент-функция g(xi,..., x2k+2) = f{xi,..., x2k) 0 x2k+\x2k+2 является нормальной (слабо нормальной) тогда и только тогда, когда / является нормальной (слабо нормальной). Также К. Карле, Х. Доббертин и Г. Леандр в работе [38] 2004 г. доказали, что если / не является нормальной, то для любой нормальной бент-функции h Є Ъ2т бент-функция g(x,y) = f(x) 0 h(y) тоже не является нормальной. Еще одна конструкция была предложена в работе [59] 2006 г.
А. Канто, М. Даум, Х. Доббертин и Г. Леандр с помощью компьютерного перебора (используя алгоритм, предложенный М. Даумом, Х. Доббертином и Г. Ле-андром, [48], 2003 г.) нашли примеры бент-функций от 10 переменных, которые не являются нормальными, и примеры бент-функций от 14 переменных, которые не являются слабо нормальными, в классе мономиальнымых бент-функций с показателем Касами, см. [33] (статья вышла только в 2006 г.). Подробную информацию о мономиальных бент-функциях с показателем Касами см. в работе Дж. Диллона и Х. Доббертина [51] 2004 г.
Построение бент-функций на минимальном расстоянии от квадратичной бент-функции
В этой главе рассматриваются оценки числа бент-функций на расстоянии 2к от / є В2к. Получена верхняя оценка для произвольной бент-функции и нижняя оценка для бент-функции из класса Мэйорана-МакФарланда (или аффинно эквивалентной такой бент-функции). Результаты о верхней оценке опубликованы в работах [90,97], о нижней оценке - в работах [87,92].
Верхняя оценка для произвольной бент-функции Поскольку любое подпространство размерности к, к 0, можно представить как L U (а 0 L), где L — подпространство Щ размерности к — 1, следующее утверждение даёт условие, при котором можно увеличить на 1 размерность подпространства, на котором аффинна булева функция.
Утверждение 17. Пусть f Є Тп, L - подпространство Щ и f\L(x) = (w, х)фс для некоторых w Є Щ и с Є Z2. Тогда f аффинна на подпространстве L U (а 0 L), а Є Щ, тогда и только тогда, когда /\аь(%) = (w,x) 0 с для некоторого d Є Z2. Доказательство. Рассмотрим функцию f (x) = f(x) 0 (w, х)фс. Очевидно, что 0. Следовательно, по лемме 3 / аффинна на L U (а 0 L) тогда и только тогда, когда f \aL = с для некоторого с Є Z2. Далее оценим число способов, которыми можно, используя утверждение 17, увеличить на 1 размерность подпространства, на котором бент-функция аффинна. Для этого нам потребуется следующее понятие. Пусть / є Тп, S С Щ. Неполным преобразованием Уолша функции f\s называется отображение
Более подробную информацию о неполном преобразовании Уолша можно найти в монографии О. А. Логачева, А. А. Сальникова, С. В. Смышляева, В. В. Ященко [18].
Лемма 15. Пусть f - бент-функция от 2к переменных, L - линейное подпространство Z размерности t, t к и а\ 0 L,..., ап 0 L —различные сдвиги L. Пусть для некоторого w Є Ъ22к верно, что
Утверждение 18. Пусть бент-функция f Є B2k постоянна на 22k 2t различных сдвигах подпространства L С Zf размерности t, 1 t к. Тогда на всех других сдвигах L бент-функция f является уравновешенной. Данный случай является обобщением утверждения, доказанного К. Карле. Утверждение 19 (К. Карле, 1994, [36]). Пусть бент-функция f Є B2fc постоянна на некотором подпространстве L размерности к. Тогда f уравновешенна на каждом сдвиге L, отличном от самого L. Таким образом, утверждение 18 эквивалентно утверждению 19 в случае t = к. Отметим, что Х. Доббертин в работе [52] использовал утверждение 19 как идею для построения большого класса нормальных бент-функций. Докажем, что аффинное подпространство, на котором аффинна полностью аффинно расщепляемая бент-функция, можно «достроить» максимальным для бент-функции числом способов. Лемма 16. Пусть f Є B2fc и для некоторого линейного подпространства L С Zf размерности t, t к, бент-функция f аффинна на каждом сдвиге L. Тогда f(x) 0 (w,x) является константой ровно на 22k 2t различных сдвигах L для любого w Є Zlk.
Доказательство. Обозначим через Sw множество сдвигов L, на которых f(x) 0 (w,x) является константой. Заметим, что если f\ab(x) = (w,x) 0 с, то для любого w Є w 0 L1- верно, что f\ab(x) = (w ,x) Ф (w ф w ,a) 0 с. Таким образом, Sw = Sw(Su для и Є L . Поскольку / аффинна на каждом сдвиге L, а число различных сдвигов равно 22k f, то должно быть справедливо 22k—t
Докажем, что оценка достигается только для квадратичных бент-функций. Пусть / не является квадратичной (из этого автоматически следует, что к 2). Тогда по теореме 1 она не является полностью аффинно расщепляемой порядка к, т.е. / аффинна на подпространстве L размерности А; и не аффинна на некотором его сдвиге (если / не аффинна ни на одном подпространстве размерности к, то \Dk(f)\ = 0). Без ограничения общности можем полагать, что L — линейное подпространство, и f\L = 0 (этого можно добиться за счет преобразований вида /(х0a) 0 (w, x) 0c). Из утверждения 18 следует, что на всех сдвигах L, отличных от L, функция / уравновешена. Пусть V — линейное подпространство L размерности к — 1. Очевидно, что /z/ = 0. Пусть Nf(L ) 1, т.е. функция / аффинна на Ь и(афЬ ) для некоторого а ф L. Тогда из леммы 3 следует, что f\au = с для некоторого с Є Z2. Но в силу уравновешенности / на а 0 L получаем, что f\aL)\(aL ) = с 0 1 и по лемме 3 / аффинна на а 0 L. Также заметим, что если V и L" — различные линейные подпространства L размерности к — 1, то / не может быть аффинна одновременно на V U (а 0 L ) и на L" U (а 0 L") в силу уравновешенности / на а 0 L. Число различных V равно 2 — 1. Число различных сдвигов L, не равных L, тоже равно 2 — 1. Поэтому если Nf(L ) 1 для всех L , то / аффинна на всех сдвигах L. Следовательно, Nf(L ) = 1 для какого-то V, в то время как Nh(U) = 3 для любого U Є Dk l(h). Теорема доказана. Рассмотрим тривиальную верхнюю оценку для произвольной бент-функции. Утверждение 20. Пусть f Є В2к. Тогда число бент-функций на расстоянии 2к от нее не больше, чем и (22к — 1) ... (2k+l — 1) 2г . (2fe — 1) ... (2і — 1) Это число аффинных подпространств Zjf размерности к. Его можно оценить как 2кЧк 2fc(22 -1)-----(21-1) 2кЧ2к_ (2fe — 1) ... (2і — 1) Таким образом, верхняя оценка близка к квадратному корню из тривиальной оценки. 5.2 Нижняя оценка для бент-функций из класса
Мэйорана-МакФарланда Рассмотрим нижнюю оценку числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана-МакФарланда. Напомним, что класс Мэйорана - МакФарланда содержит функции вида f(x,y) = (х,7г(у)) 0 ф(у), где х,у Є Z, ф — булева функция от к переменных, 7г - перестановка на Z. Для нахождения нижней оценки нам потребуется следующая вспомогательная лемма. Лемма 17. Пусть f Є Тп, L - линейное подпространство Щ размерности к, а Є Щ и f\ab(%) = (w,x) 0 с для некоторых w Є Z2 и с Є Z2. Тогда f\ab(%) = (w\ х) 0 с для некоторых w1 Є Z2 и с Є Z2 тогда и только тогда, когда w = w 0 L-1 и с = с 0 (и 0 и/, а).
Доказательство. Заметим, что /Ць(ж) = (w ,x) 0 с тогда и только тогда, когда справедливо (и/, ж) 0 с = («;, ж) 0 с Ух Є а 0 L. Поэтому найдем все w , удовлетворяющие равенству. Сделаем замену переменных: у = w@w , и = хфа. Получим {у,и) =с фсф {у,а) Уи Є L. Поскольку 0 Є L, то с = с0 {у,а), где у является решением системы линейных уравнений (у, и) = 0 У и Є L, т.е. у Є LL. Следовательно, w = w 0 L , с = с 0 (w 0 if , a). Теорема 6. Дус/иь / - бент-функция от 2k переменных из класса Мэйорана-МакФарланда. Тогда число бент-функций на расстоянии 2к от нее не меньше, чем 22k+l - 2к. Доказательство. Используя следствие 1, достаточно подсчитать аффинные подпространства размерности к, на которых / аффинна. Пусть L = {(ж,0) х Є Z2} С Z2 . Очевидно, что L - линейное подпространство. Также любая функция из класса Мэйорана-Мак-Фарланда аффинна на L и каждом его сдвиге. Мы будем подсчитывать сдвиги тех линейных подпространств, которые пересекаются с L по 2к 1 элементам.
Линейное подпространство L содержит ровно 2к — 1 различных линейных подпространств U размерности к — 1. Таким образом, аффинное подпространство и U можно выбрать ровно 2k+l (2 - 1) способами. Также очевидно, что аффинное подпространство ифіі содержится в множестве и 0 L.
Используя утверждение 17, получаем, что существует ровно 2к+1 векторов w\, таких что f\uu(%) = Ц,ж) 0 cWl. Но для любого и 0 L существует ровно 2к векторов W2, таких что f\ub(x) = {w2,x) 0 cW2. Поэтому, в силу леммы 16, существует сдвиг v ф L, отличный от и ф L, такой что для некоторого вектора w и констант с\, с выполняется
f\uu(%) = (w,x) Сі, f\vb(%) = (w,x) C i В множестве v ф L содержится ровно 2 различных сдвига подпространства U, обозначим их через а U и 6 ф U. Таким образом, по утверждению 17 функция / аффинна на аффинных подпространствах (и Ф С/) U (а С/) и (и Ф С/) U (6 С/) размерности ft. С учетом того, что мы выбираем неупорядоченную пару сдвигов, получаем ((2к - 1) 2к+1 2)/2 = 22к+1 - 2к+1 различных аффинных подпространств размерности ft, на которых функция / аффинна. Также / аффинна на каждом сдвиге подпространства L. Теорема до казана. Заключение
Приведем список основных результатов данной работы.
1. Введено понятие полной аффинной расщепляемости булевой функции. Доказано, что все полностью аффинно расщепляемые функции являются либо аффинными, либо квадратичными.
2. Доказано, что две бент-функции от 2 переменных находятся на минимальном возможном расстоянии 2 тогда и только тогда, когда они различаются на аффинном подпространстве размерности и обе функции на нём аф-финны.
3. Получена классификация всех бент-функций на минимальном расстоянии от квадратичной бент-функции. Подсчитано число таких бент-функций.
4. Получена точная верхняя оценка числа бент-функций на расстоянии 2 от произвольной бент-функции от 2 переменных. Доказано, что оценка достигается только для квадратичных бент-функций.
5. Получена нижняя оценка числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана—МакФарланда.
