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

Сформулируем необходимое условие того, что функция из Fn n является APN-функцией.

Лемма 3. Пусть APN-функция F от n переменных принадлежит F'nn, другими словами, множество наборов её аргументов разбивается на пары xi,1 ,xi,2, i = = 1,..., 2n-1, такие, что для каждого i выполнено F(xi;i) = F(xi;2). Тогда для любых j, k E {1,..., 2n-i}, j = k, справедливо xj-)1 + Xj,2 + xk)1 + xk,2 = 0.

Заметим, что из леммы 3 следует, в частности, что в классе F2 2 не может быть APN-функций.

Гипотеза 1. Для любого n > 2 в классе F!nn есть APN-функции.

В результате компьютерных экспериментов при n = 3 обнаружено, что для каждой APN-функции из класса F 3, веса координатных функций которой равны 2 или 6, существует ровно 128 аффинных векторных функций, дающих в сумме с ней APN-перестановку. Для APN-функций с другими весами координатных функций также всегда существуют соответствующие аффинные функции. Естественно предположить далее, что для некоторых других n пересечение множества APN-функций с классом K также непусто. Заметим, что для n = 4 в классе K нет APN-функций, поскольку иначе существовала бы APN-перестановка от четырёх переменных, что, как известно, не так.

Гипотеза 2. Для некоторых значений n ^ 5 в классе K есть APN-функции.

Истинность гипотезы 2 для конкретных чётных значений n влечёт существование взаимно однозначных APN-функций для соответствующего числа переменных.

ЛИТЕРАТУРА

1. Nyberg K. Differentily uniform mappings for cryptography // Eurocrypt 1993. LNCS. 1994. V. 765. P. 55-64.

2. Глухов М. М. О совершенно нелинейных и почти совершенно нелинейных функциях // Матем. вопр. криптограф. 2016.

3. McQuistan M. T., Wolfe A. J., Browning K. A., and Dillon J. F. An APN permutation in dimension six // Amer. Math. Soc. 2010. V. 518. P. 33-42.

4. Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3. С. 14-20.

5. Carlet C. Open questions on nonlinearity and on APN Functions // LNCS. 2015. V. 9061. P. 83-107.

УДК 519.7 DOI 10.17223/2226308X/9/8

О ДИФФЕРЕНЦИАЛЬНОЙ ЭКВИВАЛЕНТНОСТИ КВАДРАТИЧНЫХ

APN-ФУНКЦИЙ1

А. А. Городилова

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

1 Работа поддержана грантом РФФИ, проект 15-07-01328.

совершенно нелинейных (APN) функций, так как его решение может потенциально привести к новым конструкциям APN-функций. В работе начато изучение данного вопроса с исследования аффинных функций, прибавление которых к квадратичным APN-функциям не выводит за рамки их классов дифференциальной эквивалентности. Полностью описаны такие аффинные функции для известного класса APN-функций Голда. Получены вычислительные результаты для известных квадратичных APN-функций от малого числа переменных 2, ..., 8.

Ключевые слова: векторная булева функция, почти совершенно нелинейная функция, дифференциальная эквивалентность.

Отображение F : F^ ^ F^ называется почти совершенно нелинейной функцией (APN-функцией), если для любых векторов a, b G F^, a = (0,..., 0), уравнение F(x) + F(x + a) = b имеет не более двух решений. APN-функции интересны для использования в криптографических приложениях в силу их оптимальной стойкости к дифференциальному методу криптоанализа. Обзорам APN-функций посвящены работы М. Э. Тужилина [1], А. Потта [2]. Некоторые открытые вопросы в области APN-функций представлены в работе К. Карле [3]. Например, открытому вопросу о существовании APN-подстановок посвящены работы М. М. Глухова [4], В. Н. Сачкова [5].

