О компонентах некоторых классов обратимых векторных булевых функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/20

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

В классе обратимых векторных булевых функций от n переменных, координатные функции которых существенно зависят от всех переменных, рассматриваются подклассы Kn и КП, функции в которых получены с помощью n независимых транспозиций из тождественной подстановки и из подстановки, каждая координатная функция которой существенно зависит от одной переменной, соответственно. Приводятся некоторые свойства компонент функций из этих классов.

About the components of some classes of in-vertible vectorial boolean functions.pdf Для n Е N рассмотрим обратимые векторные булевы функции F = (f1... fn) на Fn, такие, что координатные функции f : Fn ^ F2, i = 1,... , n, существенно зависят от всех n переменных. В [1] предложен алгоритм 1 построения некоторой такой функции, который состоит в следующем: стартуя с тождественной подстановки G : Fn ^ Fn, на i-м шаге, i = 1,... , n, выбираем два соседних по i-й координате и не выбранных на предыдущих шагах вектора а,Ь Е Fn и меняем местами значения G^) и G(b). Обозначим класс функций, которые можно получить алгоритмом 1, через Kn. В [1] доказано, что Kn = 0 для всех n > 2; в [2] описаны некоторые свойства координат функций из Kn. В [1] предложена модификация алгоритма 1 построения функций из класса Kn, состоящая в том, что отправной точкой алгоритма является не обязательно тождественная подстановка G, а такая, что каждая координатная функция существенно зависит ровно от одной переменной, т. е. G = (g1... gn), = xj, где {j^... , jn} = {1,... , n}, a G {0,1} и x0 = xj, x1 = Xj, i = 1,... , n. Будем называть эту модификацию алгоритмом 1', а класс функций, которые можно таким образом получить, обозначим К. Утверждение 1. Пусть F = (f1... fn) G Kn. Тогда для всех i = 1,... , n функция fj имеет единственную линейную переменную Xj. Пусть v = (v1... vn) G (Fn)* = Fn \\ {00 ... 0}. Компонентой функции F = (f1... fn) n называется скалярное произведение vF : Fn ^ F2, vF(x) = ф vifi(x) = ф fj(x). i=1 vi=1 Через w(v) обозначим вес вектора v (количество единиц в нём). Утверждение 2. Пусть F = (f1... fn) G К и F получена алгоритмом 1' из начальной подстановки G = (xj1 ... xj™). Тогда fj имеет единственную линейную переменную x^, i = 1,... , n. Утверждение 3. Пусть F = (f1... fn) G К. Тогда для всех v = v1... vn G Fn, таких, что w(v) > 2, компонентная функция vF не имеет фиктивных и линейных переменных. Утверждение 4. |Kn | = 2n n! |Kn |. Приведём определения некоторых криптографических характеристик векторных булевых функций [3]. Нелинейность Nf функции F - минимальная нелинейность её компонент. Степень deg F функции F - максимальная степень её компонент (совпадает с максимальной степенью координатных функций). Компонентная алгебраическая иммунность AIcomp(F) функции F - минимальная алгебраическая иммунность её компонент. Утверждение 5. Для функции F G Kn выполняются следующие свойства: 1) Nf = 2; 2) deg F = n _ 1; 3) AIcomp(F) = 2; 4) если v G Fn и w(v) ^ 2n-3, то нелинейность компонентной функции vF равна NvF = 2w(v). Подробное изложение представленных результатов и доказательства утверждений можно найти в [4].

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

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

Авторы

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

Ссылки

Pankratova I. A. Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables // Материалы Междунар. науч. конгресса по информатике: Информационные системы и технологии. Республика Беларусь, Минск, 24-27 окт. 2016. Минск: БГУ, 2016. С. 519-521.
Карпова Л. А., Панкратова И. А. Свойства координатных функций одного класса подстановок на Fn // Прикладная дискретная математика. Приложение. 2017. №10. С. 38-40.
Carlet C. Vectorial Boolean Functions for Cryptography. Cambridge: Cambridge University Press, 2010. 93 p.
Панкратова И. А. Свойства компонент некоторых классов векторных булевых функций // Прикладная дискретная математика. 2019. №44. С. 5-11.
 О компонентах некоторых классов обратимых векторных булевых функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/20

О компонентах некоторых классов обратимых векторных булевых функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/20