On properties of the set of values of an arbitrary vector boolean function.pdf В работе рассматриваются векторные булевы функции F : Fn ^ Fn, которые также известны как S-блоки. Они играют центральную роль для криптографической стойкости блочных шифров. В 1994 г. K. Nyberg [1] ввела понятие дифференциально ^-равномерных векторных булевых функций. Векторная булева функция F : Fn ^ Fn называется дифференциально 6-равномерной, если для любого ненулевого вектора a Е Fn и любого вектора b Е Fn уравнение F(x) ф F(x ф a) = b имеет не более 6 решений, где 6 - целое положительное число. Порядком дифференциальной равномерности функции F назовём минимальное возможное 6, такое, что F - дифференциально 6-равномерная функция. Чем меньше порядок дифференциальной равномерности S-блока, который используется в шифре, тем выше стойкость шифра к дифференциальному криптоанализу [2]. Минимальное возможное значение, которое может принимать 6, - это 2. Если 6 = 2, то дифференциально 6-равномерная функция называется APN-функцией (Almost Perfect Nonlinear). Для векторной булевой функции F и любого ненулевого вектора a Е Fn определим множество Ba(F) = {F(x) ф F(x ф a) : x Е Fn}. Максимальная достижимая мощность множества Ba(F) равна 2n-1. В частности, если при любом ненулевом векторе a выполнено |Ba(F)| = 2n-1, то функция F является APN [3]. В работе [4] исследовалось расстояние между различными APN-функциями, в связи с этим была выдвинута следующая гипотеза. Гипотеза 1. Если F - APN-функция от n переменных, то выполнено Vx' Е Fn ( U (Ba(F) ф F(x' Ф a)) = Fn yaGF^ ,a=0 Для доказательства этой гипотезы требуется рассматривать объединение множеств Ba (F). В данной работе исследуются некоторые свойства множества значений произвольной векторной булевой функции из Fn в Fn, а именно множество значений её производных. Полученные результаты помогут в изучении метрических свойств класса APN-функций. Суммой двух множеств A, B С Fn назовём множество всех попарных сумм элементов этих множеств: A ф B = {a ф b : a Е A,b Е B}. Сумма вектора x Е Fn и множества A С Fn - сдвиг множества A: x ф A = {x ф a : a Е A}. Множество всех значений векторной булевой функции F : Fn ^ Fn называется образом функции F и обозначается im(F). Лемма 1. Пусть A, B С F^ |A| ^ 2n-1 и |B| ^ 2n-1 + 1. Тогда A ф B = Fn Теорема 1. Пусть F : Fn ^ Fn - векторная булева функция. Тогда: 1) если 2n-1 < |im(F)| < 2n, то U Ba(F) = Fn; a€F™a=0 2) если |im(F)| = 2n, т.е. F является перестановкой, то и Ba(F) = Fn\{0}. Условие на мощность образа функции не может быть ослаблено. Существуют функции F, у которых мощность образа равна |im(F)| = 2n-i и выполнено (J B„(F) = aGF^a^O = Fn. Например, такова APN-функция F : F;] ^ F2, заданная вектором значений (0, 0,1, 2,1, 4, 2, 4). Для неё |im(F)| = 22, а (J B„(F) = Fn\{7}. aGF^a^O Теорема показывает, как ведёт себя объединение множеств B„(F), при каких условиях на образ функции F объединение даёт всё пространство Fn, а при каких нет.

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