Для векторной функции F от n переменных определяется ассоциированная булева функция Yf от 2n переменных по правилу yF(a, b) = 1, где a, b G F^, если a = (0,... , 0) и уравнение F(x) + F(x + a) = b имеет решение, и yF(a,b) = 0 иначе. Легко видеть, что F — APN-функция тогда и только тогда, когда wt(YF) = 22n-1 — 2n-1, где wt — вес Хэмминга булевой функции. Введём следующее определение.

Определение 1. Функции F и G называются дифференциально эквивалентными, если Yf = Yg. Обозначим класс дифференциальной эквивалентности F через DEf .

Говорят, что две векторные функции F и G EA-эквивалентны, если существуют аффинные взаимно однозначные функции A',A'' и аффинная функция A, такие, что G = A' о F о A'' + A. Дифференциальная и EA-эквивалентности сохраняют свойство функции быть почти совершенно нелинейной. Однако в настоящий момент не известно, вкладываются ли классы дифференциальной эквивалентности APN-функций в соответствующие классы EA-эквивалентности APN-функций. Ответ на этот вопрос может потенциально привести к новым конструкциям APN-функций.

Утверждение 1. Пусть F и G — EA-эквивалентные функции. Тогда |DEF| = = |DEG|. Более того, если G = A' о F о A" + A и DEF = {F1,... ,Fk}, то DEG = = {A' о F1 о A" + A,..., A' о Fk о A" + A}.

Легко видеть, что класс дифференциальной эквивалентности любой APN-функции F содержит 22n тривиальных различных функций Fc,d(x) = F(x + c) + d, c, d G Fn. В [6] найден пример APN-функции от четырёх переменных, чей класс дифференциальной эквивалентности шире, чем тривиальный (состоящий из 22n функций Fc,d). В данной работе случай n = 4 рассмотрен полностью. В табл. 1 приведены значения мощностей классов дифференциальной эквивалентности APN-функций от малого числа переменных n = 2, 3, 4.

Поскольку задача описания класса дифференциальной эквивалентности в общем случае представляется сложной, в данной работе начато её рассмотрение применительно к квадратичным APN-функциям, а именно исследуется вопрос, когда функции F и F + A дифференциально эквивалентны, где F — квадратичная APN-функ-ция, а A — произвольная аффинная функция. Заметим, что для любой квадратичной

Таблица 1

п Кол-во ЕА-классов ЕА-представитель Г(х) deg(F) |

2 1 3 х3 2 24

3 1 3 х3 2 26

4 2 3 х3 2 210

х3 + (х2 + х + 1) ^(х3) 3 210

АРК-функции 22п таких аффинных функций всегда существует, поскольку ^¿(ж) = = ^(ж + с) + d = ^(ж) + (^(ж) + ^(ж + с) + = ^(ж) + А^(ж), где А^ — аффинная функция в силу квадратичности ^.

По аналогии с утверждением 1 справедливо следующее

Утверждение 2. Для квадратичной АРК-функции ^ число различных аффинных функций А, таких, что ^ и ^ + А дифференциально эквивалентны, инвариантно относительно ЕА-преобразования.

Для известного класса АРК-функций Голда получена следующая теорема, полностью описывающая все аффинные функции, прибавление которых к исходной функции не выводит за рамки её класса дифференциальной эквивалентности. Напомним, что векторную функцию ^ : КП ^ КП можно рассматривать как функцию над конечным полем К2п и однозначно представлять в виде полинома степени не выше 2п — 1: 2П —1

^(ж) = ^ агжг, где аг € К2п. При этом степень функции равна шах^^г) : аг = 0},

i=0

где '^(г) —двоичный вес числа.

Теорема 1. Пусть ^ — АРК-функция Голда от п переменных, ^(ж) = ж2к+1 и (к,п) = 1. Тогда выполнены следующие утверждения:

