On nonlinearity of some boolean functions with maximal algebraic immunity.pdf После публикации работ [1,2] большое внимание уделяется алгебраической иммун-ности булевых функций. Алгебраическая иммунность булевой функции f (обознача-ется через A I ( f ) ) -это минимальная положительная алгебраическая степень булевойфункции, аннулирующей f или f ф 1, т. е.AI(f) = min{deg(g) : Vxf (x)g(x) = 0 или Vx (f (x) ф 1)g(x) = 0}.g=0Известно, что для функции f от n переменных A / ( f ) ^ [n/2]. Для криптографическихприложений наибольший интерес представляют функции с максимально возможнойалгебраической иммунностью, т.е. с AI(f) = |~n/2] (такое значение алгебраическойиммунности достижимо для любого n).В данной работе исследуется нелинейность функций, обладающих максимальновозможной алгебраической иммунностью, а именно: рассматриваются функции, по-строенные с помощью одной из самых простых конструкций для чётного числа пере-менных, которая предложена D. K. Dalai и др. в работе [3]:0, wt(x) < n/2,f ( x ) = { b G {0,1}, wt(x) = n/2, (1)1, wt(x) > n/2,где n - количество переменных (n чётно); wt(x) -вес Хэмминга вектора x. Все такиефункции обладают алгебраической иммунностью n/2.Нелинейностью булевой функции f (обозначается через nl(f)) называется рас-стояние Хэмминга от функции f до класса аффинных функций (функций видаa1x1 ф . . . ф anxn ф а0). Это также одно из важнейших криптографических свойствбулевых функций.Получена следующая верхняя оценка нелинейности функций вида (1).Теорема 1. Для функций f вида (1) выполняетсяnl(f) ^ 2n - 1 - / n - Гn/2В той же работе [3] рассматривается нелинейность функций, полученных с помо-щью данной конструкции, а именно доказаноУтверждение 1 (Dalai и др. [3]). Для функции0, wt(x) ^ n/2,f ( x ) ^ 1, wt (x) > n/2от n переменных (n чётно) верноnKZ) = 2 " - 1 - ( "n-1Таким образом, оценка из теоремы 1 достижима.Поскольку максимальная нелинейность для функций от чётного числа переменныхравна 2 n - 1 - 2 n / 2 - 1 , нелинейность функций вида (1) заметно отличается от максималь-но возможной.

Скачать электронную версию публикации