An iterative construction of almost perfect nonlinear functions.pdf Булевой функцией от n переменных называется любое отображение f : Zn ^ Z2. Весом Хэмминга wt(f) булевой функции f называется количество единиц в векторе ее значений. Векторной булевой функцией F называется любое отображение F : Zn ^ Zm. Векторную функцию можно рассматривать как набор из m координатных булевых функций от n переменных, т. е. F = (f1,... , fm). Булевы функции, использующиеся в криптографических приложениях, должны обладать рядом специальных свойств для обеспечения стойкости к некоторым видам криптоанализа. В работе [1] определено следующее требование к функции. Векторная функция F называется 5-дифференциально равномерной, если для любых векторов a = 0, b уравнение F(x) ф F(x ф a) = b имеет не более 5 решений. Для обеспечения стойкости шифра к дифференциальному криптоанализу необходимо использовать 5-дифференциально равномерные векторные булевы функции с малым значением 5. Далее рассматриваем только случай n = m. В этом случае минимальное возможное 5 равно двум. APN-функцией (Almost Perfect Nonlinear) называется 2-дифферен-циально равномерная векторная функция. В работе [2] приведен обзор по известным APN-функциям. Открытыми вопросами остаются оценки количества и новые способы построения APN-функций. Пусть F : Zn ^ Zn. Для F и любого вектора a = 0 определяется множество Ba(F) = {F(x) ф F(x ф a) : x G Zn}. Для F строится булева функция yf от 2n переменных следующим образом: , J1, если a = 0 и b G Ba(F), yf (a,b) = < I 0 иначе. Известно, что F — APN-функция тогда и только тогда, когда wt(YF) = 22n-1 - 2n-1. Пусть F, F' : Zn ^ ZI^. Определение 1. Функции F и F' назовем y-эквивалентными, если yF = YF'. Нетрудно убедиться, что y-эквивалентность является отношением эквивалентности на множестве всех векторных булевых функций. Следовательно, множество функций распадается на непересекающиеся классы. Получены следующие результаты. Теорема 1. Пусть F — APN-функция от n переменных. Тогда все функции Fc,d(x) = F(x ф c) ф d, где c, d Е Zn, являются APN-функциями, Y-эквивалентными F. Кроме того, все функции Fc,d попарно различны. Теорема 2. Пусть y — булева функция от 2n переменных, y = Yf для некоторой APN-функции F от n переменных. Тогда существует не более 22n APN-функций с такой Y. Следствие 1. В каждом классе Y-эквивалентности APN-функций от n переменных ровно 22n различных функций. Опишем итеративную конструкцию APN-функции от n + 1 переменных из двух APN-функций и двух булевых функций от n переменных. Теорема 3. Пусть F и G — APN-функции от n переменных, f и g — булевы функции от n переменных. Пусть S — векторная булева функция от n + 1 переменных, определённая как S(x,xn+1) = ((xn+1 ф 1)F(x) ф xn+1G(x), (xn+1 ф 1)f (x) ф xn+1g(x)), где x Е Zn, xn+1 Е Z2. Тогда S — APN-функция, если выполнено условие для всех x,y,a Е Zn,a = 0, таких, что F(x) ф F(x ф a) = G(y) ф G(y ф a), выполняется f (x) ф f (x ф a) = g(y) ф g(y ф a). Следствие 2. Пусть F и G — APN-функции от n переменных, f и g — булевы функции от n переменных, удовлетворяющие условию (1). Тогда функции F'(x) = = F(x ф c') ф d', G'(x) = G(x ф c'') ф d'', f' = f (x ф c') ф d1, g'(x) = g(x ф c'') ф d2 удовлетворяют условию (1) для любых c', c'', d', d'' Е Zn, d1, d2 Е Z2. Открытым остается вопрос, как выбрать APN-функции F, G и булевы функции f, g, которые бы удовлетворяли условию (1). При малых n экспериментально показано, что для любой APN-функции F найдется достаточно много функций G, f, g, удовлетворяющих (1). Можно сформулировать гипотезу. Гипотеза 1. Для любой APN-функции F от n переменных найдутся APN-функ-ция G и булевы функции f, g от n переменных, удовлетворяющие условию (1).

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