Об алгебраической иммунности векторных булевых функций | ПДМ. Приложение. 2015. № 8.

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

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

On algebraic immunity of vector boolean functions.pdf В 2003 г. N. Courtois и W. Meier предложили алгебраический метод криптоанализа шифров [1]. В случае поточных шифров этот метод использует следующие слабости фильтрующей функции: наличие у неё аннигиляторов низкой степени и множителей, уменьшающих степень функции. В настоящее время данный вид криптоанализа является одним из наиболее перспективных и развивающихся; соответственно возникает вопрос о поиске функций, способных ему противостоять. В 2004 г. W. Meier, E. Pasalic и C. Carlet в работе [2] ввели понятие алгебраической иммунности для булевых функций. Алгебраической иммунностью AI(f) булевой функции f : Fn - F2 называется такое минимальное число d, что существует булева функций g степени d, не тождественно равная нулю, для которой fg = 0 или (f ф 1)g = 0. Для любой булевой функции выполняется AI(f) ^ [n/2] и существуют функции, имеющие AI(f) = |~n/2]. Высокая алгебраическая иммунность позволяет противостоять алгебраическим атакам. Понятие алгебраической иммунности различными способами было обобщено на векторный случай. Так, в работе [3] F. Armknecht и M. Krause, а также G. Ars и J.-C. Faugere в [4] рассмотрели алгебраическую иммунность S-блоков и ввели понятия базовой AI(F) и графической AIgr(F) алгебраической иммунности векторных булевых функций. При этом базовая алгебраическая иммунность больше 1 только при малых значениях m, поэтому данный параметр анализируется у S-блоков, которые используются в поточных шифрах. Графическая алгебраическая иммунность используется для изучения сопротивляемости алгебраическим атакам блочных шифров. Следующее обобщение является одним из наиболее естественных с криптографической точки зрения. Компонентной алгебраической иммунностью AIcomp(F) векторной булевой функции F : Fn - Fm называется минимальная алгебраическая иммунность компонентных функций b ■ F (b е Fm,b = 0), т.е. AIcomp(F) = min{AI(b ■ F) : b е Fm, b = 0}, где b ■ F = b1f1 ф ... ф bmfm. Данное определение является наиболее универсальным, наличие высокой компонентной алгебраической иммунности S-блоков способствует противостоянию алгебраическому криптоанализу поточных и блочных шифров. В [5] получена оценка AIcomp ^ min{|~n/2|, dminF}, где dminF - минимальная степень компонентных функций b • F. При этом остаётся не изученным вопрос о существовании функций, имеющих AIcomp = |~n/2|. В работе получены следующие результаты. Теорема 1. Для любого нечётного n векторная булева функция F : F^ ^ Fm, имеющая AIcomp = |~n/2|, является сбалансированной. В случае n = m функция F взаимно однозначна. Занумеруем через a = (ai,..., an) Е Fn мономы от n переменных, где a^ соответствует появлению в мономе переменной x, а a = (0,..., 0) соответствует 1. Например, вектор a = (1, 0,1,0,... , 0) соответствует моному Для каждой векторной булевой функции F : Fn ^ Fm введём две матрицы Mf , MF, элементами которых являются булевы функции от n переменных. Построим эти матрицы следующим способом: в матрице Mf j-му столбцу соответствует умножение компонентной функции b • F, b = 0, на мономы степени меньше |~n/2|. Нумерация столбцов идёт по вектору b Е Fm, b = 0. Соответственно число столбцов 2m - 1. Строки занумерованы с помощью вектора a = (a1,... , an). Матрица Mp строится аналогично, только вместо b • F подставляется b • F 0 1: f i 0 f2 « (fi ® f2 f fi fixi \ f2 f2x1 fm MF F fiXiX2 . . 0 fm)xi (fi 0 f2 0 ... 0 fm)XiX2 V / fi 0 1 f2 0 1 (fi 0 1)Xi (f2 0 1)Xi fi 0 . . (fi 0 . (fi 0 . Mp (fi 0 1)XiX2 f m0 . 0 fm 0 1)xi . 0 fm 0 1)XiX2 \ 1 V Функции fi,..., fn являются линейно независимыми, если выражение aifi 0 a2f2 0 0 ... 0 anfn, где ai,a2,... ,an Е F2, тождественно равно нулю только при условии ai = a2 = ... = an = 0. Теорема 2. Векторная булева функция F : Fn ^ Fm имеет максимальную компонентную алгебраическую иммунность AIcomp(F) = |~n/2| тогда и только тогда, когда в матрицах Mf и Mp элементы любого столбца образуют линейно независимое множество. Для малого числа переменных найдены векторные булевы функции, которые имеют AIcomp = |~n/2|, подсчитано число таких функций. В таблице приведено количество векторных булевых функций с максимальной компонентной алгебраической иммунностью, общее количество векторных булевых функций, действующих из Fn в Fm, и доля функций с AIcomp = |~n/2| от общего числа векторных булевых функций. / (n, m) Функции с AIcomp(F) = [n/2] Все функции из F^ в F™ Доля функций (2,2) 168 256 0,65625 (3,2) 1344 65536 0,02051 (3,3) 10752 16777216 0,00064 (4,2) « 108 4294967296 « 0,02

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

balancedness, vector Boolean function, component algebraic immunity, компонентная алгебраическая иммунность, векторная булева функция

Авторы

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

Ссылки

Carlet C. On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions // Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes. Amsterdam: IOS Press, 2009. P. 104-116.
Armknecht F. and Krause M. Constructing single- and multi-output Boolean functions with maximal immunity // ICALP'2006. LNCS. 2006. V.4052. P. 180-191.
Ars G. and Faugere J.-C. Algebraic immunities of functions over finite fields // Proc. Conf. BFCA. 2005. P. 21-38.
Courtois N. and Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt'2003. LNCS. 2003. V.2656. P. 345-359.
Meier W, Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions // Eurocrypt'2004. LNCS. 2004. V. 3027. P. 474-491.
 Об алгебраической иммунности векторных булевых функций | ПДМ. Приложение. 2015. № 8.

Об алгебраической иммунности векторных булевых функций | ПДМ. Приложение. 2015. № 8.