О дифференциальной эквивалентности квадратичных APN-функций | ПДМ. Приложение. 2016. № 9.

О дифференциальной эквивалентности квадратичных APN-функций

Для векторной булевой функции F : Fn ^ Fn определяется ассоциированная булева функция yf от 2n переменных по правилу: yf(a, b) = 1, где a,b Е Fn, если a = (0,..., 0) и уравнение F(x) + F(x + a) = b имеет решение, и yf(a, b) = 0 иначе. Вводится понятие дифференциально эквивалентных векторных булевых функций как функций, имеющих одинаковые ассоциированные булевы функции. Интересен вопрос описания классов дифференциальной эквивалентности почти совершенно нелинейных (APN) функций, так как его решение может потенциально привести к новым конструкциям APN-функций. В работе начато изучение данного вопроса с исследования аффинных функций, прибавление которых к квадратичным APN-функциям не выводит за рамки их классов дифференциальной эквивалентности. Полностью описаны такие аффинные функции для известного класса APN-функций Голда. Получены вычислительные результаты для известных квадратичных APN-функций от малого числа переменных 2, ..., 8.

On differential equivalence of quadratic apn functions.pdf Отображение F : Fn ^ Fn называется почти совершенно нелинейной функцией (APN-функцией), если для любых векторов a, b Е Fn, а = (0,..., 0), уравнение F(x) + F(x + а) = b имеет не более двух решений. APN-функции интересны для использования в криптографических приложениях в силу их оптимальной стойкости к дифференциальному методу криптоанализа. Обзорам APN-функций посвящены работы М. Э. Тужилина [1], А. Потта [2]. Некоторые открытые вопросы в области APN-функций представлены в работе К. Карле [3]. Например, открытому вопросу о существовании APN-подстановок посвящены работы М. М. Глухова [4], В. Н. Сачкова [5]. Для векторной функции F от n переменных определяется ассоциированная булева функция Yf от 2n переменных по правилу yf(а, b) = 1, где а, b Е Fn, если а = (0,... , 0) и уравнение F(x) + F(x + а) = b имеет решение, и yf(а,^ = 0 иначе. Легко видеть, что F - APN-функция тогда и только тогда, когда wt(YF) = 22n-1 - 2n-1, где wt - вес Хэмминга булевой функции. Введём следующее определение. Определение 1. Функции F и G называются дифференциально эквивалентными, если Yf = Yg. Обозначим класс дифференциальной эквивалентности F через DEf . Говорят, что две векторные функции F и G EA-эквивалентны, если существуют аффинные взаимно однозначные функции Л', Л" и аффинная функция Л, такие, что G = Л' о F о Л'' + Л. Дифференциальная и EA-эквивалентности сохраняют свойство функции быть почти совершенно нелинейной. Однако в настоящий момент не известно, вкладываются ли классы дифференциальной эквивалентности APN-функций в соответствующие классы EA-эквивалентности APN-функций. Ответ на этот вопрос может потенциально привести к новым конструкциям APN-функций. Утверждение 1. Пусть F и G - EA-эквивалентные функции. Тогда |DEF | = = |DEG|. Более того, если G = Л' о F о Л'' + Л и DEF = {F1,..., Fk}, то DEG = = {Л' о F1 о Л'' + Л,..., Л' о Fk о Л'' + Л}. Легко видеть, что класс дифференциальной эквивалентности любой APN-функции F содержит 22n тривиальных различных функций Fc,d(x) = F(x + c) + d, c, d Е Fn. В [6] найден пример APN-функции от четырёх переменных, чей класс дифференциальной эквивалентности шире, чем тривиальный (состоящий из 22n функций Fc,d). В данной работе случай n = 4 рассмотрен полностью. В табл. 1 приведены значения мощностей классов дифференциальной эквивалентности APN-функций от малого числа переменных n = 2, 3, 4. Поскольку задача описания класса дифференциальной эквивалентности в общем случае представляется сложной, в данной работе начато её рассмотрение применительно к квадратичным APN-функциям, а именно исследуется вопрос, когда функции F и F + Л дифференциально эквивалентны, где F - квадратичная APN-функ-ция, а Л - произвольная аффинная функция. Заметим, что для любой квадратичной Таблица 1 n Кол-во EA-классов EA-представитель F(ж) deg(F) |DE F | 2 1 ж3 2 24 3 1 3 ж3 2 26 4 2 3 ж3 2 210 ж3 + (ж2 + ж + 1) tr(x3) 3 210 APN-функции 22n таких аффинных функций всегда существует, поскольку Fc,d(x) = = F(ж + c) + d = F(ж) + (F(ж) + F(ж + c) + d) = F(ж) + А^(ж), где Af,d - аффинная функция в силу квадратичности F. По аналогии с утверждением 1 справедливо следующее Утверждение 2. Для квадратичной APN-функции F число различных аффинных функций A, таких, что F и F + A дифференциально эквивалентны, инвариантно относительно EA-преобразования. Для известного класса APN-функций Голда получена следующая теорема, полностью описывающая все аффинные функции, прибавление которых к исходной функции не выводит за рамки её класса дифференциальной эквивалентности. Напомним, что векторную функцию F : F^ ^ F^ можно рассматривать как функцию над конечным полем F2n и однозначно представлять в виде полинома степени не выше 2n - 1: 2n-1 F(ж) = Y1 а»жг, где ai G F2n. При этом степень функции равна max{wt(i) : ai = 0}, i=0 где wt(i) -двоичный вес числа. Теорема 1. Пусть F - APN-функция Голда от n переменных, F(ж) = ж2+1 и (k,n) = 1. Тогда выполнены следующие утверждения: 1) если n = 4t для некоторого t и k = n/2 ± 1, то существуют в точности 22n+n/2 различных аффинных функций A, таких, что F и F + A дифференциально эквивалентны, при этом A(ж) = а + Л2кж + Лж2к + 5ж2', где а, Л, 5 G F2n; 5 = 52"/2; j = k - 1 при k = n/2 + 1 и j = n - 1 при k = n/2 - 1; 2) иначе существуют в точности 22n различных аффинных функций A, таких, что F и F + A дифференциально эквивалентны, при этом A(ж) = а + Л2 ж + Лж2 , где а, Л G F2n. Теорема 1 показывает, что среди APN-функций Голда существуют такие, чей класс дифференциальной эквивалентности шире, чем тривиальный. А именно это функции F(ж) = ж2"/2±1+1 при n, кратном 4 (заметим, что эти функции EA-эквивалентны). В табл. 2 приведены вычислительные результаты, полученные для всех известных EA-классов квадратичных APN-функций от 2 до 8 переменных. Отметим, что EA-классификация квадратичных APN-функций вплоть до 6 переменных известна полностью, а для 7 и 8 переменных найдена частичная классификация (см. [2]). Как видно из табл. 2, для почти всех рассмотренных EA-классов существует только 22n тривиальных аффинных функций Ac,d. Исключения составляют следующие: n = 4: APN-функция Голда ж3; n = 6: APN-функция и7ж3 + ж5 + и3ж9 + и4ж10 + ж17 + и6ж18; n = 8: APN-функция Голда ж9. Таблица 2 n Кол-во EA-классов Кол-во аффинных функций A: F + A G Т>£F 2 1 24 3 1 26 4 1 210 5 2 Для обоих классов: 210 6 13 Для одного класса: 213; для остальных 12 классов: 212 7 > 487 Для всех известных 487 классов: 214 8 > 8179 Для одного класса из известных 8179: 220; для остальных 8178 классов: 216

Ключевые слова

векторная булева функция, почти совершенно нелинейная функция, дифференциальная эквивалентность, vectorial Boolean functions, almost perfect nonlinear functions, differential equivalence

Авторы

ФИООрганизацияДополнительноE-mail
Городилова Анастасия АлександровнаИнститут математики им. С. Л. Соболева СО РАНаспиранткаgorodilova@math.nsc.ru
Всего: 1

Ссылки

Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3. С. 14-20.
Pott A. Almost perfect and planar functions // Des. Codes Cryptogr. 2016. V. 78. P. 141-195.
Carlet C. Open questions on nonlinearity and on APN functions // Arithmetic of Finite Fields. LNCS. 2015. V. 9061. P. 83-107.
Глухое М. М. О матрицах переходов разностей при использовании некоторых модулярных групп // Матем. вопр. криптограф. 2013. Т. 4. №4. С. 27-47.
Сачков В. Н. Комбинаторные свойства дифференциально 2-равномерных подстановок // Матем. вопр. криптограф. 2015. Т. 6. №1. С. 159-179.
Городилова А. А. О пересечении множеств значений производных APN-функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 25-27.
 О дифференциальной эквивалентности квадратичных APN-функций | ПДМ. Приложение. 2016. № 9.

О дифференциальной эквивалентности квадратичных APN-функций | ПДМ. Приложение. 2016. № 9.