Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

Бент-функция


Бент-функция (от англ. bent — «изогнутый, наклонённый», ) — булева функция с чётным числом переменных, для которой расстояние Хэмминга от множества аффинных булевых функций с тем же числом переменных максимально. Бент-функции в этом смысле обладают максимальной степенью нелинейности среди всех функций с данным числом переменных и благодаря этому широко применяются в криптографии для создания шифров, максимально устойчивых к методам линейного и дифференциального криптоанализа.

В русскоязычной литературе используется близкий по смыслу термин «максимально нелинейная функция», число переменных таких функций не ограничивается чётными числами. Максимально нелинейная функция с чётным числом переменных является бент-функцией .

Определения

Расстояние Хэмминга для двух булевых функций n переменных — количество различий в значениях этих функций на полном множестве из 2n наборов переменных.

Аффинная (линейная) булева функция — булева функция, полином Жегалкина которой не имеет нелинейных членов, то есть членов, представляющих собой конъюнкцию нескольких переменных.

Степень нелинейности булевой функции deg(f) — число переменных в самом длинном слагаемом её полинома Жегалкина.

Нелинейность булевой функции N(f) — расстояние Хэмминга от данной функции до множества всех аффинных функций.

История

Бент-функции были введены в 1960-х годах Оскаром Ротхаузом (1927—2003), который в это время (с 1960 по 1966 годы) работал Институте оборонного анализа (IDA), где занимался криптографическими исследованиями. Его первая работа по бент-функциям относится к 1966 году, однако она была засекречена и в открытой печати появилась только в 1976 году.

В 1960-х годах В.А.Елисеев и О.П.Степченков занимались исследованием бент-функций в СССР, однако их работы до сих пор засекречены. Известно, что они называли бент-функции "минимальными функциями" и предложили конструкцию МакФарланда еще в 1962 году.

Свойства

Нелинейность бент-функций с числом переменных n (n — чётное) определяется соотношением , :

N ( f ) = 2 n − 1 − 2 n 2 − 1 {displaystyle N(f)=2^{n-1}-2^{{frac {n}{2}}-1}} .

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

Примеры бент-функций

Ниже приведены примеры бент-функций четырёх, шести и восьми переменных.

n = 4 : f 1 ( X ) = x 1 x 3 ⊕ x 2 x 4 ; N ( f 1 ) = 6 ; {displaystyle n=4:f_{1}(X)=x_{1}x_{3}oplus x_{2}x_{4};N(f_{1})=6;} n = 6 : f 2 ( X ) = x 1 x 2 x 3 ⊕ x 1 x 4 ⊕ x 2 x 5 ⊕ x 3 x 6 ; N ( f 2 ) = 28 ; {displaystyle n=6:f_{2}(X)=x_{1}x_{2}x_{3}oplus x_{1}x_{4}oplus x_{2}x_{5}oplus x_{3}x_{6};N(f_{2})=28;} n = 8 : f 3 ( X ) = x 1 x 2 x 3 ⊕ x 2 x 4 x 5 ⊕ x 1 x 2 ⊕ x 1 x 4 ⊕ x 2 x 6 ⊕ x 3 x 5 ⊕ x 4 x 5 ⊕ x 7 x 8 ; N ( f 3 ) = 120 ; {displaystyle n=8:f_{3}(X)=x_{1}x_{2}x_{3}oplus x_{2}x_{4}x_{5}oplus x_{1}x_{2}oplus x_{1}x_{4}oplus x_{2}x_{6}oplus x_{3}x_{5}oplus x_{4}x_{5}oplus x_{7}x_{8};N(f_{3})=120;} n = 8 : f 4 ( X ) = x 1 x 2 x 3 ⊕ x 2 x 4 x 5 ⊕ x 3 x 4 x 6 ⊕ x 1 x 4 ⊕ x 2 x 6 ⊕ x 3 x 4 ⊕ x 3 x 5 ⊕ x 3 x 6 ⊕ x 4 x 5 ⊕ x 4 x 6 ⊕ x 7 x 8 ; N ( f 4 ) = 120. {displaystyle n=8:f_{4}(X)=x_{1}x_{2}x_{3}oplus x_{2}x_{4}x_{5}oplus x_{3}x_{4}x_{6}oplus x_{1}x_{4}oplus x_{2}x_{6}oplus x_{3}x_{4}oplus x_{3}x_{5}oplus x_{3}x_{6}oplus x_{4}x_{5}oplus x_{4}x_{6}oplus x_{7}x_{8};N(f_{4})=120.}

Монография

В книге приведен детальный обзор результатов в области бент-функций. Рассматривается история открытия бент-функций, описываются их приложения в криптографии и дискретной математике. Исследуются основные свойства и эквивалентные представления бент-функций, классификации бент-функций от малого числа переменных, комбинаторные и алгебраические конструкции бент-функций, связь бент-функций с другими криптографическими свойствами. Изучаются расстояния между бент-функциями и группа автоморфизмов бент-функций. Рассматриваются верхние и нижние оценки числа бент-функций и гипотезы о его асимптотическом значении. Приводится детальный систематический обзор 25 различных обобщений бент-функций, рассматриваются открытые вопросы в данной области. Книга 2015 года содержит более 125 теорем о бент-функциях и существенно расширяет книгу , опубликованную в 2011 году.


(голосов:0)

Пожожие новости
FNV
Комментарии

Ваше Имя:   

Ваш E-Mail: