Верхняя оценка алгебраической иммунности некоторых бентфункций Диллона | ПДМ. 2013. № 6 (Приложение).

Верхняя оценка алгебраической иммунности некоторых бентфункций Диллона

Получена верхняя оценка алгебраической иммунности некоторых бент-функций Диллона. Приводится степень бент-функций максимальной алгебраической иммунности, предложенных З. Ту и Й. Денгом.

Algebraic immunity upper bound for some Dillon's bent functions.pdf Путём детального анализа успешных способов взлома блочных и поточных шифров были определены свойства булевой функции, которыми она должна обладать для использования её в криптографических приложениях. На данный момент остаётся открытым вопрос о том, как совмещаются различные криптографические свойства у одной булевой функции. Данная работа посвящена изучению алгебраической иммунности при максимальной нелинейности булевой функции. Булева функция от n переменных представима единственным образом в виде алгебn раической нормальной формы (АНФ): f (x1,... ,xn) = (ф ф aib...,ifcxi1 ■... ■ xifc) ф ao, fc=1 i1,...,ik где ao,ai G Z2. Степенью deg(f) булевой функции f называется число переменных в самом длинном слагаемом её АНФ. Алгебраической иммунностью AI(f) булевой функции f называется минимальное целое число d ^ 1, такое, что существует булева функция g степени d, для которой выполняется равенство fg = 0 или (f ф 1)g = 0. Нелинейностью nl(f) булевой функции f от n переменных называется расстояние Хэм-минга от данной функции до множества аффинных функций от n переменных. Бент-функция — булева функция от n переменных (n чётно), обладающая максимальной нелинейностью равной 2n-1 - 2(n/2)-1. На сегодняшний день полная классификация бент-функций не произведена, но предложены способы построения таких функций. Функцию вида g : GF(2k) ^ GF(2) будем рассматривать как булеву, зафиксировав некоторый базис в поле GF(2k). В работе [1] Диллон приводит следующий способ построения бент-функций. Пусть g : GF(2k) ^ GF(2) —уравновешенная функция от k переменных и g(0) = 0. Тогда функция f (x,y) = g(x • y2 -2) является бент-функцией от 2k переменных. В данной работе исследуется алгебраическая иммунность некоторых бент-функций Диллона. В качестве уравновешенных рассматриваются линейные функции, как самые простые. Доказана Теорема 1. Пусть функция g : GF(2k) ^ GF(2) линейна, g = const и f построена с помощью конструкции Диллона по функции g, а именно f (x, y) = g(x • y2 -2). Тогда AI(f) ^ [k/2] +1. При k = 2,..., 8 оценка достигается. Из теоремы заключаем, что алгебраическая иммуность бент-функций Диллона, построенных с помощью линейных булевых функций, отличается от максимально возможной почти в 2 раза. В конструкции Диллона свойства бент-функции f зависят от выбора g. Возникает ряд вопросов — существуют ли такие g, чтобы AI(f) была максимальной, а если существуют, то какими свойствами обладают. В работе [2] предлагается способ построения таких g. Пусть g : GF(2k) ^ GF(2), supp(g) = {as,...,as+2 -1}, где a — примитивный элемент поля GF(2k) и s Е N. Тогда бент-функция f, построенная с помощью конструкции Диллона, обладает максимальной алгебраической иммунностью. Доказано Утверждение 1. Пусть g : GF(2k) ^ GF(2), supp(g) = {as,... , as+2k-1-1}, где a — примитивный элемент GF(2k) и s Е N. Тогда для k = 2, 3,... , 8 верно deg(g) = k - 1.

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

булева функция, нелинейность, бент-функция, алгебраическая иммунность, Boolean function, nonlinearity, bent function, algebraic immunity

Авторы

ФИООрганизацияДополнительноE-mail
Филюзин Станислав ЮрьевичНовосибирский государственный университетстудент механико-математического факультетаforgogu@inbox.ru
Всего: 1

Ссылки

Dillon J. F. Elementary Hadamard difference sets. Ph. D. Thesis. Univ. of Maryland, 1974.
Tu Z. and Deng Y. A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity // Designs, Codes and Cryptography. 2011. V.60. Iss. 1. P. 1-14.
 Верхняя оценка алгебраической иммунности некоторых бентфункций Диллона | ПДМ. 2013. № 6 (Приложение).

Верхняя оценка алгебраической иммунности некоторых бентфункций Диллона | ПДМ. 2013. № 6 (Приложение).

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