Конструкции векторных булевых функций с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/14

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

Исследуется компонентная алгебраическая иммунность векторных булевых функций. Рассмотрен метод построения векторных булевых функций F : Fn ^ F™ с максимальной компонентной алгебраической иммунностью из булевой функции f : Fn ^ F2 с максимальной алгебраической иммунностью в следующем виде: F(x) = (f(x),f(Ax),...,f(Am-ix)), где A - невырожденная булева матрица порядка п. Найдены функции с максимальной компонентной алгебраической иммунностью от 3 и 4 переменных. Доказано, что не существует функций F : F2 ^ F55 с максимальной компонентной алгебраической иммунностью, построенных по данному методу.

Constructions of vectorial boolean functions with maximum component algebraic immunity.pdf Многие шифры могут быть заданы в виде системы булевых уравнений. В 2003 г. предложен метод криптоанализа шифров, названный алгебраическим криптоанализом [1]. Основная его идея заключается в понижении степени системы уравнений и, следовательно, упрощении всей задачи. Данный вид криптоанализа является одним из наиболее перспективных и развивающихся в настоящее время. Соответственно возникает вопрос о возможности построения функций, способных ему противостоять. Алгебраической иммунностью AI(/) функции / называется минимальное число d, такое, что существует булева функция g степени d, не тождественно равная нулю, для которой /g = 0 или (/ ф 1)g = 0. Компонентной алгебраической иммунностью Alcomp (F) функции F называется минимальная алгебраическая иммунность компонентных функций F ■ b = bi/i ф ... ф bm/m, где b Е F^, b = 0. На олимпиаде NSUCRYPTO 2016 предлагалась открытая задача по построению векторных булевых функций с максимальной компонентной алгебраической иммунностью. Участником олимпиады Алексеем Удовенко предложено искать векторную булеву функцию F : Fn ^ F^ с максимальной компонентной алгебраической иммунностью в виде F(x) = (/(ж), /(Ax),..., /(Am-iж)), где / : Fn ^ F2 - некоторая булева функция с максимальной алгебраической иммунностью; A - невырожденная булева матрица n х n. Алексеем Удовенко найдены функции с максимальной компонентной алгебраической иммунностью, где в качестве линейного преобразования A выбрана функция циклического сдвига координат на одну позицию влево. Его идеи описаны в [2], где приводятся решения всех задач олимпиады. В качестве функции / : Fn ^ F2 выберем наиболее простую и известную функцию с максимальной алгебраической иммунностью - функцию Dalai [3]. Это функция вида '0, wt(x) < n/2, /(x) = n/2, *, wt(x) = n/2, где wt(x) -вес вектора x. Теорема 1. Существуют матрицы A, такие, что функция F : F^ ^ F^ вида F(x) = (f (x),f (Ax),..., f (An-1x)), где f - функция Dalai от n = 3, 4 переменных, имеет максимальную компонентную алгебраическую иммунность |~n/2]. Теорема 2. Не существует функций F : F2 ^ F^ вида F(x) = (f (x),f (Ax), f (A2x),f (A3x), f (A4x)), где f - функция Dalai от 5 переменных, с максимальной компонентной алгебраической иммунностью 3. Теорема 3. Пусть f - булева функция с максимальной алгебраической иммунностью от нечётного числа переменных n, A - невырожденная матрица n х n. Тогда функция g(x) = f (x) + f (Ax) обладает максимальной алгебраической иммунностью только в том случае, если под действием линейного преобразования A ровно половина элементов множества supp(f) остаётся в этом множестве, где supp(f) -носитель функции f. Теорема 4. Пусть функция F : Fn ^ Fn имеет вид F(x) = (f (x),f (Ax),..., f (An-1x)), где f - булева функция от n переменных с максимальной алгебраической иммунностью; n - нечётное число. Если функция F имеет максимальную компонентную алгебраическую иммунность, то матрицы A,... , An-1 должны удовлетворять условию теоремы 3. Продолжаются исследования существования векторных булевых функций с максимальной компонентной алгебраической иммунностью при n ^ 6.

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

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

Авторы

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

Ссылки

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. P. 41-58.
Tokareva N., Gorodilova A., Agievich S., et al. Mathematical methods in solutions of the problems from the Third International Students' Olympiad in Cryptography // Прикладная дискретная математика. 2018. №40. С. 34-58.
Courtois N. T. and Meier W. Algebraic attacks on stream ciphers with linear feedback // LNCS. 2003. V. 2656. P. 345-359.
 Конструкции векторных булевых функций с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/14

Конструкции векторных булевых функций с максимальной компонентной алгебраической иммунностью | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/14