Бент-функции: результаты и приложения. Обзор работ | ПДМ. 2009. № 1(3).

Бент-функции: результаты и приложения. Обзор работ

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

Bent functions: results and applications. A survey .pdf Данный обзор посвящен результатам в области бент-функций и их приложениям. Логическим продолжением этой работы следует считать обзор [16], в котором будут рассмотрены различные обобщения бент-функций и история их возникновения.Мера нелинейности является важной характеристикой булевой функции. Линейность часто свидетельствует о простой (в определенном смысле) структуре этой функции и, как правило, представляет собой богатый источник информации о многих других ее свойствах. Задача построения булевых функций, обладающих нелинейными свойствами, естественным образом возникает во многих областях дискретной математики. И часто (что является типичной ситуацией в математике) наибольший интерес вызывают те функции, для которых эти свойства экстремальны. Такие булевы функции называются максимально нелинейными или бент-функциями.Первой работой, посвященной бент-функциям, принято считать статью О. Ротхауса 1976 г. [ПО], хотя эти специальные булевы функции были введены им еще в 60-х годах XX века [109]. В настоящее время можно говорить уже о теории бент-функций.Приведем ряд определений и обозначений. Пустьф - сложение по модулю 2 (или XOR);п - натуральное число;v = (i>i,..., vn) - двоичный вектор;ГЕ1 - множество всех двоичных векторов длины щ{и, v) = U\V\ ф ... ф unvn - скалярное произведение векторов;/ : Z^ -> Z2 - булева функция от п переменных;/ - вектор значений длины 2п функции /. Будем считать, что аргументы функции (т. е. векторы длины п) перебираются в лексикографическом порядке;dist(/, g) - расстояние Хэмминга между функциями fug, т.е. число позиций, в которых различаются векторы fug.Известно, что каждая булева функция однозначно может быть задана своей алгебраической нормальной формой (АНФ), а именно представлена в виде/(«) =100 aiu...Ak vh ■ ... ■ vik J Ф ao,\fc=l h,...,ik/1Исследование выполнено при финансовой поддержке интеграционного проекта СО РАН № 35 «Древовидный каталог математических интернет-ресурсов , РФФИ (проекты 07-01-00248, 08-01-00671, 09-01-00528-а) и Фонда содействия отечественной науке.16Н. Н. Токаревагде при каждом к индексы %\,... , ik различны и в совокупности пробегают все к-эле-ментные подмножества множества {!,...,п}. Коэффициенты а^...^, «о принимают значения 0 или 1. В русскоязычной литературе АНФ также называют полиномом Же-галкина. Напомним, что степень нелинейности deg(f) булевой функции / - это число переменных в самом длинном слагаемом ее АНФ. Функция называется аффинной, квадратичной, кубической и т. д., если ее степень равна соответственно 1, 2, 3 и т. д. Каждая аффинная функция от п переменных V\,... , vn имеет вид {и, v) ф а для подходящих вектора и и константы а.Максимально нелинейной называется булева функция от п переменных {п любое) такая, что расстояние Хэмминга Nf от данной функции до множества всех аффинных функций является максимально возможным. Величину Nf называют нелинейностью булевой функции. В случае четного п максимально возможное значение нелинейности равно 2п~1 - 2^п'2'~1. В случае нечетного п точное значение максимального расстояния неизвестно (поиск этого значения или его оценок представляет весьма любопытную и сложную комбинаторную задачу [89, 78]). Термин «максимально нелинейная функция» принят в русскоязычной литературе, тогда как в англоязычной широкое распространение получил термин «бент-функция» (от англ. bent - изогнутый, наклоненный). Аналогия между терминами не полная. При четном числе переменных п бент-функции и максимально нелинейные функции совпадают, а при нечетном п бент-функции (в отличие от максимально нелинейных) не существуют.Преобразованием Уолша-Адамара булевой функции / от п переменных называется целочисленная функция Wf, заданная на множестве Z^ равенствомwf(v)= j2(-i){u,v)®f{u)-u£Z™Справедливо равенство Парсеваля, Yl (Wf(v)) = 22п. Поскольку число всех коэф-фициентов Wf(v) равно 2п, из равенства следует, что максимум модуля коэффициента Уолша-Адамара не может быть меньше величины 2пv), где au>v = -^j^Wfiu ф v), является матрицей Адамара; (ш) матрица D = (dUyV), где du>v = (K-\yyu®v>i является матрицей Адамара; (iv) для любого ненулевого вектора и функция f(v) ®/(v®u) сбалансирована, т. е. принимает значения 0 и 1 одинаково часто.Пункт (iv) теоремы носит название критерия распространения РС(гг) порядка п. В качестве важного свойства бент-функций можно отметить следующий факт [НО], согласно [5] полученный В. А. Елисеевым и О. П. Степченковым еще в 1962 г.Теорема 2. Степень нелинейности deg(/) любой бент-функции / от п ^ 4 переменных не превосходит числа п/2.Бент-функции: результаты и приложения. Обзор работ19Аффинная функция, как нетрудно видеть, не может быть бент-функцией. Сразу отметим, что бент-функции любой другой возможной степени существуют. Например, квадратичной бент-функцией при любом четном п является функцияf(vi,...,vn) = viv2 e v3v4 e... е vn_xvn.(i)Интересно, что любую другую квадратичную бент-функцию д можно получить из / аффинным преобразованием. Приведем необходимое определение. Булевы функции / и д от п переменных аффинно эквивалентны, если существуют невырожденная n x n матрица А, векторы 6, с длины п и константа Л Е Z2, такие, чтоg(v) = f(Av е ъ) е (с, v) е л.Согласно [52] (см. [9, 62]), выполняетсяТеорема 3. Любая квадратичная бент-функция от п переменных аффинно эквивалентна функции (1).Для бент-функций степени 3 и выше подобных результатов нет. СправедливаТеорема 4. Класс *3П бент-функций замкнут относительно(i) любого невырожденного аффинного преобразования переменных;(И) прибавления любой аффинной функции.В силу теоремы 4 имеет смысл вопрос об аффинной классификации бент-функций, который для функций степени ^ 3 пока остается открытым. Подробнее о методах аффинной и линейной классификации булевых функций можно прочитать в [18].Часто с бент-функцией / связывают так называемую дуальную булеву функцию f от п переменных, которая определяется равенством Wf(v) = 2n^2(-l)^v\ Определение корректно, поскольку Wf(v) = ±2га'2 для каждого вектора v. Несложно доказать, чтобулева функция / является бент-функцией. Справедливо / = /. Отметим, что если deg(/) = n/2, то степень / также максимальна: deg(/) = n/2. Самодуальные бент-функции, т. е. такие, что / = /, изучались в [43].Дуальные бент-функции потребуются далее в теореме 14.2.2. X а р а к т е р и з а ц и и бент-функцийРассмотрим ряд попыток найти бент-функциям комбинаторные или алгебраические «эквиваленты».С самого начала бент-функции изучались в связи с разностными множествами [62]. Пусть конечная абелева группа G имеет порядок v и дана в аддитивной записи. Подмножество D С G мощности к называется разностным множеством с параметрами (v, к, Л), если каждый ненулевой элемент g E G можно представить в виде g = b - d ровно Л способами, где b, d - элементы множества D. Справедлива [62]Теорема 5. Булева функция / от п переменных является бент-функцией, если и только если множество D = { (v, f(v)) | v E Ж?} является разностным множеством с параметрами (2га+1, 2га, 2П~1) в аддитивной группе Z^+1.Разностные множества с приведенными в теореме 5 параметрами называются элементарными адамаровыми. Примеры таких множеств были известны еще до появления бент-функций [62].Известно [17], что разностные множества тесно связаны с блок-схемами. Напомним, что блок-схемой с параметрами (v,k,X) называется система fc-элементных подмножеств (или блоков) f-элементного множества, такая, что каждая пара различных20Н. Н. Токареваэлементов содержится ровно в Л блоках. Блок-схема симметрична, если число блоков равно числу элементов, т. е. равно v. Теорема 5 имеет следующий эквивалентный вид.Теорема 6. Булева функция / от п переменных является бент-функцией, если и только если система множеств Dz = D ф z, где вектор z пробегает Z^+ , является симметричной блок-схемой с параметрами (2га+1, 2п, 2п~1).В. В. Ященко [19] в 1997 г. предложил следующее описание класса бент-функций. В его основе лежит тот факт, что любая булева функция / от п переменных может быть представлена в виде линейного разветвленияf(u', и") = (и', h{u")) Ф д{и"), где и' G Ъ\, и" G Ъ\(2)для подходящих чисел г ж к таких, что п = г + к, отображения h : Z,2 -> Ъг2 и булевой функции д от к переменных. Максимально возможное значение г в таком представлении называется индексом линейности булевой функции /.Подмножество М пространства Ж2 называется бент-множеством, если его мощность равна 22£ при некотором £ и для любого ненулевого вектора z G Z,2 множество М Г) (z (В М) либо пусто, либо имеет четную мощность.Пара (д; М), где д - булева функция от к переменных, М - бент-множество, называется частичной бент-функцией, если для любого v' G Ъг2 и ненулевого v" G Zg функция д{и") ф д{и" ф v") сбалансирована на множестве {v', v") ф М.Теорема 7. Булева функция / вида (2) является бент-функцией тогда и только тогда, когда п > 2г и для любого вектора и' G 1/2 выполняются условия: (i) мощность множества h~l{u') равна 2п~2г] (И) множество h~l(u') является бент-множеством; (ш) пара (д; h~l(u')) является частичной бент-функцией.Позднее в 2004 г. К. Карле независимо предложил конструкцию бент-функций, представляющую собой частный случай данного описания (см. далее теорему 17).Приведем геометрическое описание класса бент-функций, которое предложили в 1998 г. К. Карле и Ф. Гуилло [47] (см. также более раннюю работу [46]).Пусть / - булева функция от п переменных. Пусть Ind^ : Ж2 ->■ Z2 - характеристическая функция подмножества S С Ж2, т. е. Ind^ принимает значение 1 на элементах из S и значение 0 на остальных элементах.Теорема 8. Функция / является бент-функцией тогда и только тогда, когда существуют подпространства Е\,... , Е^ размерности п/2 или (п/2) + 1 пространства Z,2 и ненулевые целые числа т\,... , nik, такие, что для любого v G ГЕ2Ь выполняетсякJ]mjnde» = ±2(ra/2)-1Ind{0}H + f(v).г=1Авторы [47] вводят ограничения на способ выбора пространств Е\,... , Е^, при которых такой выбор становится единственным для каждой бент-функций. Таким образом, можно говорить об однозначности такого представления.Другой подход предложили в 1999 г. А. Бернаскони и Б. Коденотти [26], затем к ним присоединился и Дж. Ван-дер-Кам [27].Пусть / - булева функция от п переменных. Через supp(/) обозначим ее носитель, т. е. множество всех двоичных векторов длины п, на которых функция / принимаетБент-функции: результаты и приложения. Обзор работ21значение 1. Рассмотрим граф Кэли Gf = G(Z^,supp(/)) булевой функции /. Вершинами графа являются все векторы длины п. Две вершины и, v соединяются ребром, если вектор и® v принадлежит множеству supp(/).Граф G называется сильно регулярным (strongly regular), если существуют неотрицательные целые числа Л, [i такие, что для любых двух вершин х, у общее число смежных им вершин равно Л или ц в зависимости от того, соединены вершины х, у ребром или нет. В работе [27] доказанаТеорема 9. Булева функция / является бент-функцией тогда и только тогда, когда граф Gf является сильно регулярным, причем А = ц.С. В. Агиевич в 2000 г. [22] установил биекцию между множеством всех бент-функций от п переменных и множеством бент-прямоугольников.Пусть / - булева функция от п переменных, п = r-\-k. Вектор W f коэффициентов Уолша-Адамара назовем спектральным вектором функции /. Представим двоичный вектор / в виде / = (/т, , /(2г))> гДе каждый вектор f и\ имеет длину 2к. Пусть /(г) - булева функция от к переменных, для которой f ,^ является вектором значений, г = 1,..., 2Г. Свяжем с функцией / матрицу .Л/f/ размера 2r x 2к, строками которой являются спектральные векторы Wf(1),... , Wf(2r .Матрица размера 2r x 2к называется бент-прямоуголъником, если каждая ее строка и каждый столбец, домноженный на 2г~(п'2>, являются спектральными векторами для подходящих булевых функций. Согласно [22], выполняетсяТеорема 10. Булева функция / является бент-функцией тогда и только тогда, когда матрица Aif является бент-прямоугольником.Данный подход позволил [22] дать описание всех бент-функций от шести переменных (см. далее) и получить алгоритм построения специального класса бент-функций от произвольного числа переменных п. В работе [24] СВ. Агиевич исследует соответствие между бент-прямоугольниками и регулярными д-значными бент-функциями [83], описывает аффинные трансформации первых и переводит на язык бент-прямоугольников основные конструкции бент-функций. Дальнейшее развитие этого подхода представляется весьма перспективным.Здесь перечислены лишь некоторые возможные характеризации бент-функций.2.3. Бент-функции от малого числа переменныхЗадача описания всех бент-функций от п переменных решена лишь при малых значениях п. Приведем эти результаты.п = 2. Функция i>ii>2 является представителем единственного класса аффинной эквивалентности. Класс ОЗг состоит из восьми функций. Это все функции, векторы значений которых содержат нечетное число единиц.п = 4. Множество ®4 состоит из 896 булевых функций, причем каждая функция является квадратичной. Все бент-функции от четырех переменных аффинно эквивалентны функции ViV2®VsV4- Множество 034 можно разделить на 28 классов по 32 функции. Алгебраические нормальные формы функций из каждого класса обладают одинаковой квадратичной частью, произвольной линейной частью и любым свободным членом. Если рассмотреть граф на множестве переменных, а ребрами соединить те вершины, которые образуют слагаемое в квадратичной части АНФ функции, то эти 28 типов можно задать следующим образом:22Н. Н. ТокареваПИЙ(3)(12) (12)(1)Под каждым графом указано число типов, которые он определяет. Например, имеется 3 типа квадратичной части, состоящей из двух слагаемых: V\V2 Ф v3v4, V\V3 © v2v4, V\V4 (BV2V3, и только один тип из шести слагаемых.п = 6. Аффинная классификация бент-функций от 6 переменных была получена еще в работе О. Ротхауса [110]: множество 036 состоит из четырех классов аффинной эквивалентности, представителями которых являются следующие функции:V\V2 ®v3v4 ®v5v6,v\v2v3 Ф v\v4 ф v2v5 ф v3v6,V\V2V3 ф V2V4V5 ф ViV2 ф ViV4 Ф V2V6 ф V3V5 ф V4V5,V\V2V3 ф W2W4W5 Ф V3V4V6 ф WiW4 Ф W2W6 Ф V3V4 ф W3W5 Ф V3V6 ф W4W5 Ф W4W6.В работе [113] приводится подобная алгебраическая классификация. Пусть GF(26) = = {0, l,a,a2,... ,Q!62}, где a - корень многочлена х6 + х + 1. Пусть булева функция отождествляется с функцией f{v) : GF(26) -> GF(2), где t; рассматривается как элемент поля GF(26). Тогда в качестве представителей классов аффинной эквивалентности множества 036 можно выбрать функции: tr(v3 + a5v5), tr(o;3i;7 + v9), ti(av3 + a6v7 + a60v13), ti(v7 + avg + v21), где tr - функция следа из GF(26) в GF{2).Дж;. Диллоном [62] (см. также [30]) было показано, что любая бент-функция от шести переменных аффинно эквивалентна функции из класса Мэйорана-МакФарланда (см. далее теорему 16).Класс 036 содержит 5 425 430 528 ~ 232'3 функций. Описание было дано СВ. Аги-евичем [22] с использованием бент-квадратов, т. е. бент-прямоугольников при г = к (см. теорему 10). Скажем, что две бент-функции квадратно-эквивалентны, если бент-квадрат одной из них может быть получен из бент-квадрата второй изменением знаков элементов и перестановкой строк и столбцов. Пусть г = к = 3. Все функции класса 036 разбиваются на восемь классов квадратной эквивалентности. Ниже приводятся соответствующие бент-квадраты размера 23 х 23 и количество функций в каждом классе.80000000-4 4440000-4 4440000-4 4440000080000004-44400004-44400004-4004400008000004 4-4400000 0-44440040-4 04040000800004 4 4-40000004-4 44004 0 0-4044000008000000080004 4 0 0-44000 4 4 0 0 4-4000000800000008004 4 0 0 4-4000 4 0 4-40400000008000000080000000800 0 4 4 4-40000000008000000080000000800000008(215-32-5-7) (218-3-72) (221-3-72) (225 3 7)-4 4440000 -4 4440000 -4 4440000 -6 2222222 4-4 440000 4-4 440000 4-4 004400 2-6 2222224 4-4400000 0-4444004 0-40404022-6 222224 4 4-400000 0 4-44400400-4 0440222-6 22220 0 0 0-44440000-4 4440 4 4 0-40042222-6 2220 0 0 0 4-4440 0 0 0 4-4440 4 0 4 0-40422222-6 220 0 0 0 4 4-444 4 0 0 0 0-440 0 4 4 0 0-44222222-6 20 0 0 0 4 4 4-44 4 0 0 0 0 4-40 0 0 0 4 4 4-42222222-6(219-72)(220-32-72) (223-3-72) (223 З2 5 7)Бент-функции: результаты и приложения. Обзор работ23Отметим, что мощность ОЗб была найдена раньше в диссертации Б. Пренела [104]. В 2004 г. авторы [92] перечислили функции класса 036 способом, отличным от приведенного в [22].п = 8. Аффинная классификация бент-функций от восьми переменных степени не выше 3 была получена в работах [30, 74] (см. также работу [23], посвященную кубическим бент-функциям специального вида). Бент-функции от восьми переменных степени не выше 3 делятся на 10 классов аффинной эквивалентности, представителями которых являются:V\V2 Ф V3V4 ф V5V6 ф V7V8,V\V2V3 ф V\V4 ф V2V5 ф V3V6 Ф V7V8,V\V2V3 ф V2V4V5 Ф V3V4 Ф V2V6 ф V\V7 ф V5V8,V\V2V3 ф V2V4V5 ф ViV3 ф ViV5 ф V2V6 ф V3V4 ф V7Vg,V\V2V3 ф V2V4V5 ф V3V4V6 ф V3V5 ф V2V6 ф V2V5 ф W1W7 ф W4W8,VlV2V3 ф W2W4W5 ф W3W4W6 ф V3V5 ф W1W3 ф ViV4 ф W2W7 Ф W6W8,V\V2V3 ф W2W4W5 Ф %Ш«6 Ф V3V5 ф W2W6 Ф V2V5 ф WiW2 Ф W1W3 ф V1V4 ф W7W8,W1W2W3 Ф V2V4V5 ф ШШ^б Ф V3V5 ф WiW6 Ф W2W7 Ф V4V8,V\V2V7 ф W3W4W7 ф V5V6V7 ф W1W4 ф V3V6 ф W2W5 Ф W4W5 Ф V7V%,^1^3 Ф W2W4W5 Ф V3V4V6 ф W1W4W7 ф V3V5 ф W2W7 Ф W1W5 ф ViV6 ф W4W8.В диссертации [30] также показано, что все эти функции аффинно эквивалентны функциям из класса Мэйорана-МакФарланда.Нижняя 270'4 и верхняя 2129'2 оценки числа всех функций в классе Q3g были получены соответственно в [22] и [86]. Некоторые результаты по частичному описанию класса 038 на основе исследования групп автоморфизмов бент-функций приводит У. Демп-вольф в работах [60, 61]. М. Янг, К. Менг и X. Жанг [113] показали, что множество Q3g состоит не менее чем из 129 классов аффинной эквивалентности. Представители всех найденных ими классов приводятся в их работе. Это 53 функции вида tr(a%vdl + ajvd2 + akvdi) и 76 функций вида tr(a%vdl + ajvd2 + akvdi + aevdi), где tr : GF(28) -> GF{2) - функция следа. Авторы [72] показали, что множество Q38 C\VS содержит функции из не менее чем шести классов аффинной эквивалентности, где VS - класс бент-функций, полученных методом частичного расщепления (см. далее теорему 18).По последним данным (2009) аффинная классификация бент-функций от восьми переменных четвертой степени завершена [84]. Описаны все 536 возможных вариантов для части четвертой степени2 АНФ бент-функции от восьми переменных. Установлено точное число всех бент-функций от восьми переменных [84]. Оно равно 29 х 193 887869 660 028 067003 488 010 240 ~ 2106>29.При п ^ 10 класс 03га не описан, его мощность неизвестна. В работе [113] построено большое число бент-функций от десяти переменных; установлено, что среди них содержится как минимум несколько сотен попарно аффинно неэквивалентных функций. Некоторую информацию о классах 53 ю, 23 \2 можно найти на сайте [61].2.4. Оценки числа бент-функцийИнформации об оценках числа бент-функций от п переменных немного. Приведем нижнюю оценку этого числа, которую дает конструкция Мэйорана-МакФарланда (см. далее теорему 16).Теорема 11. Справедливо |«8га| ^ 22"/2(2га/2)!.2Под частью степени i АНФ функции понимаем набор всех тех слагаемых ее АНФ, степень которых равна г.24Н. Н. ТокареваА/ о(п/2) + 1 \ on/2 /г\( /р\ | 1симптотически, эта оценка имеет вид () V2(п'г>+1тг, или, если совсем грубо, 22 . Следует отметить, что в работе [22] приводится уточнение оценки теоремы 11,являющееся на данный момент лучшим. Однако охарактеризовать асимптотическоеповедение оценки [22] достаточно трудно.Тривиальная верхняя оценка следует из того факта, что, согласно теореме 2, степень бент-функции не превышает п/2. Имеем|Ип| ^21+(i) + ( 2 )+"+( га/2)=2-1+Кга/2)_К. Карле и А. Клаппер в 2002 г. [48] немного улучшили эту оценку: Теорема 12. Пусть п ^ 6 и выполняется е = „, /-л-,-. Тогдаlay « /w+'( v» )-2""+(и") = fu>>(u'). Тогда / - бент-функция, если и только если ди> - бент-функция для любого и'.Бент-функции: результаты и приложения. Обзор работ25Заметим, что теорема 13 следует из теоремы 14. Итеративный способ построения бент-функций от п + 2 переменных из бент-функций от п переменных приводится в [56]. В качестве упражнения можно доказать следующий факт (см. [75]).Теорема 15. Пусть / - булева функция от п переменных, h - перестановка на Z£. Обозначим через h\,... , hn булевы функции такие, что h(v) = (h\(v),... , hn(v)). Функция / о h~l является бент-функцией, если для каждого и выполняетсяпdist(/,0^i) = 2ra-1±2(ra/2)-1.г=1К первичным конструкциям принадлежит простая и богатая конструкция Мэйо-рана-МакФарланда 1973 г. [63, 91].Теорема 16. Пусть h - любая перестановка на Z^ , пусть g - произвольная булева функция от п/2 переменных. Тогда функция f{u',u") = (u',h(u")) ф g{u") является бент-функцией от п переменных.Основной идеей конструкции служит, по выражению К. Карле [40], «конкатенация аффинных функций». Действительно, при каждом фиксированном значении переменных из второй половины функция / является аффинной от п/2 первых переменных. С другой стороны, аффинные функции возникают и при рассмотрении соответствующих бент-квадратов. А именно, бент-функция принадлежит классу Мэйорана-МакФар-ланда, если и только если строки и столбцы ее бент-квадрата являются спектральными векторами аффинных булевых функций [22].Из теоремы легко следует, что существуют бент-функции с любой степенью нелинейности d, такой, что 2 ^ d ^ п/2. Итак, в теореме 16 переменные функции / разбиваются пополам. В 2004 г. К. Карле [39] (см. также [40]) обобщил идею Мэйорана- МакФарланда, рассмотрев разбиение переменных на неравные части.Теорема 17. Пусть п = г + к. Пусть h : Z| ->■ Zg - любое отображение, такое, что для каждого вектора и длины г множество h~l(u) образует подпространство в Z| размерности п - 2г. Пусть g - булева функция от к переменных, сужение которой на h~l(u) для каждого и является бент-функцией при п > 2г. Тогда булева функция f(u', и") = (и', h{u")) ф д{и") является бент-функцией от п переменных.Отметим, что конструкция К. Карле имеет сильные сходства с методом описания бент-функций, предложенным В. В. Ященко [19] еще в 1997 г. (см. выше теорему 7).Теорема 16 представляет собой частный случай теоремы 17 при г = к = п/2.Следующая первичная конструкция Дж. Диллона [63] 1974 г. опирается на специальные семейства подпространств гг-мерного пространства и носит название частичного расщепления (Partial Spreads).Пусть Inds '■ Z^ -> Z2 - характеристическая функция подмножества S С Z^-.Теорема 18. Пусть число q равно 2i GF(2) - функция следа, т. е. tr(v) = v + v2 + + v2" . Бент-функции, имеющие видf{v)=ti{avd),где а £ GF*{2n) - некоторый параметр, называются степенными или мономиалъ-ными, а целое число d называется бент-показателем. Здесь GF*{2n) - множество ненулевых элементов поля. Бент-функции такого вида интересны в первую очередь для криптографических приложений в силу своей простой вычислимости. Хотя криптографы до сих пор не определились: считать простоту вычислимости бент-функции ее достоинством или скорее недостатком [40].Пусть gcd(-, ) - наибольший общий делитель двух чисел.Теорема 19. Следующие значения d являются бент-показателями:d = 2п'2 - 1(Диллон о, 1974, [63]);d = 2г + 1, где cd? ^ четно(показатель Голда |);d = 22k - 2k + 1, где gcd(fc, n) = 1(показатель Касами);d = (2k + I)2, где п = Ak,k нечетно(Канто-Леандер |, 2004, [87]);d = 22k + 2k + 1, где п = 6k(Канто-Шарпин-Карегян j, 2006, [35]).Известно, что три типа степенных бент-функций (в теореме их показатели помечены знаком |) можно описать с помощью конструкции Мэйорана-МакФарланда, а один тип (помечен знаком о) содержится в классе VS~. Существуют ли степенные бент-функции с другими показателями? Можно ли для степенных бент-функций найти простое комбинаторное описание? Ответов на эти вопросы пока нет.Вторая серия бент-функций состоит из функций видаf(v) = ti(aivdl +a2vd2)(3)для подходящих элементов а\,а2 £ GF{2n) и показателей d\,d2- Известны примеры таких функций со специальными степенными показателями - так называемыми показателями Нихо вида d = 2г mod (2ra/2 - 1). Без ограничения общности [67] пусть первый показатель равен d\ = {2^п/2"> - 1)^ + 1. Справедлива [69]Теорема 20. Если выполняется

Ключевые слова

булева функция , АНФ , преобразование Уолша-Адамара , нелинейность , бент-функция

Авторы

ФИООрганизацияДополнительноE-mail
Токарева Наталья Николаевна Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск кандидат физико-математических наук tokareva@math.nsc.ru
Всего: 1

Ссылки

Августинович С. В. Об одном свойстве совершенных двоичных кодов // Дискрет. анализ и исслед. операций. 1995. Т. 2. № 1. С. 4-6.
Амбросимов А. С. Свойства бент-функций q-значной логики над конечными полями // Дискретная математика. 1994. Т. 6. № 3. С. 50-60.
Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. 1962. Вып. 8. С. 337-339.
Кузнецов Ю. В., Шкарин С. А. Коды Рида-Маллера (обзор публикаций) // Математические вопросы кибернетики. 1996. Вып. 6. С. 5-50.
Кузьмин А. С., Марков В. Т., Нечаев А. А. и др. Бент-функции и гипербент-функции над полем из 2l элементов // Проблемы передачи информации. 2008. Т. 44. Вып. 1. С. 15-37.
Логачев О. А., Сальников А. А., Ященко В. В. Бент-функции на конечной абелевой группе // Дискретная математика. 1997. Т. 9. № 4. С. 3-20.
Логачев О. А., Сальников А. А., Ященко В. В. Некоторые характеристики «нелинейности» групповых отображений // Дискрет. анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 1. С. 40-54.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: Московский центр непрерывного математического образования, 2004. 470 с.
Мак-Вилъямс Ф. Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 745 с.
Молдовян А. А., Молдовян Н. А., Еремеев М. А. Криптография: от примитивов к синтезу алгоритмов. СПб.: БХВ-Петербург, 2004.
Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991. 240 с.
Сиделъников В. М. О взаимной корреляции последовательностей // Проблемы кибернетики. 1971. Т. 24. С. 15-42.
Сиделъников В. М. Об экстремальных многочленах, используемых при оценках мощности кода // Проблемы передачи информации. 1980. Т. 14. Вып. 3. С. 17-30.
Солодовников В. И. Бент-функции из конечной абелевой группы в конечную абелеву группу // Дискретная математика. 2002. Т. 14. № 1. С. 99-113.
Токарева Н. Н. Бент-функции с более сильными свойствами нелинейности: k-бент-функции // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 4. С. 76-102.
Токарева Н. Н. Обобщения бент-функций. Обзор // Дискрет. анализ и исслед. операций. 2009. Т. 16
www.math.nsc.ru/~tokareva.
Холл М. Комбинаторика. М.: Мир, 1970. 424 с.
Черемушкин А. В. Методы аффинной и линейной классификации булевых функций // Труды по дискретной математике. М.: Физматлит, 2001. Т. 4. С. 273-314.
Ященко В. В. О критерии распространения для булевых функций и о бент-функциях // Пробл. передачи информации. 1997. Т. 33. Вып. 1. С. 75-86.
Ященко В. В. О двух характеристиках нелинейности булевых отображений // Дискрет. анализ и исслед. операций. Сер. 1. 1998. Т. 5. № 2. С. 90-96.
Adams С. On immunity against Biham and Shamir's «differential cryptanalysis» // Information Processing Letters. 1992. V. 41. P. 77-80.
Agievich S. V. On the representation of bent functions by bent rectangles // Fifth Int. Petrozavodsk conf. on probabilistic methods in discrete mathematics (Petrozavodsk, Russia, June 1-6, 2000). Proc. Boston: VSP, 2000. P. 121-135.
Available at <http://arxiv.org/abs/math/0502087>.
Agievich S. V. On the affine classification of cubic bent functions // Cryptology ePrint Archive, Report 2005/044,
available at <http://eprint.iacr.org/>.
Agievich S. V. Bent rectangles // NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security (Zvenigorod, Russia. September 8-18, 2007). Proc: Netherlands, IOS Press, 2008. P. 3-22.
Available at <http://arxiv.org/abs/0804.0209>.
Bending T. D., Fon-Der-Flaass D. G. Crooked Functions, Bent Functions and Distance Regular Graphs // Electronic J. Combinatorics. 1998. No. 5 (R34).
Bernasconi A., Codenotti B. Spectral analysis of Boolean functions as a graph eigenvalue problem // IEEE Trans. Computers. 1999. V. 48. No. 3. P. 345-351.
Bernasconi A., Codenotti В., VanderKam J. M. A characterization of bent functions in terms of strongly regular graphs // IEEE Trans. Computers. 2001. V. 50. No. 9. P. 984-985.
Biham E., Shamir A.Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V. 4. No. 1. P. 3-72.
Bracken C., Leander G. New families of functions with differential uniformity of 4 //Fourth International Conference BFCA - Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). Proc. to appear. P. 190-194.
Braeken A. Cryptographic properties of Boolean functions and S-boxes // Ph. D. Thesis, Katholieke Univ. Leuven, 2006.
Available at <http://www.сosic.esat.kuleuven.be/publications/thesis-129.pdf>
Budaghyan L., Carlet С., Leander G. On inequivalence between known power APN functions // Fourth International Conference BFCA - Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). Proc. to appear. P. 3-15.
Budaghyan L. Private Communication. 2008.
Budaghyan L., Pott A. On differential uniformity and nonlinearity of functions // Discrete Mathematics. 2009. V. 309. No. 1. P. 371-384.
Byrne E., McGuire G. On the non-existence of crooked functions on finite fields // WCC - International Workshop on Coding and Cryptography (Bergen, Norway, March 14-18, 2005). Proc. 2005. P. 316-324.
Canteaut A., Charpin P., Kuyreghyan G. A new class of monomial bent functions // Finite Fields and Applications. 2008. V. 14. No. 1. P. 221-241.
Carlet С. Generalized Partial Spreads // IEEE Trans. Inform. Theory. 1995. V. 41. No. 5. P. 1482-1487.
Carlet С. A construction of bent functions // Finite Fields and Applications, London mathematical society. 1996. Lecture series 233. P. 47-58.
Carlet С. On cryptographic complexity of Boolean functions // Proc. of the Sixth Conference on Finite Fields with Applications to Coding Theory, Cryptography and Related Areas. Springer, G. L. Mullen, H. Stichtenoth and H. Tapia-Recillas Eds. 2002. P. 53-69.
Carlet С. On the confusion and diffusion properties of Maiorana-McFarland's and extended Maiorana-McFarland's functions // Special Issue «Complexity Issues in Coding Theory and Cryptography» dedicated to Prof. Harald Niederreiter on the occasion of his 60th birthday, J. Complexity. 2004. V. 20. P. 182-204.
Carlet С. Boolean Functions for Cryptography and Error Correcting Codes // Chapter of the monograph «Boolean Methods and Models», Cambridge Univ. Press (P. Hammer, Y. Crama eds.), to appear. Prelim, version is available at www-rocq.<inria.fr/secret/Claude.Carlet/chap-fcts-Bool>.pdf.
Carlet С. Vectorial Boolean Functions for Cryptography //Chapter of the monograph «Boolean Methods and Models», CambridgeUniv. Press (P. Hammer, Y. Crama eds.), to appear. Prelim, version isavailable at www-rocq.<inria.fr/secret/Claude.Carlet/chap-vectorial-fcts.pdf>.
Carlet C., Charpin P., Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Designs, Codes and Cryptography. 1998. V. 15. No. 2. P. 125-156.
Carlet С., Danielsen L.-E., Parker M. G., Sole P. Self Dual Bent Functions // Fourth International Conference BFCA - Boolean Functions: Cryptography and Applications (Copenhagen, Denmark, May 19-21, 2008). Proc. to appear. P. 39-52.
Carlet C., Ding С. Highly nonlinear mappings // J. Complexity. 2004. V. 20. No. 2-3. P. 205-244.
Carlet C., Ding C., Niederreiter H. Authentication schemes from highly nonlinear functions // Designs, Codes and Cryptography. 2006. V. 40. No. 1. P. 71-79.
Carlet C., Guillot P. A characterization of binary bent functions // J. Combin. Theory. Ser. A. 1996. V. 76. No. 2. P. 328-335.
Carlet C., Guillot P. An alternate characterization of the bentness of binary functions, with uniqueness // Designs, Codes and Cryptography. 1998. V. 14. P. 133-140.
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).Ргос. 2002. Р. 307-314.
The full version will appear in Lecture Notes dedicated to Philippe Delsarte. Available at http://www.cs <http://www.es>.engr.uky.edu/~klapper/ps/bent.ps.
<http://www.faqs.org/rfcs/rfc2144.html-CAST-128>. Rfc 2144 - the cast-128 encryption algorithm-1997.
Chabaud F., Vaudenay S. Links between Differential and Linear Cryptanalysis // Advances in Cryptology - EUROCRYPT '94, International Conference on the Theory and Application of Cryptographic Techniques. (Perugia, Italy. May 9-12, 1994) Proc. Springer, 1995. P. 356-365 (Lecture Notes in Comput. Sci. V. 950).
Charpin P., Pasalic E., Tavernier С. On bent and semi-bent quadratic Boolean functions // IEEE Trans. Inform. Theory. 2005. V. 51. No. 12. P. 4286-4298.
Chase P. J., Dillon J. F., Lerche K. D. Bent functions and difference sets // NSA R41 Technical Paper. September, 1970.
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 Comput. Sci. V. 917).
Clark J. A., Jacob J.L. Two-stage optimisation in the design of Boolean functions // 5th Australian Conference on Information Security and Privacy. (Brisbane, Australia, July 10-12, 2000). Proc. Springer-Verlag, 2000. P. 242-254 (Lecture Notes in Comput. Sci. V. 1841).
Clark J. A., Jacob J. L., Maitra S., Stanica P. Almost Boolean Functions: the Design of Boolean Functions by Spectral Inversion. // Computational Intelligence. Special Issue on Evolutionary Computing in Cryptography and Security. 2004. V. 20. No. 3. P. 450-462.
Climent J.-J., Garcia F. J., Requena V. On the construction of bent functions of n + 2 variables from bent functions of n variables. // Advances in Math. of Communications. 2008. V. 2. No. 4. P. 421-431.
Van Dam E. R., Fon-Der-Flaass D. G. Uniformly Packed Codes and More Distance Regular Graphs from Crooked Functions // J. Algebraic Combinatorics. 2000. V. 12. No. 2. P. 115-121.
Van Dam E. R., Fon-Der-Flaass D. G. Codes, graphs, and schemes from nonlinear functions // European J. Combinatorics, 2003. V. 24. No. 1. P. 85-98.
Delsarte P. An algebraic approach to the association schemes of coding theory // Ph. D. Thesis, Univ. Catholique de Louvain, 1973.
Dempwolff U. Automorphisms and equivalence of bent functions and of difference sets in elementary Abelian 2-groups // Communications in Algebra. 2006. V. 34. No. 3. P. 1077-1131.
<http://www.mathematik.uni-kl.de/~dempw/>-Homepage of U. Dempwolff. See the section «Bent Functions in Dimensions 8,10,12». 2009.
Dillon J. F. A survey of bent functions // The NSA Technical J. 1972. Special Issue. P. 191-215.
Dillon J. F. Elementary Hadamard Difference sets // Ph. D. Thesis. Univ. of Maryland, 1974.
Dobbertin H. Construction of bent functions and balanced Boolean functions with high nonlinearity // Fast Software Encryption, Second International Workshop - FSE'95. (Leuven, Belgium, December 14-16, 1994) Proc. Berlin: Springer, 1995. P. 61-74 (Lecture Notes in Comput. Sci. V. 1008).
Dobbertin H. Almost perfect nonlinear power functions over GF(2n): the Niho case // Inform. and Comput. 1999. V. 151. No. 1-2. P. 57-72.
Dobbertin Н. Almost perfect nonlinear power functions over GF(2n): a new case for n divisible by 5 // Finite Fields and Applications FQ5 (Augsburg, Germany, August 2-6, 2000). Proc. Springer / Eds. D. Jungnickel, H. Niederreiter. 2000. P. 113-121.
Dobbertin H., Leander G. A survey of some recent results on bent functions // Sequences and their applications. - SETA 2004. Third Int. conference (Seoul, Korea, October 24-28, 2004). Revised selected papers. Berlin: Springer, 2005. P. 1-29 (Lecture Notes in Comput. Sci. V. 3486).
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/>.
Dobbertin H., Leander G., Canteaut A., et al. Construction of Bent Functions via Niho Power Functions // J. Combin. Theory. Ser. A. 2006. V. 113. No. 5. P. 779-798.
Available at <http://www-rocq.inria.fr/secret/Anne.Canteaut/Publications/index-pub.html>.
Fuller J. E. Analysis of affine equivalent Boolean functions for cryptography // Ph. D. thesis, Queensland University of Technology. Brisbane, Australia. 2003.
Available at <http://eprints.qut.edu.au/15828/>.
Fuller J. E., Dawson E., Millan W. Evolutionary generation of bent functions for cryptography // The 2003 Congress on Evolutionary Computation. 2003. CEC apos;03. V. 3. P. 1655-1661.
Gangopadhyay S., Sharma D., Sarkar S., Maitra S. On Affine (Non) Equivalence of Bent Functions // CECC'08 - Central European Conference on Cryptography (Graz, Austria, July 2-4, 2008). Proc. 2008.
Available at <http://www.math.tugraz>.at/~cecc08/abstracts/cecc08_abstract_25.pdf.
Grocholewska-Czuryio A. A study of differences between bent functions constructed using Rothaus method and randomly generated bent functions // J. Telecommunications and Information Technology. 2003. No. 4. P. 19-24.
Available at <http://www.itl.waw.pl/czasopisma/JTIT/2003/4/19.pdf>.
Hou X.-D. Cubic bent functions // Discrete Mathematics. 1998. V. 189. P. 149-161.
Hou X.-D., Langevin P. Results on bent functions // J. Comb. Theory, Series A. 1997. V. 80. P. 232-246.
Hu H., Feng D. On quadratic bent functions in polynomial forms // IEEE Trans. Inform. Theory 2007. V. 53. No. 7. P. 2610-2615.
Kantor W. M. Codes, Quadratic Forms and Finite Geometries // Proceedings of Symposia in Applied Math. 1995. V. 50. P. 153-177.
Available at http://darkwing.uoregon.edu/~kantor/.
Kavut S., Maitra S., Yucel M. D. Search for Boolean functions with excellent profiles in the rotation symmetric class // IEEE Trans. Inform. Theory. 2007. V. 53. No. 5. P. 1743-1751.
Kerdock A. M. A class of low-rate non-linear binary codes // Inform. Control. 1972. V. 20. No. 2. P. 182-187.
Khoo K., Gong G., Stinson D. R. A new family of Gold-like sequences // ISIT - IEEE Int. Symposium on Information Theory (Lausanne, Switzerland, June 30-July 5, 2002). Proc. 2002. P. 181.
Khoo K., Gong G., Stinson D. R. A new characterization of semi-bent and bent functions on finite fields // Designs, Codes and Cryptography. 2006. V. 38. No. 2. P. 279-295.
Krotov D. S., Avgustinovich S. V. On the Number of 1-Perfect Binary Codes: A Lower Bound // IEEE Trans. Inform. Theory. 2008. V. 54. No. 4. P. 1760-1765.
Kumar P. V., Scholtz R. A., Welch L. R. Generalized bent functions and their properties // J. Combin. Theory. Ser. A. 1985. V. 40. No. 1. P. 90-107.
<http://langevin.univ-tln.fr/project/quartics/>Classification of Boolean Quartics Forms in eight Variables (Langevin P.). 2008.
Langevin P., Leander G. Monomial bent functions and Stickelberger's theorem // Finite Fields and Applications. 2008. V. 14. P. 727-742.
Langevin P., Rabizzoni P., Veron P., Zanotti J.-P. On the number of bent functions with 8 variables // Second International Conference BFCA - Boolean Functions: Cryptography and Applications (Rouen, France, March 13-15, 2006). Proc. 2006. P. 125-135.
Leander N. G. Monomial bent functions // IEEE Trans. Inform. Theory. 2006. V. 52. No. 2. P. 738-743.
Leander N. G., Langevin P. On exponents with highly divisible Fourier coefficients and conjectures of Niho and Dobbertin // Algebraic Geometry and its applications (France, May 7-11, 2007) Proc. 2008. P. 410-418.
Maitra S., Sarkar P. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables // IEEE Trans. Inform. Theory. 2002. V. 48. No. 9. P. 2626-2630.
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 Comput. Sci. V. 765).
McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory. Ser. A. 1973. V. 15. No. 1. P. 1-10.
Meng Q., Yang M. G., Zhang H., Cui J.-S. A novel algorithm enumerating bent functions // Cryptology ePrint Archive, Report 2004/274, available at <http://eprint.iacr.org/>.
Meng Q., Zhang H., Wang Z. Designing bent functions using evolving computing // Acta Electronica Sinica. 2004. No. 11. P. 1901-1903.
Millan W., Clark A., Dawson E. An effective genetic algorithm for finding highly nonlinear Boolean functions // First Int. conference on Information and Communications Security -ICICS'97. (Beijing, China, November 11-14, 1997). Proc. Springer Verlag, 1997. P. 149-158 (Lecture Notes in Comput. Sci. V. 1334).
Millan W., Clark A., Dawson E. Smart hill climbing finds better Boolean functions // Workshop on Selected Areas in Cryptology. 1997. Workshop record. P. 50-63.
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 Comput. Sci. V. 547).
Nyberg K. Differentially uniform mappings for cryptography // Advances in cryptology - EUROCRYPT'1993. Int. conference on the theory and application of cryptographic techniques (Lofthus, Norway. May 23-27, 1993). Proc. Berlin: Springer, 1994. P. 55-64 (Lecture Notes in Comput. Sci. V. 765).
Olejdr D., Stanek M. On cryptographic properties of random Boolean functions // J. Universal Computer Science. 1998. V. 4. No. 8. P. 705-717.
Olsen J.D., Scholtz R. A., Welch L. R. Bent-function sequences // IEEE Trans. Inform. Theory. 1982. V. 28. No. 6. P. 858-864.
Parker M. G. The constabent properties of Golay-Davis-Jedwab sequences // IEEE International Symposium on Information Theory - ISIT'2000. (Sorrento, Italy, June 25-30, 2000). Proc. 2000. P. 302.
Parker M. G., Pott A. On Boolean functions which are bent and negabent // Sequences, Subsequences, and Consequences - SSC 2007 - International Workshop. (Los Angeles, СА, USA, May 31 - June 2, 2007). Proc. Berlin: Springer, 2007. P. 9-23 (Lecture Notes in Comput. Sci. V. 4893).
Paters on K. G. Sequences For OFDM and Multi-code CDMA: two problems in algebraic Coding Theory // Sequences and their applications. - Seta 2001. Second Int. Conference (Bergen, Norway, May 13-17, 2001). Proc. Berlin: Springer, 2002. P. 46-71.
Preneel В., 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 Comput. Sci. V. 473).
Preneel В. Analysis and design of cryptographic hash functions //Ph. D. thesis, Katholieke Universiteit Leuven, 3001 Leuven, Belgium. 1993.
Qu C., Seberry J., Pieprzyk J. Homogeneous bent functions // Discrete Appl. Math. 2000. V. 102. No. 1-2. P. 133-139.
Riera G., Parker M. G. Generalised Bent Criteria for Boolean Functions (I) // IEEE Trans. Inform. Theory 2006. V. 52. No. 9. P. 4142-4159.
Rodier F. Asymptotic nonlinearity of Boolean functions// Designs, Codes and Cryptography. 2006. V. 40. No. 1. P. 59-70.
Preprint is available at <http://iml.univ-mrs.fr/editions/preprint2003/files/RodierFoncBool.pdf>
Rodier F. Private Communication. 2008.
Rothaus O. On bent functions // IDA CRD W.P. No. 169. 1966.
Rothaus O. On bent functions // J. Combin. Theory. Ser. A. 1976. V. 20. No. 3. P. 300-305.
Schmidt K-U. Quaternary Constant-Amplitude Codes for Multicode CDMA // Available at <http://arxiv.org/abs/cs.IT/0611162>.
Wang L., Zhang J. A best possible computable upper bound on bent functions // J. West of China. 2004. V. 33. No. 2. P. 113-115.
Yang M., Meng Q., Zhang H. Evolutionary design of trace form bent functions // Cryptology ePrint Archive, Report 2005/322,
available at <http://eprint.iacr.org/>.
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 Comput. Sci. V. 2045).
Yu N. Y., Gong G. Constructions of quadratic bent functions in polynomial forms // IEEE Trans. Inform. Theory 2006. V. 52. No. 7. P. 3291-3299.
 Бент-функции: результаты и приложения. Обзор работ             | ПДМ. 2009. № 1(3).

Бент-функции: результаты и приложения. Обзор работ | ПДМ. 2009. № 1(3).

Полнотекстовая версия