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].

Скачать электронную версию публикации