1) если п = 4£ для некоторого £ и к = п/2 ± 1, то существуют в точности 22п+п/2 различных аффинных функций А, таких, что ^ и ^ + А дифференциально эквивалентны, при этом А (ж) = а + Л2к ж + Лж2к + 5ж2', где а, Л, 5 € К2п; 5 = 52"/2; ] = к — 1 при к = п/2 + 1 и ] = п — 1 при к = п/2 — 1;

2) иначе существуют в точности 22п различных аффинных функций А, таких, что ^ и ^ + А дифференциально эквивалентны, при этом А (ж) = а + Л2 ж + Лж2 , где а, Л € К2п.

Теорема 1 показывает, что среди АРК-функций Голда существуют такие, чей класс дифференциальной эквивалентности шире, чем тривиальный. А именно это функции ^(ж) = ж2"/2±1+1 при п, кратном 4 (заметим, что эти функции ЕА-эквивалентны). В табл. 2 приведены вычислительные результаты, полученные для всех известных ЕА-классов квадратичных АРК-функций от 2 до 8 переменных. Отметим, что ЕА-классификация квадратичных АРК-функций вплоть до 6 переменных известна полностью, а для 7 и 8 переменных найдена частичная классификация (см. [2]).

Как видно из табл. 2, для почти всех рассмотренных ЕА-классов существует только 22п тривиальных аффинных функций Ае,^. Исключения составляют следующие:

п = 4: АРК-функция Голда ж3;

п = 6: АРК-функция и7ж3 + ж5 + и3ж9 + и4ж10 + ж17 + и6ж18;

п = 8: АРК-функция Голда ж9.

Таблица 2

n Кол-во EA-классов Кол-во аффинных функций А: Г + А € р

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

ЛИТЕРАТУРА

1. Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3. С. 14-20.

2. Pott A. Almost perfect and planar functions // Des. Codes Cryptogr. 2016. V. 78. P. 141-195.

3. Carlet C. Open questions on nonlinearity and on APN functions // Arithmetic of Finite Fields. LNCS. 2015. V. 9061. P. 83-107.

4. Глухов М. М. О матрицах переходов разностей при использовании некоторых модулярных групп // Матем. вопр. криптограф. 2013. Т. 4. №4. С. 27-47.

5. Сачков В. Н. Комбинаторные свойства дифференциально 2-равномерных подстановок // Матем. вопр. криптограф. 2015. Т. 6. №1. С. 159-179.

6. Городилова А. А. О пересечении множеств значений производных APN-функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 25-27.

УДК 512.542.3 DOI 10.17223/2226308X/9/9

ФУНКЦИИ С ВАРИАЦИОННО-КООРДИНАТНОЙ ПОЛИНОМИАЛЬНОСТЬЮ НАД ГРУППОЙ

А. И. Зуева, А. В. Карпов

Определён класс функций с вариационно-координатной полиномиальностью над группой, являющийся обобщением класса ВКП-функций над примарным кольцом вычетов. Представлен алгоритм нахождения координат для элемента группы. Доказано, что класс ВКП-функций над UTn(Zp) не совпадает с классом полиномиальных функций. Указан способ обращения биективной ВКП-функции над UTn(Zp).

Ключевые слова: функции над группой, функции с вариационно-координатной полиномиальностью, координатные функции.

В [1] определён класс функций с вариационно-координатной полиномиальностью (ВКП-функций) над примарным кольцом вычетов, порождающий системы ВКП-урав-нений, для решения которых применим метод покоординатной линеаризации.

В данной работе делается обобщение класса ВКП-функций на случай, когда полиномы рассматриваются над группой с нормальным рядом. Получающийся при этом класс ВКП-функций над группой даёт конструктивный пример дифференцируемых функций над группой, рассмотренных в [2].

Пусть задана группа G с нормальным рядом G = H0 ¡> H ¡>... ¡> Hn = e. Как и в случае примарного кольца вычетов, для определения класса ВКП-функций над группой необходимо определить понятие координатной функции полинома над группой.