On intersection of derivatives images for apn functions.pdf В работе рассматривается специальный класс векторных булевых функций - почти совершенные нелинейные функции (APN-функции). Векторная булева функция F : Fn ^ Fn называется APN-функцией, если для любых векторов а, b е Fn, где а - ненулевой вектор, уравнение F(x) ф F(xфа) = b имеет не более двух решений. Данные функции представляют интерес для использования в качестве узлов замены в блочных шифрах в силу их оптимальной стойкости к разностному криптоанализу. Однако класс APN-функций достаточно слабо изучен (см., например, обзор [2]), остаётся большое число открытых вопросов [3]. Настоящая работа посвящена исследованию пересечений множеств значений производных APN-функций. Производной функции F : Fn ^ Fn по направлению а е Fn называется функция DaF(x) = F(x) ф F(x ф а). По определению F - APN-функция, если её производные по каждому направлению принимают в точности 2n-1 различных значений, т.е. |Ba(F)| = |{DaF(x) : x е Fn}| = 2n-1. Для автора представляется интересным найти ответы на следующие вопросы. Открытый вопрос 1. Каково минимальное пересечение множеств значений производных двух APN-функций? Открытый вопрос 2. Как связаны APN-функции F и G от n переменных, если их производные по каждому направлению имеют одинаковые множества значений соответственно, т. е. для любого а = 0 верно Ba(F) = Ba(G)? Первый вопрос связан, в частности, с поиском итеративной конструкции. Из теоремы 1 [1] следует, что если взять две APN-функции F, G от n переменных и две булевы функции f, g от n переменных, для которых выполнено условие допустимости (для всех x, y, а е Fn, а = 0, хотя бы одно из равенств DaF(x) = DaG(y) и Daf (x) = Dag(y) нарушается), то по ним можно определить APN-функцию от n +1 переменной. Фактически, вся сложность описанного подхода к итеративному построению APN-функций заключается в поиске исходных допустимых векторных функций F и G (т. е. тех, для которых существуют булевы функции f, g, такие, что для F, G, f, g выполнено условие допустимости). Получен следующий эквивалентный критерий проверки допустимости пары APN-функций F и G, который не включает в рассмотрение соответствующие булевы функци f и g. Утверждение 1. Пара APN-функций F и G от n переменных допустима тогда и только тогда, когда для любого нечётного k, k ^ 3, не существует набора векторов x*, y*, а*, i = 1,..., k, где а4 = 0, таких, что F(x*) ф F(x* ф а4) = G(y*) ф G(y* ф а4), i = 1... , k, и каждый из векторов x и y среди x*, x* ф а* и y*, у* ф а* соответственно (i = 1,..., k) встречается чётное число раз. Как можно видеть из утверждения 1, необходимо отслеживать, какие пересечения имеют множества значений производных функций F и G по всем направлениям. Логично предположить, что чем меньше мощности пересечений значений производных функций F и G, тем больше вероятность, что будут выполнены условия утверждения 1. Утверждение 2. Для любых двух APN-функций F и G от n переменных, n ^ 3, существует ненулевой вектор а е Fn, такой, что множества значений производных DaF и DaG пересекаются. Далее рассмотрим отдельно случай двух квадратичных APN-функций, которые в сумме дают линейную функцию. Пусть F - квадратичная APN-функция, а L - линейная от n переменных (для любых x,y е Fn выполнено L(x ф у) = L(x) ф L(y)). Тогда производные F по всем направлениям аффинны и, следовательно, множества Ba(F) = {F(x) ф F(x ф а) : x е Fn} являются аффинными подпространствами Fn размерности n - 1. Далее, поскольку Ba(F ф L) = Ba(F) ф L^), то Ba(F) и Ba(F ф L) либо совпадают, либо не пересекаются. Из этого следует также, что F ф L является APN-функцией. Утверждение 3. Пусть F - квадратичная APN-функция, а L - произвольная линейная функция от n переменных. Пусть существуют в точности k различных ненулевых а* е Fn, при которых Bai(F) = Bai(FфL). Тогда если k > 2n-1, то пара F, FфL не является допустимой. Гипотеза 1. Для любой квадратичной APN-функции F от n переменных существует линейная функция L от n переменных, такая, что пара F и F ф L является допустимой. Гипотеза 1 выполняется для n = 3; найдены также примеры, подтверждающие её при n = 4, 5 (эти размерности вычислительно не позволяют провести полный перебор). Второй вопрос связан с описанием классов APN-функций, у которых множества значений производных попарно совпадают по каждому направлению. Ранее автором неверно предполагалось, что для каждой APN-функции F такой класс состоит только из функций F(x ф с) ф d, где с, d пробегают Fn. Однако найдены примеры квадратичных функций F от 4 переменных, для которых существуют линейные функции L, прибавление которых к исходной функции F сохраняет множества значений производных по всем направлениям, но при этом F ф L не лежит в классе {F(x ф с) ф d : с, d е Fn}. Например, в качестве F можно выбрать APN-функцию F(xi,x2,x3,x4) = (xix2, xix3 ф x2x4, x2x3 ф xix4 ф x2x4, x3x4), а в качестве линейной следующую: L(xi,x2,x3,x4) = (xi ф x2, x2 ф x3, x2, x3 ф x4). Тогда для любого ненулевого а е F4 верно Ba(F) = Ba(F ф L).

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