Functions on distance one from apn functions in small number of variables.pdf Исследуется вопрос существования APN-функций на расстоянии один друг от друга. Доказано, что гипотеза о том, что таких APN-функций нет, выполнена для большинства известных APN-функций от не более чем восьми переменных. Ключевые слова: векторная булева функция, дифференциально 8-равномерная функция, APN-функция. В работе рассматриваются векторные булевы функции F : Fn ^ Fn. Каждая такая векторная булева функция единственным образом представляется в виде АНФ: (1) все функции на расстоянии один являются дифференциально равномерными порядка 4; таким образом, на расстоянии один от них нет APN-функций. В работе [3] выдвигается также гипотеза о том, что все APN-функции удовлетворяют этому условию. Данный вопрос тесно связан с вопросом существования APN-функций максимальной алгебраической степени, а именно, если найдутся две APN-функции на расстоянии один, то одна из них обладает максимальной алгебраической степенью. В [4] доказано, что для большинства известных APN-функций F : Fn ^ Fn функция x2"-1 + F (x) алгебраической степени n не является APN-функцией. F(x)= Е (П xi)= Е а/x/, /eP(N) ге/ /ер(n) где P(N) - множество всех подмножеств множества N = {1,..., n}; а/ из Fn. Алгебраической степенью функции F называется величина равная max{|11 : а/ = (0,... , 0), I е е P(N)}. Функции с алгебраической степенью, не превосходящей 1, называются аффинными. Функция называется дифференциально 5-равномерной [1], если для любого ненулевого вектора а е Fn и любого вектора b е Fn уравнение F(x) ф F(x ф а) = b имеет 8 решений, где 8 - целое положительное число. Порядком дифференциальной равномерности функции F называется минимальное возможное 8, такое, что F - дифференциально 8-равномерная функция. Расстоянием между векторными булевыми функциями F и G называется мощность множества {x е Zn : F(x) = G(x)}. Векторные булевы функции также известны как S-блоки - примитивные элементы шифров. Чем меньше порядок дифференциальной равномерности S-блока, тем выше стойкость шифра, в котором он используется, к дифференциальному криптоанализу [2]. Минимальный возможный порядок равен двум. Функция с порядком дифференциальной равномерности 2 называется APN-функцией (Almost Perfect Nonlinear). В работе [3] поднимается вопрос существования APN-функции на расстоянии один от произвольной APN-функции и доказано, что для тех APN-функций F : Fn ^ Fn, для которых выполнено В данной работе исследуется вопрос: удовлетворяют ли APN-функции от малого числа переменных условию (1). Функции F и G из Fn в Fn называются EA-эквива-лентными, если G представима в виде G = Ai о Fо A2 ф A, где A, Ai и A2 - аффинные отображения из Fn в F^"; Ai и A2 являются перестановками. Утверждение 1. Если векторные булевы функции F и G EA-эквивалентны и условие (1) выполнено для F, то оно выполнено и для G. Прямым следствием данного утверждения является то, что если какая-то функция из класса EA-эквивалентности удовлетворяет условию (1), то все функции из этого класса также удовлетворяют этому условию. Таким образом, достаточно проверять только одного представителя класса EA-эквивалентности. В [5] приведены представители классов EA-эквивалентности векторных булевых функций, которые покрывают все APN-функции от не более чем пяти переменных (10 классов) и все квадратичные APN-функции от шести переменных (13 классов). В [6] приведён список всех известных представителей классов EA-эквивалентности APN-функций от семи (490 классов) и восьми переменных (8180 классов). В данной работе с помощью компьютерных вычислений были проверены представители этих классов и установлено, что они удовлетворяют условию (1). Утверждение 2. Условию (1) удовлетворяют все APN-функции от не более чем пяти переменных, все квадратичные APN-функции от шести переменных и все известные APN-функции от семи и восьми переменных. Таким образом, на расстоянии один от любой такой APN-функции все функции являются дифференциально равномерными порядка 4, т. е. на расстоянии один от таких APN-функций нет других APN-функций.

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