A classification of differentially nonequivalent quadratic APN function in 5 and 6 variables.pdf Почти совершенно нелинейные (APN) функции определяются как векторные булевы функции из Fn в Fn, наиболее сильно отличающиеся от самых простых - аффинных функций, если в качестве меры отличия рассматривать максимальное число решений уравнения F(x) фF(xфа) = b по всем а, b £ Fn, а = 0. Для APN-функций это число решений минимально и равно 2. Класс APN-функций мало изучен, несмотря на большое число работ в данной области, не описаны даже все самые простые - квадратичные - APN-функции. Обзору результатов об APN-функциях и смежных с ними посвящена работа М. М. Глухова [1]. Будем обозначать Ba(F) = {F(x) ф F(x ф а) : x £ Fn}. Функции F и G дифференциально эквивалентны [2], если Ba(F) = Ba(G) для любого a £ Fn. Линейным спектром [3] квадратичной APN-функции F называется вектор ЛF = (А^,... , А|п-1), где Af - число линейных функций L, таких, что kLf = k, где kFL = |{а £ Fn \ {0} : Ba(F) = Ba(F ф L)}|. Из определений естественно следует свойство: линейные спектры дифференциально эквивалентных квадратичных APN-функций равны. Обратное в общем случае неверно, т. е. из того, что линейные спектры двух функций совпадают, не следует, что эти функции дифференциально эквивалентны. Функции F и G EA-эквивалентны, если существуют аффинные взаимно однозначные функции A', Л" и аффинная функция A, такие, что G = A' о F о A" ф A. EA-эквивалентность сохраняет свойство функции быть APN. В [3] показано, что линейный спектр - EA-инвариант, и найдены линейные спектры всех квадратичных APN-функций от n = 3, 4,5, 6 переменных. При n = 3, 4 существует только по одному кассу EA-эквивалентности квадратичных APN-функций; при n = 5 - два класса, и их линейные спектры различны; при n = 6 - 13 классов, линейные спектры которых попарно различны, кроме одной пары (функции 3 и 10 в [3, табл.4]). Из данных результатов по свойству выше следует, что не существует дифференциально эквивалентных квадратичных APN-функций, принадлежащих разным классам EA-эквивалентности, при n = 3, 4, 5, 6, кроме, быть может, одного случая при n = 6. Однако удалось вычислительно доказать, что данный случай не реализуется. Доказательство существенно опирается на отличительное свойство квадратичных APN-функций от чётного числа переменных [3]: - пусть F - квадратичная APN-функция от n переменных, n чётно. Тогда для любого v £ Fn размерность Af U {0} чётна. Здесь Af - множество векторов а £ Fn, таких, что линейная часть подпространства Ba(F) совпадает с линейным подпространством {y £ Fn : (y,v) = 0}, где v £ Fn. В этих же обозначениях можно сформулировать следующий известный факт: - пусть F - квадратичная APN-функция от n переменных, n нечётно. Тогда для любого v Е Fn, v = 0, множество состоит из одного элемента. Следующий шаг - проверить, какие функции дифференциально эквивалентны в каждом классе EA-эквивалентности. При n = 3, 4 данные результаты известны [2]. Для n = 5, 6 проведены вычислительные эксперименты, основанные на свойствах выше и том факте, что для любой квадратичной APN-функции F множество Ba(F) - аффинное подпространство размерности n- 1, поэтому его линейная часть может быть однозначно задана одним вектором, ортогональным данному линейному подпространству. Обобщая полученные результаты, сформулируем теорему. Теорема 1. Пусть F - квадратичная APN-функция от n переменных, n Е {3, 4, 5, 6}. Тогда все дифференциально эквивалентные ей квадратичные APN-функции G представляются в виде G = F ф A, где A - аффинная функция. При этом число K таких аффинных функций A равно 22n для всех функций, за исключением функций из трёх классов EA-эквивалентности со следующими представителями: 1) n = 4: APN-функция Голда F(x) = x3, K = 210; 2) n = 6: APN-функция F(x) = a7x3 + x5 + a3x9 + a4x10 + x17 + a6x18, K = 213; 3) n = 8: APN-функция Голда F(x) = x9, K = 220. Здесь функции заданы над конечным полем F2n, a - примитивный элемент поля. Один из дальнейших интересных вопросов следующий: можно ли предложить способ описания всех представителей классов дифференциальной эквивалентности квадратичных APN-функций, отличный от полного их перечисления?

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