Bent functions and their generalizations.pdf ВведениеБент-функции впервые были введены О. Ротхаусом в 60-х годах XX века. ВыпускникПринстонского университета Оскар Ротхаус (1927-2003) после службы вовремя Корейской войны в войсках связи поступил на работу математиком в АгентствоНациональной Безопасности США. С 1960 по 1966 г. он работал в Институтеоборонного анализа (IDA). Его криптографические работы того времени оценивалисьруководством IDA достаточно высоко. Как и его преподавательская деятельность:«he was one of the most important teachers of cryptology to mathematicians andmathematics to cryptologists» [8]. На это же время приходится и его первая работа обент-функциях [36]. В открытой печати она появилась только в 1976 г. [37]. В ней былиустановлены базовые свойства бент-функций, предложены их простейшие конструкциии намечена классификация бент-функций от шести переменных.В настоящее время бент-функции и их приложения изучаются очень активно.Семейства бент-последовательностей из элементов +1 и - 1 , построенные на основебент-функций, имеют предельно низкие значения как взаимной корреляции, так иавтокорреляции (достигают нижней границы Велча). Такие семейства успешно применяютсяв коммуникационных системах коллективного доступа, а также в работе состандартом CDMA. Технология цифровой сотовой связи CDMA ^ o d e Division MultipleAccess - множественный доступ с кодовым разделением каналов) была стандартизованав 1993 г. американской телекоммуникационной промышленной ассоциацией(US TIA) в виде стандарта IS-95. В настоящее время технология используется большинствомпоставщиков беспроводного оборудования во всем мире согласно стандартамIMT-2000 мобильной связи третьего поколения (в России - стандарты IMT-MC 450или CDMA-450). В системах CDMA для предельного снижения отношения пиковой исредней мощностей сигнала (peak-to-average power ratio) используются коды постояннойамплитуды. Их построение напрямую связано с выбором специального подмножествабент-функций.В блочных и поточных шифрах бент-функции и их векторные аналоги способствуютпредельному повышению стойкости этих шифров к линейному и дифференциальномуметодам криптоанализа. Стойкость достигается за счет использования сильнонелинейных булевых функций в S-блоках (см., например, шифр CAST). Бент-функции и их обобщения находят свое применение также в схемах аутентификации,хэш-функциях (см. HAVAL) и псевдослучайных генераторах. См. также пример использованиябент-функций в поточном шифре Grain.Несмотря на высокий интерес к бент-функциям, прогресс в их изучении самыйминимальный. Для мощности класса бент-функций не найдена асимптотика, не установленоприемлемых нижних и верхних оценок. Мало изучены и их обобщения, возникающиеиз новых постановок прикладных задач.Данная лекция построена на основе двух обзоров автора [5, 6] и по сути являетсяих кратким конспектом. Приводятся основные свойства, конструкции, эквивалентныепредставления бент-функций. Значительное внимание уделяется обобщениямбент-функций. В конце статьи приводятся открытые вопросы в этой области.Нам потребуются следующие определения и обозначения:q, n - натуральные числа;+-----сложение по модулю q;x = ( x i , ... , xn) - q-значный вектор;- множество всех q-значных векторов длины n;Fqn - поле Галуа порядка qn;(x, y) = x 1y 1 + ... + xnyn - скалярное произведение векторов;f : Zn ^ Z 2 - булева функция от n переменных;f - вектор значений длины 2n функции f . Будем считать, что аргументы функции(т. е. векторы длины n) перебираются в лексикографическом порядке;dist(f, g) - расстояние Хэмминга между функциями f и g, т. е. число позиций,в которых различаются векторы f и д;АНФ - алгебраическая нормальная форма функции;d e g (f) - степень нелинейности булевой функции f , т. е. число переменных в самомдлинном слагаемом ее АНФ;Wf (y) = (-l)(x>y)+/(x) - преобразование Уолша-Адамара булевой функции f ;xezr;Nf - нелинейность булевой функции f , т. е. расстояние Хэмминга от данной функциидо множества всех аффинных функций;максимально нелинейная функция - булева функция с максимально возможнымзначением N f;бент-функция (n чётное) - булева функция, такая, что все её коэффициентыУолша-Адамара равны ± 2 n/2;Bn - класс бент-функций от n переменных;аффинно эквивалентные функции f и g от п переменных: существуют невырожденнаяп х n-матрица A, векторы b,c длины п и константа Л Е Z 2, такие, чтоg(x) = f (Ax + b) + (c, x) + Л.1. К ри т ери и и св ой ств а► Следующие утверждения эквивалентны:(i) булева функция f от n переменных является бент-функцией;(ii) матрица A = (ax,y), где ax,y = 2-n/2Wf (x + y), является матрицей Адамара;(iii) матрица D = (dx,y), где dx,y = (-1)f(x+y), является матрицей Адамара;(iv) для любого ненулевого вектора x функция f (y) + f (x + y) сбалансирована, т. е.принимает значения 0 и l одинаково часто.► Степень нелинейности d e g (f) любой бент-функции f от n ^ 4 переменных непревосходит числа n /2.► Бент-функции любой степени 2 ^ d e g (f) ^ n/2 существуют.► Любая квадратичная бент-функция от n переменных аффинно эквивалентнафункции f (xi, . . . ,Xn) = Х1Х2 + ХзX4 + . .. + Xn-lXn.► Класс бент-функций замкнут относительно(i) любого невырожденного аффинного преобразования переменных;(ii) прибавления любой аффинной функции.2. Эквивалентные представления бент-функц ий► Бент-функции могут быть описаны в терминах элементарных адамаровых разностныхмножеств и симметричных блок-схем [19].► (Описание В. В. Ященко, 1997 [7].) Любая булева функция f от n переменныхможет быть представлена в виде линейного разветвления f (x ',x '') = (x ',h (x '')) ++g (x ''), где x' G Z2,x" G Z| для подходящих чисел r и k, таких, что n = r + k,отображения h : Z| ^ Z2 и булевой функции g от k переменных. Максимально возможноезначение r в таком представлении называется индексом линейности булевойфункции f . Подмножество M пространства Zn называется бент-множеством, еслиего мощность равна 22 при некотором . и для любого ненулевого вектора z G Zn множествоM П (z + M ) либо пусто, либо имеет четную мощность. Пара (g; M ), где g -булева функция от k переменных, M - бент-множество, называется частичной бент-функцией, если для любого y' G Z2 и ненулевого y" G Z^ функция g(x'') + g(x'' + y")сбалансирована на множестве M П ((y ',y'') + M ).Функция f в виде линейного разветвления является бент-функцией тогда и толькотогда, когда n ^ 2r и для любого вектора x' G Z2 выполняются условия:(i) мощность множества h- 1(x') равна 2n-2r;(ii) множество h- 1(x ') является бент-множеством;(iii) пара (g; h- 1(x')) является частичной бент-функцией.► (Описание К. Карле и Ф. Гуилло, 1998 [15].) Пусть f - булева функция от nпеременных. Пусть Inds : Zn ^ Z 2 - характеристическая функция подмножестваS С Zn, т. е. Inds принимает значение l на элементах из S и значение 0 на остальныхэлементах.Функция f является бент-функцией тогда и только тогда, когда существуют подпространстваE 1, . . . , Ek размерности n/2 или (n /2) + l пространства Zn и ненулевыецелые числа m1, . . . ,m k, такие, что ^ k=1 miIndEi(y) = ± 2 (n/2) - 1Ind{o}(y) + f(y ) длялюбого y G Zn. Можно ввести ограничения на способ выбора пространств E 1, . . . , E^,при которых можно говорить об однозначности такого представления.► (Описание А. Бернаскони, Б. Коденотти и Дж. Ван-дер-Кама, 1999 [10, 11].)Пусть f - булева функция от n переменных. Через supp(f) обозначим ее носитель,т. е. множество всех двоичных векторов длины n, на которых функция f принимаетзначение 1. Рассмотрим граф Кэли Gf = G(Zn, supp(f)) булевой функции f . Вершинами графа являются все векторы длины n. Две вершины x, y соединяются ребром, есливектор x + y принадлежит множеству supp(f). Граф G называется сильно регулярным(strongly regular), если существуют неотрицательные целые числа Л, ^, такие, что длялюбых двух вершин x, y общее число смежных им вершин равно Л или ^ в зависимостиот того, соединены вершины x, y ребром или нет.Булева функция f является бент-функцией тогда и только тогда, когда граф Gfявляется сильно регулярным, причем Л = ^.► (Описание С. В. Агиевича, 2000 [9].) Пусть f - булева функция от n переменных,n = r + k. Вектор W f коэффициентов Уолша-Адамара назовем спектральнымвектором функции f . Представим двоичный вектор f в виде f = ( f ( l)^ .^ f (2r)),где каждый вектор f (^ имеет длину 2k. Пусть f^) - булева функция от k переменных,для которой f (^) является вектором значений, i = 1 , .. ., 2r. Свяжем с функциейf матрицу M f размера 2r х 2k, строками которой являются спектральные векторыW f(1), . . . , W f(2r). Матрица размера 2r х 2k называется бент-прямоугольником, есликаждая ее строка и каждый столбец, домноженный на 2r-(n/2), являются спектральнымивекторами для подходящих булевых функций. Согласно [9], выполняется следующаятеорема.Булева функция f является бент-функцией тогда и только тогда, когда матрицаM f является бент-прямоугольником.3. Оценки числа бент-функц ийЧисло бент-функций от n переменных неизвестно. Существует большой разрывмежду нижней и верхней оценками этого числа. Асимптотически он имеет видC1 22" /2 ^ |Bn| ^ С2 22" . Нижняя оценка получается из конструкции Мэйорана-МакФарланда (некоторое ее улучшение см. в [9]). Верхняя оценка приводится в [16].Сократить этот разрыв - серьезная задача.4. Нелинейность произвольн ой булевой функцииВ 1998 г. Д. Оледжар и М. Станек [32] исследовали криптографические свойстваслучайной булевой функции от n переменных. В частности, они показали, что существуетконстанта c, такая, что при достаточно больших n почти для каждой булевойфункции f от n переменных выполняется Nf ^ 2n-i - c^fn 2n/2. То есть с ростомn нелинейность случайной булевой функции от n переменных становится достаточновысокой и даже сопоставимой с нелинейностью бент-функции!Для криптографических приложений булева функция кроме нелинейности должнаобладать целым рядом других свойств. Приведенный факт позволяет сказать, чтоесть «гарантированная возможность» выбора функции с высокой нелинейностью нев ущерб этим свойствам. Но хотя нелинейность почти всех булевых функций высока,это не означает, что такие функции легко построить.Задача описания всех бент-функций от n переменных решена лишь при малыхзначениях n. Приведем эти результаты (см. таблицу). Количество бент-функций приn = 8 равно 29 х 193 887 869 660 028 067 003 488 010 240 ~ 2106>295. К он стр ук ц и и бент-ф ункц и й► Функция f (x ',x '') = g(x') + h(x''), где векторы x', x'' имеют четные длины r, kсоответственно, является бент-функцией тогда и только тогда, когда функции g, h -бент-функции.Б ен т-ф ун кц и и о т малого числа переменныхnЧислофункцийЧислокл. экв. Представители классов эквивалентности2 8 1 х 1 х24 896 1 х 1 х2 + х 3х465 425 430 528 ~~ 232,3 4Представители степени 2х 1 х2 + х 3х4 + х 5х 6,представители степени 3х 1 х2х 3 + х 1х4 + х 2х 5 + х 3х 6,х 1 х2х 3 + х 2х4х 5 + х 1х 2 + х 1х4 + х 2х 6 + х 3х 5 + х4х 5,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 1х4 + х 2х6 + х 3 х4++ х 3х 5 + х 3х 6 + х4х 5 + х4х 68 ~ 2106,29 ^ 536Представители степени 2х 1 х2 + х 3х4 + х 5х 6 + х 7х8,представители степени 3х 1 х2х 3 + х 1х4 + х 2х 5 + х 3х 6 + х 7х8,х 1 х2х 3 + х 2х4х 5 + х 3х4 + х 2х 6 + х 1х 7 + х 5х8,х 1 х2х 3 + х 2х4х 5 + х 1х 3 + х 1х 5 + х 2х 6 + х 3х4 + х 7х8,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 3х5 + х 2х6 + х 2 х5++ х 1х 7 + х4х8,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 3х5 + х 1х3 + х 1 х4++х2х7 + х 6х8,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 3х5 + х 2х6 + х 2 х5++ х 1х 2 + х 1х 3 + х 1х4 + х 7х8,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 3х5 + х 1х6 + х 2 х 7 + х 4 х8,х 1 х2х 7 + х 3х4х 7 + х 5х 6х7 + х 1х4 + х 3х6 + х 2 х5++ х 4х 5 + х 7х8,х 1 х2х 3 + х 2х4х 5 + х 3х4х6 + х 1х4х 7 + х 3х 5 + х 2х 7++ х 1х 5 + х 1х 6 + х4х8,представителей степени 4 см. в [26, 27]^ 10 ??? ??? ???► Пусть n = r + k, где r и k четны, f - булева функция от n переменных. Пусть х',х'' пробегают Z2 и Z^ соответственно. Предположим, что функции f xii(х') = f (х ',х '')являются бент-функциями при любых х''. Определим gxi (х'') = f xii (х'). Тогда f -бент-функция, если и только если gxi - бент-функция для любого х'.► (Конструкция Мэйорана-МакФарланда, 1973 [29].) Пусть h - любая перестановкана Z^/2, пусть g - произвольная булева функция от n/2 переменных. Тогдафункция f (х ',х '') = (х', h(x'')) + д(х'') является бент-функцией от n переменных.► (Partial Spreads, Дж. Диллон, 1974 [20].) Пусть IndS : Z^ ^ Z 2 - характеристическаяфункция подмножества S С Z^. Пусть число q равно 2(n/2)-1 или 2(n/2)-1 + 1.Пусть L 1, . .. , Lq - линейные подпространства размерности n/2 пространства Z^, такие,что любые два из них пересекаются лишь по нулевому вектору. Тогда функцияqf (у) = Ф Ind^ (y) является бент-функцией. Различают классы бент-функций P S + иi=1P S - (при q = 2(n/2)-1 и q = 2(n/2)-1 + 1 соответственно).► (Степенные или мономиальные бент-функции - power/monomial bent functions.)Пусть векторное пространство Z^ отождествляется с полем Галуа F2n. Булевы функции от n переменных можно рассматривать как функции из F2n в F2, сопоставляя каждомувектору y соответствующий элемент поля F2n, который будем обозначать тем жесимволом. Пусть tr : F2n ^ F2 - функция следа, т. е. tr(y) = y + y2 + + y2" . Бент-функции, имеющие вид f (y) = tr(ayd), где a G F*n - некоторый параметр, называютсястепенными или мономиальными, а целое число d называется бент-показателем.Здесь F2" - множество ненулевых элементов поля. Пусть gcd(-, ) - наибольший общийделитель двух чисел. Известны следующие бент-показатели: 2n/2 - 1, 2г + 1 (еслиn /gcd (n ,i) четно), 22k - 2k + 1 (при gcd(k,n) = 1), (2k + 1)2 (если n = 4k, k нечетно),22k + 2k + 1 (при n = 6k).► Пусть булева функция представлена в виде f (y) = tr(a1ydl + a2yd2) для подходящихэлементов a1,a 2 G F2n и показателей d1,d2. Будем рассматривать специальныестепенные показатели - показатели Нихо вида d = 2г mod (2n/2 - 1). Без ограниченияобщности [21] пусть первый показатель равен d1 = (2(n/2) - 1) 1 + 1. Тогда [23] еслиd2 = (2(n/2) - 1)А + 1, где А равно 1/6, 1/4 или 3, то существуют элементы a1, a2 G F2n,такие, что f является бент-функцией.► Общий алгебраический подход к описанию бент-функций мог бы основыватьсяна том, что любая булева функция f : F2n ^ F2 может быть представлена с помощьюследа (в так называемой trace form), т. е. в виде f (y) = tr I adyd I =Vdecs J= S tr(adyd) для подходящих элементов ad G F2n, где CS - множество представите-decsлей циклотомических классов по модулю 2n - 1. Эволюционный алгоритм на основетакого представления был предложен М. Янгом, К. Менгом и Х. Жангом [39]. На основемногочисленных компьютерных исследований авторы делают в этой работе некоторыепредположения, например о том, что бент-функцию - представителя классааффинной эквивалентности - можно представить в trace form с участием небольшогочисла мономов. Причем более вероятными ненулевыми коэффициентами ad считаютсяте, для которых d является бент-показателем.6 . Ал ге бр аи ч е ски е об общ ени я бент-ф ункц и йПриведем обобщения, в которых рассматриваемые функции отличаются от булевых.Как правило, это отображения из одной алгебраической системы в другую. В этоми других пунктах обобщения приводятся на уровне определений. О том, в каких случаяхдоказано существование этих обобщений, см. подробнее в [6].► (ВЕКТОРНЫЕ БЕНТ-ФУНКЦИИ.) С 90-х годов XX века стали исследоватьсяфункции f : Zn ^ Zm, получившие название векторных булевых функций, или (n,m)-функций. Нелинейные такие функции имеют непосредственные криптографическиеприложения. Например, в шифрах они используются в качестве S-блоков. ПреобразованиемУолша-Адамара (n, т)-функции f называется отображение WJect : Zn xZm ^ Z,заданное равенством WJect(x', x'') = J^yeZn(-1)(x/,y)+(x//,f(y)). Векторная (n, т)-функцияназывается бент-функцией, если |Wfect(x', x'')| = 2n/2 для каждых x' G Zn, x'' G (Zm)*.Но векторные бент-функции существуют тогда и только тогда, когда n четно иm ^ n/2 [31]. При m > n/2 (в частности при m = n) рассматриваются аналоги бент-функций, такие, как APN- и AB-функции.► (q-ЗНАЧНЫЕ БЕНТ-ФУНКЦИИ, q-ARY BENT FUNCTIONS, П.В. Кумар,Р. А. Шольц и Л. Р. Велч, 1985 [25].) Пусть q ^ 2 - натуральное число, i = \[-1- мнимая единица. Пусть ш - примитивный комплексный корень степени q изединицы, ш = e2ni/q. Рассмотрим q-значную функцию f : Z n ^ Z q. Преобразованием Уолша-Адамара функции f называется комплексная функция Wf(y) == S xeZ" y>+f(x), y G Z ; , где скалярное произведение и сложение + рассматриваютсяпо модулю q. Пусть |с| обозначает модуль комплексного числа с. Функция f : Z ; ^ Z qназывается q-значной бент-функцией, если |Wf (y)| = qn/2 для каждого y G Z ; .► (БЕНТ-ФУНКЦИИ НАД КОНЕЧНЫМ ПОЛЕМ, А.С. Амбросимов, 1994 [1].)Пусть q = p^, где p - простое, . - натуральное. Пусть ш - примитивный комплексныйкорень степени p из единицы, ш = e2ni/p. Пусть f : Fqn ^ Fq - q-значная функция.При фиксированном z G Fq преобразование Уолша-Адамара функции f определяетсякак Wf,z(y) = J^xeF n ш ^ '^ ^ (x),z^, где z рассматривается как вектор над Fpдлины . и внешнее скалярное произведение берется по модулю p (внутреннее - помодулю q). Для любой функции f и любого ненулевого z выполняется равенство Пар-севаля yeF |W/;Z (y)|2 = q2n, из которого следует, что max |W/)Z (y)| ^ qn/2. ФункциУ yeFqn яf : Fqn ^ Fq называется бент-функцией, если при любых векторах z G Fq\{0}, y G Fqnвыполняется |Wf,z(y)| = qn/2. Заметим, что при q = p, . = 1 данное определениеq-значной бент-функции совпадает с определением Кумара, Шольца и Велча.► (ОБОБЩЕННЫЕ БУЛЕВЫ БЕНТ-ФУНКЦИИ, К.Шмидт, 2006 [38].) Они возниклив связи с построением обобщенных кодов постоянной амплитуды для системCDMA. Пусть q ^ 2 - натуральное число, ш - примитивный комплексный кореньстепени q из единицы, ш = e2ni/q. Функция f : Zn ^ Z q называется обобщенной булевойфункцией. Ее преобразованием Уолша-Адамара называется комплексная функцияWf(y) = . * « ; ( -1)

Скачать электронную версию публикации