О верхней оценке нелинейности некоторого класса булевых функций с максимальной алгебраической иммунностью | ПДМ. 2013. № 1(19).

О верхней оценке нелинейности некоторого класса булевых функций с максимальной алгебраической иммунностью

Доказывается верхняя оценка нелинейности булевых функций от чётного числа переменных, обладающих максимально возможной алгебраической иммунностью и предложенных D. K. Dalai и др. в 2006 г.

An upper bound for the nonlinearity of some Boolean functions with maximal possible algebraic immunity.pdf Введение В работе [1] N. Courtois и W. Meier предложили метод криптоанализа шифров, основанных на фильтрующих генераторах. Этот криптоанализ использует следующие слабости фильтрующей функции: наличие у неё аннигиляторов низкой степени и множителей, существенно уменьшающих степень получающейся в результате произведения функции. В работе [2] сформулировано понятие алгебраической иммунности булевой функции, которое объединило эти слабости в одно свойство. Таким образом, булевы функции с низкой алгебраической иммунностью обладают слабостью к алгебраической атаке на поточные шифры. В данной работе рассматривается верхняя оценка нелинейности булевых функций от чётного числа переменных, предложенных в [3]. Основная часть Через Zn обозначим n-мерный булев куб. Под расстоянием между двумя булевыми функциями будем понимать расстояние Хэмминга (число векторов, на которых функции различаются). Вес Хэмминга вектора x (wt(x)) —количество его ненулевых координат. Будем называть i-м слоем n-мерного булева куба все векторы веса i. Степень алгебраической нормальной формы булевой функции называется алгебраической степенью функции (обозначается deg(f)). Булева функция называется аффинной, если ее алгебраическая степень не превосходит 1. Алгебраической иммунностью булевой функции f (AI(f)) называют минимальную положительную алгебраическую степень булевой функции, которая аннулирует f или f 0 1, т.е. AI(f) = min{deg(g): f (x)g(x) = 0 или (f (x) 0 1)g(x) = 0}. g=0 Известно, что для функции f от n переменных AI(f) ^ |~n/2~|. Для криптографических приложений наибольший интерес представляют функции с максимально возможной алгебраической иммунностью, т.е. с AI(f) = |~n/2] (это значение достигается для любого n). Исследование выполнено при поддержке РФФИ, проект №12-01-31097. Рассмотрим нелинейность функций, обладающих максимальной возможной алгебраической иммунностью, а именно функций, построенных с помощью одной из самых простых конструкций для чётного числа переменных, которая предложена в работе [3]: 0, wt(x) < n/2, f (ж) = { b(x) е {0,1}, wt(x) = n/2, (1) 1, wt(x) > n/2. Все такие функции обладают алгебраической иммунностью n/2. Напомним, что нелинейностью булевой функции f (обозначается nl(f)) называется расстояние Хэмминга от функции f до класса аффинных функций. Известна следующая оценка снизу на нелинейность функции от n переменных [4]: AI(f)-2 nl(f) ^ 2 £ СП-1. i=0 Для булевых функций с максимально возможной алгебраической иммунностью от чётного числа переменных n эта оценка выглядит следующим образом: nl(f) ^ 2n-1 - 2СП-21. (2) Среди функций вида (1) существуют такие, для которых в (2) достигается равенство. Эта оценка доказана также в [3] для функций вида (1), уравновешенных на среднем слое. Докажем верхнюю оценку нелинейности для данного класса функций. Следует упомянуть, что данная оценка приводится (как тезис) в презентации Ch. Li [5]. Теорема 1. Для функций f вида (1) выполняется nl(f) ^ 2n-1 - СП-. Доказательство. Оценим расстояния d от функций вида (1) до линейных функций /j(ж) = Xi, i е {1,...,n}, n — количество переменных. Пусть f — функция вида (1) от n переменных. Рассмотрим расстояния на каждом слое булева куба Zn отдельно. Пусть dj —расстояние до ^ на j-м слое, т .е. dj = |{ж е zn : wt(x) = j, f (ж) = /i(x)}| , j е {0,... , n}. Тогда dj = d0 + d1 + ... + dn. Очевидно, что 0, j = 0, Cn-i, 0 < j < n/2, dj 4 dn/2, j = n/2, (3) Cn-1, n/2 < j < n, 0, j = n. Поэтому n/2-1 j-1 n-1 j /2 n/2-2 j n-1 j /2 di = S Cn-1 + S Cn-1 + "i = S Cn -1 + Cn-1 + "i j=1 j=n/2+1 j=0 n/2+1 n1 — V^ nj — Г

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

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

Авторы

ФИООрганизацияДополнительноE-mail
Коломеец Николай АлександровичИнститут математики Сибирского отделения Российской академии наук (г. Новосибирск)аспирантnkolomeec@gmail.com
Всего: 1

Ссылки

Courtois N. and Meier W. Algebraic attacks on stream ciphers with liner feedback // LNCS. 2003. V. 2656. P. 345-359.
Meier W, Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions // LNCS. 2004. V. 3027. P. 474-491.
Dalai D.K., Maitra S., and Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity // Designs, Codes and Cryptography. 2006. V. 40. Iss. 1. P. 41-58.
Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Вып. 18. №3. С. 152-159.
Li Ch. A survey on construction of Boolean function with optimum algebraic immunity (AI) // http://www.frisc.no/wp-content/uploads/2011/10/Li-A-survey-on-construc-tions-of-BFs-with-optimum-AI.pdf
 О верхней оценке нелинейности некоторого класса булевых функций с максимальной алгебраической иммунностью | ПДМ. 2013. № 1(19).

О верхней оценке нелинейности некоторого класса булевых функций с максимальной алгебраической иммунностью | ПДМ. 2013. № 1(19).

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