Содержание к диссертации
Введение
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 одинаково часто. Отсутствие сбалансированности препятствует использованию бент-функций как координатных функций во взаимно однозначных -блоках блочных шифров. Одним из путей решения проблемы является построение криптографических булевых функций путем модификации имеющейся бент-функции, поскольку во многих случаях можно гарантировать, что нелинейность функции по прежнему останется высокой. Ещё один путь — использование различных обобщений бент-функций, см., например, полу-бент-функции [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к переменных достигается только для полностью аффинно расщепляемых бент-функций, т.е. только для квадратичных бент-функций. Получена нижняя оценка числа бент-функций на минимальном расстоянии от бент-функции из класса Мэйорана-МакФарланда.
Критерий расположения бент-функций на минимальном расстоянии друг от друга
В данной главе вводится понятие полностью аффинно расщепляемой булевой функции. Понятие полной аффинной расщепляемости связывает аффинность булевой функции на одном подпространстве с аффинностью функции на каждом сдвиге этого подпространства. Доказывается, что все полностью аффинно расщепляемые булевы функции являются либо аффинными, либо квадратичными. Результаты главы опубликованы в работах [90,97]. В работах [88,89,96] опубликованы результаты о полностью аффинно расщепляемых булевых функциях порядка п/2], где п — число переменных.
Определение 8. Функция /GJB называется полностью аффинно расщепляемой порядка к, 2 к п, если она аффинна на некотором подпространстве Щ размерности к и аффинно расщепляема по всем подпространствам размерности к, на которых она аффинна. Порядок 0 и 1 рассматривать не имеет смысла, поскольку тогда бы все булевы функции удовлетворяли определению. Тривиально доказывается следующие утверждение. Утверждение 1. Пусть f,g Є Тп - аффинно эквивалентные булевы функции. Тогда f является полностью аффинно расщепляемой порядка к тогда и только тогда, когда g является полностью аффинно расщепляемой порядка к. Все аффинные и квадратичные булевы функции обладают следующим свойством. Утверждение 2. Пусть f Є Тп - аффинная или квадратичная. Тогда если f аффинна на подпространстве L С Щ, то f аффинна на каждом сдвиге L. Доказательство. Пусть а Є Щ. Функция / аффинна на а 0 L тогда и только тогда, когда f(x 0 а) аффинна на L. Отметим, что f(x 0 а) = f(x) 0 Daf(x), при этом из условия утверждения следует, что deg Daf 1. Следовательно, / аффинна на L тогда и только тогда, когда / аффинна на а 0 L.
Докажем вспомогательные леммы об аффинности булевой функции на подпространстве. Лемма 2. Пусть f Є Тп аффинна на подпространстве L С Щ ненулевой размерности. Тогда для некоторого подпространства U С L и а Є L, таких что L = U U (а 0 [/), функция f постоянна и на U, и на a (&U. Доказательство. Без ограничения общности можно считать, что L - линейное подпространство Щ. Тогда для любого w Є Щ решением системы уравнений (w,x) = 0, х Є L является либо все множество L, либо его подпространство размерности dim L — 1. Лемма доказана. Лемма 3. Пусть f Є Тп, L - подпространство Щ и f постоянна на L. Тогда f аффинна на подпространстве L U (а 0 L), а Є Щ тогда и только тогда, когда f постоянна на а 0 L. Доказательство. Без ограничения общности можно считать, что L - линейное подпространство
Если булева функция является полностью аффинно расщепляемой порядка к, то она также полностью аффинно расщепляема порядка t для всех 2 t к.
Для его доказательства достаточно воспользоваться следующей леммой. Лемма 4. Пусть f Є Тп является полностью аффинно расщепляемой порядка к. Тогда если f аффинна на некотором линейном подпространстве U размерности t к, то существует линейное подпространство L размерности к, такое что U С L и f аффинна на L.
Доказательство. Воспользуемся индукцией по размерности U. База индукции dim U = 0 очевидно следует из условия леммы. Предположим, что для всех подпространств размерности меньшей, чем t,t к — 1, утверждение леммы верно. Докажем, что оно верно и для U размерности t + 1. Представим U как U U (а 0 U ), где U — подпространство U размерности t, а Є U. Тогда по предположению индукции существует L размерности k,U С L и / аффинна на L. Без ограничения общности можно считать, что f\i = О, поскольку прибавление аффинной функции не влияет на наличие или отсутствие аффинности. Тогда по лемме 3 верно, что /\афи = с, где с Є Z2. Поскольку по условию леммы / аффинна на а 0 L, то по лемме 2 существует аффинное подпространство а 0 Т размерности к — 1, такое что афІІ СафТсафЬи f\aT = с. А так как /\т = 0, то по лемме 3 функция / аффинна на линейном подпространстве Т U (а 0 Т) размерности к, которое содержит U. Далее докажем, что полностью аффинно расщепляемыми порядка 2 могут быть только аффинные и квадратичные булевы функции.
Теорема 1. Пусть - булева функция от переменных. Справедливы следующие утверждения. Функция является полностью аффинно расщепляемой порядка , 2 \/2] тогда и только тогда, когда либо аффинная, либо квадратичная. Функция является полностью аффинно расщепляемой порядка , \/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 . Результаты данной главы опубликованы в работах [87,92,93].
Квадратичные бент-функции
В следующих нескольких разделах построим все бент-функции на расстоянии 2 от бент-функции и подсчитаем их количество. Утверждение 14. (Дж. Диллон [50]) Любая квадратичная бент-функция от 2 переменных аффинно эквивалентна бент-функции
Здесь и далее через 02 обозначим функцию из приведенного утверждения. Напомним, что аффинно эквивалентные бент-функции имеют одно и то же число бент-функций на любом заданном расстоянии. Поэтому, используя утверждение 14, достаточно подсчитать количество бент-функций на расстоянии 2 от бент-функции 02 , тогда от остальных квадратичных бент-функций количество бент-функций на расстоянии 2 будет таким же.
Для рассмотрения бент-функций на расстоянии 2 от функции 02 сделаем следующее: приведем некоторые утверждения об аффинности функций в общем и функции о в частности на некотором подпространстве, рассмотрим удобные базисы для представления подпространств, опишем аффинные подпространства размерности , на которых аффинна функция fik, подсчитаем количество таких подпространств и приведем некоторые примеры для малых размерностей.
Аффинность булевой функции на подпространстве Каждому линейном подпространству можно поставить в соответствие некоторую базисную матрицу. Будем считать, что базисом пространства являются столбцы этой матрицы. Также через обозначим -й столбец матрицы , а через ij — элемент этой матрицы.
Следующее утверждение позволяет определить, аффинна ли булева функция на некотором подпространстве.
Утверждение 15. Пусть - произвольная булева функция от переменных и - базисная матрица размера х для некоторого линейного подпространства размерности в Щ. Тогда функция аффинна на подпространстве тогда и только тогда когда функция ( ) =) от переменных аффинна.
Доказательство данного утверждения тривиально. Следующая лемма содержит критерий аффинности функции 02 на подпространстве с некоторой базисной матрицей . Лемма 12. Пусть - любая базисная матрица размера 2 х для линейного подпространства размерности в И2 , а матрицы = ( у-) и = ( у) образованы первыми строками и последними строками матрицы соответственно. Тогда функция f аффинна на подпространстве тогда и только тогда когда выполняются соотношения
Представление подпространств
Будем описывать линейные подпространства с помощью базисных матриц Гаусса-Жордана (или, сокращенно, GJB-матриц). Отметим, что в наших обозначениях базисные векторы являются столбцами базисной матрицы. Определение 10. Пусть G - матрица с к столбцами, образованная ненулевыми векторами и 1\... ,и к\ Через (и ) обозначим min{j и- = 0}. Матрица G является GJB-матрицей если выполняются следующие условия:
В w строки будем называть неведущими. Через LG обозначим подпространство с базисом Заметим, что столбцы матрицы G действительно являются базисными векторами пространства LQ, а матрицу GT называют также редуцированной ступенчатой матрицей.
Пример 2. Следующая матрица G является GJB-матрицей для подпространства размерности 3 в Ъ\ Заметим, что имеет место следующее утверждение. Утверждение 16. Любое линейное подпространство имеет единстееннную GJB-матрицу. Доказательство. GJB-матрицу G для любого линейного подпространства мож но определить следующим образом: любой г-й столбец матрицы и — это век тор из пространства LQ, который имеет больше всего младших нулей, а также ul N = 0 для любого і і. Отсюда очевидно следует, что у любого подпро странства L существует GJB-матрица. Теперь докажем единственность такой матрицы. Предположим, что существует два вектора и и и для некоторого і, удовлетворяющие приведенному выше свойству. Тогда вектор и 0 и будет иметь как минимум на один младший ноль больше, а совпадающие координаты векторов и и и у их суммы будут нулевыми. Утверждение доказано.
Нижняя оценка для бент-функций из класса Мэйорана—МакФарланда
В этой главе рассматриваются оценки числа бент-функций на расстоянии 2к от / є В2к. Получена верхняя оценка для произвольной бент-функции и нижняя оценка для бент-функции из класса Мэйорана-МакФарланда (или аффинно эквивалентной такой бент-функции). Результаты о верхней оценке опубликованы в работах [90,97], о нижней оценке - в работах [87,92].
Поскольку любое подпространство размерности к, к 0, можно представить как L U (а 0 L), где L — подпространство Щ размерности к — 1, следующее утверждение даёт условие, при котором можно увеличить на 1 размерность подпространства, на котором аффинна булева функция.
Далее оценим число способов, которыми можно, используя утверждение 17, увеличить на 1 размерность подпространства, на котором бент-функция аффинна. Для этого нам потребуется следующее понятие. Пусть / є Тп, S С Щ. Неполным преобразованием Уолша функции f\s называется отображение
Более подробную информацию о неполном преобразовании Уолша можно найти в монографии О. А. Логачева, А. А. Сальникова, С. В. Смышляева, В. В. Ященко [18].
Лемма 15. Пусть f - бент-функция от 2к переменных, L - линейное подпространство Z размерности t, t к и а\ 0 L,..., ап 0 L —различные сдвиги L. Пусть для некоторого w Є Ъ22к верно, что Сформулируем случай п = 22k 2t из предыдущей леммы отдельно. Утверждение 18. Пусть бент-функция f Є B2k постоянна на 22k 2t различных сдвигах подпространства L С Zf размерности Тогда на всех других сдвигах 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, то должно быть справедливо при этом по лемме 15 \SW\ 22k 2t. Следовательно, неравенство справедливо только если 15 1= 22k 2t для всех w Є Z? k.
Докажем основную теорему. Теорема 5. Пусть f - бент-функция от 2к переменных. Тогда число бент функций на расстоянии 2к не превосходит 2А;(21 + 1) ... (2к + 1). При этом данная оценка достигается только для квадратичных бент-функций.
Доказательство. Обозначим через h произвольную квадратичную бент-функцию от 2к переменных. Определим следующее множество: Df(f) = {а 0 L L — линейное подпространство Ъ2к размерности t, а Є Z2 и / аффинна на а 0 L}, t Є N, t к. По следствию 1 число бент-функций на расстоянии 2к от / равно \Dk(f)\. Докажем, что \Dk(f)\ \Dk(h)\.
Воспользуемся индукцией по t, 0 t к и покажем, что \Dt(f)\ ) (/г). База индукции t = 0: очевидно, что D(/) = \D(h)\ = 22к. Пусть для t к верно, что D (/) D (/i). Докажем, что Dt+1(/) Dt+1(/i). Пусть Nf(L) = {U Є Dt+l(f) \ L с [/"}, где L є ) (/). Отметим, что любое [/ Є Nf(L) имеет вид (7 = L U (а ф L) для некоторого а Є Ъ2к. Тогда 2(2t+i — 1) 2-— поскольку в подпространстве U содержится ровно 2(2t+1 — 1) различных подпространств размерности t. По утверждению 17 и леммам 15 и 16 для любых
Докажем, что оценка достигается только для квадратичных бент-функций. Пусть / не является квадратичной (из этого автоматически следует, что к 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.
