Characterization of apn functions by means of subfunctions.pdf Векторной булевой функцией F называется любое отображение F : Zn ^ Векторную функцию можно рассматривать как набор из n координатных булевых функций от n переменных, т. е. F = (f1,..., fn). Производной по направлению a Е Zn функции F называется векторная функция DaF, определённая как DaF(x) = F(x)®F(x®a) для всех x Е Zn. Векторная функция F называется дифференциально 5-равномерной [1], если для любых a = 0, b уравнение F(x) ф F(x ф a) = b имеет не более 5 решений. Назовём порядком дифференциальной равномерности F минимальное 5, такое, что F является дифференциально 5-равномерной. Легко видеть, что минимально возможный порядок равен двум. APN-функцией (Almost Perfect Nonlinear) называется дифференциально 2-равномерная векторная функция. Исследованию APN-функций посвящено большое число работ как в России (М. М. Глухов, В. А. Зиновьев, М. Э. Тужилин, Д. Г. Фон-дер-Флаасс и др.), так и за рубежом (K. Nyberg, L. R. Knudsen, C. Carlet, L. Budaghyan, J.Dillon и др.). APN-функции представляют интерес для криптографических приложений, в частности для использования в качестве S-блоков в блочных шифрах, поскольку обеспечивают оптимальную стойкость к дифференциальному криптоанализу. Обзор известных APN-функций приводится в работе [2]. Пусть S - векторная функция от n переменных, S = (s 1,... , Sn). Определение 1. Назовём функции F, G, f, g набором подфункций S, если они получены из S при фиксации координаты x^ и функции Sj, где i,j = 1,... ,n, следующим образом: F(x) = (si(xi,o),... , Sj-i(xi,o), Sj+i(xi,o),... , Sn(xi,o)), f (x) = Sj(x*,o), G(x) = (Si(xi,i),... , Sj-i(xi,i), Sj+i(xi,i),..., Sn(xi,i)), g(x) = Sj(xi,i), где xi,o = (xi,... ,xi-i, 0,xi,... ,xn-i) и xM = (xi,... ,xj-b 1,x*,... ,xn-i). В случае i = n, j = n функция S представляется через набор подфункций следующим образом (здесь x Е Zn-1, xn Е Z2): S(x, xn) = ((xn ф 1)F(x) ф xnG(x), (xn ф 1)f (x) ф xng(x)). Определение 2. Назовём набор функций F, G, f, g допустимым, где F, G - векторные, а f, g - булевы функции от n переменных, если выполнены следующие условия: (*) для всех x,y,a Е Z£, a = 0, хотя бы одно из равенств DaF(x) = DaG(y) и Daf (x) = Dag(y) нарушается; (**) для всех x,y,a Е Z^, a = 0, x = y,y ф a, хотя бы одно из равенств DaH(x) = = DaH(y) и Dah(x) = Dah(y) нарушается, где H = F и h = f, либо H = G и h = g. Получена следующая теорема о характеризации APN-функций через набор подфункций, обобщающая результат теоремы 3 из [3]. Теорема 1. Векторная функция S от n переменных - APN-функция тогда и только тогда, когда набор её подфункций F, G, f, g является допустимым и каждая из векторных функций F и G либо APN-функция, либо имеет порядок дифференциальной равномерности равный 4. При малом числе переменных получена следующая характеризация APN-функций от n переменных через векторные подфункции F и G от n - 1 переменных: n = 2 n = 3 n = 4 Количество всех APN-функций от n пер. 192 668 128 18 940 805 775 360 F, G - APN-функции 192 589 824 = 6/7 от всех 4 419 521 347 584 = 7/30 от всех F, G - порядка диф. рав. 4 - 98 304 = 1/7 от всех 11 995 843 657 728 = 19/30 от всех Одна функция - APN, другая - порядка диф. рав. 4 - - 2 525 440 770 048 = 4/30 от всех Вычисления для случая n = 4 проводились на кластере НКС-30Т ССКЦ СО РАН.

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