Условия существования векторной булевой функции с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2016. № 9.

Условия существования векторной булевой функции с максимальной компонентной алгебраической иммунностью

Исследуется максимальная компонентная алгебраическая иммунность и её связь с матрицами специального вида. Получены ограничения на значения n, m, при которых возможно существование векторной булевой функции F : Zn ^ Zm с максимальной компонентной алгебраической иммунностью.

Necessary condition for maximum component algebraic immunity of a vectorial boolean function.pdf Важным криптографическим свойством булевых функций является алгебраическая иммунность, она была введена в работе [1]. Алгебраической иммуностью AI(f) булевой функции f : Zn ^ Z2 называется минимальное число d, такое, что существует булева функция g степени d, не тождественно равная нулю, для которой fg = 0 или (f е 1)g = 0. Данное понятие различными способами было обобщено на векторный случай. Одним из наиболее естественных обобщений является понятие компонентной алгебраической иммунности, введённое в [2]. Компонентной алгебраической иммунностью AIcomp (F) векторной булевой функции F : Zn ^ Zm называется минимальная алгебраическая иммунность компонентных функций b • F (b Е Zm, b = 0), т.е. AIcomp(F) = = min{AI(b • F) : b Е Zm b = 0}, где b • F = bf е ... е bmfm. Для булевых функций от n переменных известно [3], что алгебраическая иммунность всегда меньше или равна [n/2], более того, существуют функции, имеющие AI(/) = [n/2]. В случае компонентной алгебраической иммунности векторных булевых функций также получено [2], что AIcomp(F) ^ [n/2]. Данная работа посвящена изучению условий существования векторных булевых функций с максимальной компонентной алгебраической иммунностью равной [n/2] . Для каждой векторной булевой функции F : Zn ^ Z^ введём две матрицы Ыр, M'F, элементами которых являются булевы функции от n переменных. Построим эти матрицы следующим способом: в матрице Ыр j-му столбцу соответствует умножение компонентной функции b • F, b = 0, на все мономы степени меньше [n/2], за исключением тождественно равного нулю монома. Матрица Ы'р строится аналогично, только вместо b • F подставляется b • F ф 1. Сопоставим вектор a = (ai,... , an) Е Zn моному от n переменных, где a^ = 1 соответствует наличию в мономе переменной Xj. Нумерация столбцов идёт по вектору b Е Zm, b = 0; строки занумерованы векторами a = (ai,..., an): /i ф /2 < (/i ф /2 ( /i /2 /i • Xi /2 • Xi \ /m MF f /i • XiX2 . . ф /m)xi (/i ф /2 ф ... ф /m)XiX2 ... ( /i Ф 1 (/i ф 1)xi /2 ф 1 (/2 ф 1)xi /i ф . . (/i ф. (/i ф. M'F (/i ф 1)XiX2 / / m ф . ф /m ф 1)xi . ф /m ф 1)XiX2 \ 1 V Функции /i,..., /n являются линейно независимыми, если выражение ai/i ф a2/2 ф ф ... ф an/n, ai, a2,..., an Е Z2, тождественно равно нулю только при условии ai = = a2 = ... = an = 0. В работе [4] установлено, что векторная булева функция имеет максимальную компонентную алгебраическую иммунность AIcomp(F) = [n/2] тогда и только тогда, когда в матрицах Ыр и Ы^ элементы любого столбца образуют линейно независимое множество. В продолжение данной работы получено утверждение, поясняющее структуру матриц. Введём новую матрицу M, которая строится из матрицы Ыр приписыванием справа от неё матрицы Ы'р. Таким образом получаем матрицу, у которой элементы - булевы функции, количество строк такое же, как у матриц Ыр и Ы'р, а количество столбцов увеличивается в 2 раза. Утверждение 1. Если векторная булева функция F : Zn ^ Zm имеет максимальную компонентную алгебраическую иммунность AIcomp(F) = [n/2], то в любой строке матрицы Ы все элементы попарно различны. При изучении максимальной компонентной иммунности возникает вопрос о существовании ограничений на значения n, m, а также на их связь друг с другом. Получено следующее соотношение. Утверждение 2. Векторная булева функция F : Zn ^ Zm может иметь максимальную компонентную алгебраическую иммунность AIcomp(F) = [n/2] только для таких n, m, для которых выполняется следующее условие: / m ^ 2Г(п+1)/21 - 1.

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

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

Авторы

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

Ссылки

Meier W, Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions // Eurocrypt 2004. LNCS. 2004. V.3027. P. 474-491.
Carlet C. On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions // Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes, 2009. P. 104-116.
Courtois N. and Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt 2003. LNCS. 2003. V. 2656. P. 345-359.
Pokrasenko D. On the maximal component algebraic immunity of vectorial Boolean functions // J. Appl. Industr. Math. 2016. V. 10. P. 257-263.
 Условия существования векторной булевой функции с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2016. № 9.

Условия существования векторной булевой функции с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2016. № 9.