Vectorial 2-to-1 functions as subfunctions of apn permutations.pdf Векторной булевой функцией F называется произвольное отображение F : Fn ^ Fm. Рассмотрим векторную булеву функцию F из F^ в F^. Для векторов a, b G Fn, где a = 0, определим величину £(a,b) = |{x G Fn : F(x + a) + F(x) = b}|. Обозначим за Ар следующий параметр: Af = max ^(a,b). Тогда F называется дифференциально AF-равномерной функцией. Чем меньше параметр А^, тем более устойчив к дифференциальному криптоанализу блочный шифр, содержащий функцию F в качестве S-блока. Для векторных функций из Fn в Fn минимально возможное значение Af равно 2. В этом случае функция F называется почти совершенно нелинейной функцией, или APN-функцией. Данные понятия введены К. Ньюберг в [1], однако известно [2], что APN-функции также изучались В. А. Башевым и Б. А. Егоровым в СССР в 60-х годах. Подробнее об APN-функциях можно прочесть в [3-5]. Одна из самых интересных проблем в данной области связана со взаимно однозначными APN-функциями [6]. Долгое время имела место гипотеза, что не существует взаимно однозначных APN-функций от чётного числа переменных. Однако в 2009 г. авторы работы [7] нашли первый и единственный (с точностью до эквивалентности) на данный момент пример взаимно однозначной APN-функции над F^. Для больших размерностей вопрос существования по-прежнему открыт. Векторная функция F : Fn ^ Fn называется 2-в-1 функцией, если её множество значений состоит из 2n-i элементов и каждое значение она принимает ровно на двух аргументах. Рассмотрим произвольную векторную функцию F = (/i,... , /n) из Fn в Fn. Будем называть векторную булеву функцию Fj из Fn в Fn-i (n - 1)-подфункцией функции F, если Fj = (/i,... , /j-i, /j+i,... , /n) для некоторого j Е {1,... , n}. Напомним, что множеству Fn можно сопоставить во взаимно однозначное соответствие целочисленное множество {0,..., 2n - 1}, где каждое число является десятичным представлением вектора из Fn . Тогда произвольную (n - 1)-подфункцию Fj из Fn в Fn-i можно рассматривать как векторную функцию из Fn в Fn, принимающую значения из множества {0,..., 2n-i - 1}. Рассмотрим произвольную 2-в-1 функцию, принимающую значения из {0,... , 2n-i - 1}, тогда вектор её значений может быть представлен в виде некоторой перестановки упорядоченного вектора (0,0,1,1,... , 2n-i - 1, 2n-i - 1). Будем обозначать множество таких 2-в-1 функций от n переменных через 7П. Можно заметить, что тогда любая (n - 1)-подфункция взаимно однозначной векторной функции принадлежит 7n. Имеет место следующее утверждение [8]. Лемма 1. Пусть F - взаимно однозначная APN-функция от n переменных. Тогда любая её (n - 1)-подфункция является дифференциально 4-равномерной функцией из 7^. В [8, 9] рассматривается алгоритм построения 2-в-1 APN-функций при помощи специальных так называемых допустимых символьных последовательностей. В [8] доказана следующая Теорема 1. Пусть F - взаимно однозначная APN-функция от n переменных. Тогда символьная последовательность, соответствующая вектору значений произвольной (n - 1)-подфункции F, является допустимой. Таким образом, любая взаимно однозначная APN-функция может быть получена из некоторой 2-в-1 дифференциально 4-равномерной функции, построенной при помощи допустимой последовательности. Данное наблюдение позволяет предложить следующий алгоритм для поиска новых взаимно однозначных APN-функций. С помощью аппарата допустимых последовательностей строим 2-в-1 векторную функцию S, принадлежащую 7^ (подробнее о данном построении см. в [8]) и проверяем её на дифференциальную равномерность. Если S дифференциально 4-равно-мерная, то она может являться (n - 1)-подфункцией некоторой взаимно однозначной APN-функции. Необходимо проверить, существует ли сбалансированная булева функция f, такая, что взаимно однозначная функция H = S U f является APN-функцией. Заметим, что требуется проверить 22п булевых функций, поскольку на каждую пару одинаковых значений 2-в-1 функции S приходится пара {0,1} из значений булевой функции f. Обозначим через nf (S) число булевых функций f, таких, что H = S U f является взаимно однозначной APN-функцией. Получена следующая нижняя оценка для данной величины: Теорема 2. Пусть S - векторная функция из 7П, построенная с помощью допустимой последовательности. Тогда если nf (S) = 0, то nf (S) ^ 2n. С помощью компьютерных вычислений проверено, что данная оценка является точной при n = 3, 5, а также при n = 6 для всех (n - 1)-подфункций APN-функции Диллона.

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