Русская Википедия:Бент-функция

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Boolean functions like 1000 nonlinearity.svg

Бинарные бент-функции с расстоянием Хэмминга, равным 1 и нелинейностью <math>2^{2-1} - 2^{\frac{2}{2}-1} = 2-1 = 1</math>

Файл:0001 0001 0001 1110 nonlinearity.svg

Нелинейность бент-функции <math>x_1 x_2~+~x_3 x_4</math> равна <math>2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6</math>

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

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

Определения

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

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

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

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

История

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

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

Свойства

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

<math> N(f) = 2^{n-1} - 2^{\frac{n}{2}-1}</math>.

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

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

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

<math> n=4: f_1(X)=x_1x_3 \oplus x_2x_4 ; N(f_1) = 6;</math>

<math> n=6: f_2(X)=x_1x_2x_3 \oplus x_1x_4 \oplus x_2x_5 \oplus x_3x_6; N(f_2) = 28;</math>

<math> n=8: f_3(X)=x_1x_2x_3 \oplus x_2x_4x_5 \oplus x_1x_2 \oplus x_1x_4 \oplus x_2x_6 \oplus x_3x_5 \oplus x_4x_5 \oplus x_7x_8; N(f_3) = 120;</math>

<math> n=8: f_4(X)=x_1x_2x_3 \oplus x_2x_4x_5 \oplus x_3x_4x_6 \oplus x_1x_4 \oplus x_2x_6 \oplus x_3x_4 \oplus x_3x_5 \oplus x_3x_6 \oplus x_4x_5 \oplus x_4x_6 \oplus x_7x_8; N(f_4) = 120.</math>

Монография

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