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

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

Рассматривается класс F n, m,k обратимых векторных булевых функций из Fn в F^, координатные функции которых существенно зависят от заданного числа k переменных. Доказано: 1) таких функций не существует при любом n = m и k = 2; 2) функции класса F n, n, n-1 могут (не могут) быть построены из аффинных координатных функций при чётном (нечётном) n; 3) если F n, m,k = 0, то и n+1 = 0.

On the invertibility of vector boolean functions.pdf Задача построения обратимых векторных булевых функций возникает при создании многих криптосистем; в частности, такие функции используются в многораундо-вых симметричных блочных шифрах класса SIBCipher [1]. Для того чтобы значения функции можно было эффективно вычислять, часто вводится ограничение на количество существенных переменных у каждой координатной функции векторной функции. Для n,m, k е Z обозначим через Fn,m,k класс функций F : Fn - Fm, где F = = (f1... fm), таких, что координатные функции f : Fn - F2, i = 1,... , m, существенно зависят ровно от k переменных и функция F - инъекция (т. е. обратима). В случае n = m (практически важном для построения многораундовых шифров) будем обозначать Fn,k = Fn,n,k. Непосредственно проверяются следующие свойства: 1) если Fn,m,k = 0, то m ^ n; 2) если F е Fn,k, то F есть подстановка на Fn и все её координатные функции уравновешены; 3) если F = (f ... fm) е Fn,m,fc, то и F' = (f ... /j... fm) е Fn,m,k, i е {1,..., m}; 4) если Fn,m,k = 0, то Fn,t,k = 0 для любого t > m; 5) если = 0, то = 0 для любого s > 1. Последнее свойство используется при построении шифров SIBCiphers семейства Люцифер [1]: ks переменных разбиваются на блоки по k переменных в каждом и «большая» раундовая функция набирается из s «маленьких» функций - подстановок на F£. Пример 1. Функция F : F3 - F2 с вектором значений (0 6 7 2 4 3 1 5) принадлежит множеству F3,3; её координатные функции f1 = x1 ф x2 ф x3, f2 = x1x2 ф ф x2x3 ф x2 ф x3, /з = x1x3 ф x2x3 ф x2. Утверждение 1. Fn,2 = 0 для любого n ^ 2. Доказательство. Предположим, F е Fn,2. Тогда по свойству 2 все её координатные функции уравновешены, т. е. имеют вид xi фxj фc для некоторых 1 ^ i < j ^ n, c е F2. Но в этом случае F(x) = F(x) для любого x е Fn, что невозможно для инъек-тивной функции. ■ Заметим, что при m > n уравновешенность координатных функций уже не обязательна и класс Fn,m,2 может быть не пуст. Пример 2. Функция F : F2 ^ F2 с вектором значений (0 5 4 2) принадлежит классу F2,3,2; её координатные функции /l = xl ф x2, /2 = xlx2, /3 = xlx2 ф x2. Утверждение 2. 1) Если n чётное, то некоторая F е Fn,n-i может быть построена из аффинных координатных функций. 2) Если n нечётное, то никакая F е Fn,n-i не может быть построена из аффинных координатных функций. 0xj ф Ci, Ci е F2, j=i i = 1,... , n; a = ... an) е Fn - произвольное значение. Ввиду свойства 3 без ограничения общности можно полагать, что все ci равны нулю. Составим уравнение F(x) = a, или в матричном виде Ax = a, где x и a - вектор-столбцы, A - (n х ^-матрица: A Доказательство. Пусть F(xl, ..., xn) = (/l ... /n), /i 1 0 1. .1 1 1 1 0. .1 1 1 1 1. .0 1 1 1 1. .1 0 Легко убедиться, что det A = (n - 1) mod 2 над полем F2, поэтому уравнение F(x) = a имеет решения для всех a (что равносильно условию F е Fn,n-i), если и только если n чётно. Для завершения доказательства п. 2 утверждения осталось заметить, что перестановка координатных функций не влияет на принадлежность функции F классу Fn,n- l ; других способов выбора n различных аффинных функций, существенно зависящих от (n - 1) переменных каждая и от всех n переменных в совокупности (что, очевидно, необходимо для принадлежности функции F классу Fn,n-1), нет. в Следствие 1. Fn,n-i = 0 для любого чётного n. Утверждение 3. Если Fn,m,fc = 0, то Fn+i,m+i,k = 0. Доказательство. Пусть F(xl, ..., xn) = (/l ... /m) е Fn,m,k. Построим функцию G : Fn+i ^ Fm+i так: G(xi,... ,xn,xn+i) = (/i... /m g), где g(xi,... ,xn,xn+i) = xn+i ф ф h(xi,... ,xn), h - любая функция, существенно зависящая от (k - 1) переменных. Тогда G(ai,..., an, 0) = G(ai,..., an, 1) для любого ai... an е Fn ввиду линейности функции g по переменной xn+i; G(ai,... , an, c) = G(6l, ... , bn, c) для любых ai... an = = ... bn, c е F2 ввиду обратимости функции F. ■ ,3 = 0 для всех Из утверждения 3, свойства 4 и примеров 1 и 2 следует, что Fn m ^ n ^ 3 и Fn,m,2 = 0 для всех m > n ^ 2.

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

invertible function, vector Boolean functions, обратимые функции, векторная булева функция

Авторы

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

Ссылки

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

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