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

Двійкові бент-функції з відстанню Геммінга, що дорівнює 1 і нелінійністю $2^{2-1}-2^{\frac{2}{2}-1}=2-1=1$

Нелінійність бент-функції $x_1{x}_2+x_3{x}_4$ дорівнює $2^{4-1}-2^{\frac{4}{2}-1}=8-2=6$

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

Близьким за змістом є термін «максимально нелінійна функція», кількість змінних таких функцій не обмежується парними числами. Максимально нелінійна функція з парною кількістю змінних є бент-функцією.

Визначення

Відстань Геммінга для двох булевих функцій Шаблон:Mvar змінних — кількість відмінностей у значеннях цих функцій на повній множині Шаблон:Math наборів змінних.

Шаблон:ЯкірАфінна (лінійна) булева функція — булева функція, поліном Жегалкіна якої не має нелінійних членів, тобто членів, що є кон'юнкцією декількох змінних.

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

Нелінійність булевої функції Шаблон:Math — відстань Геммінга від даної функції до множини всіх афінних функцій.

Історія

Бент-функції запровадив у 1960-х роках Оскар Ротгауз (1927—2003), який тоді (від 1960 до 1966 року) працював у Шаблон:Нп (IDA), де займався криптографічними дослідженнями. Його перша робота з бент-функцій відноситься до 1966 року, проте вона була засекречена й у відкритій пресі з'явилася тільки 1976 року.

У 1960-х роках В. А. Єлісєєв та О. П. Степченков досліджували бент-функції в СРСР, проте їхні роботи досі засекречено. Відомо, що вони називали бент-функції «мінімальними функціями» і запропонували побудову Макфарланда ще 1962 року.

Властивості

Нелінійність бент-функцій із кількістю змінних Шаблон:Mvar (Шаблон:Mvar — парне) визначається співвідношенням:

$N(f)=2^{n-1}-2^{\frac{n}{2}-1}$.

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

Приклади бент-функцій

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

$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\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\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\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 року.