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

О специальном подклассе векторных булевых функций и проблеме существования APN-перестановок

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

On special class of vectorial boolean functions and the problem of apn permutations existence.pdf Векторной булевой функцией (S-блоком) называется произвольное отображение F : Fn ^ Fm. Векторную функцию можно рассматривать как набор из m координатных булевых функций от n переменных, т. е. F = (f1,... , fm). Далее в работе рассматриваются только функции вида F : Fn ^ Fn. Появление в 1990 г. дифференциального криптоанализа вызвало необходимость поиска функций, наиболее стойких к данному методу. Так, в 1992 г. было предложено понятие APN-функции, а затем и дифференциально ^-равномерной функции [1]. Векторная булева функция называется APN-функцией (почти совершенно нелинейной), если уравнение F(x+a) + F(x) = b имеет не более двух решений для любых a Е Fn\{0}, b Е Fn. Первый пример APN-функции был указан ещё в 1968 г. В. А. Башевым и в дальнейшем исследован Б. А. Егоровым [2]. Интересно, что именно эта функция была затем использована в качестве S-блока криптосистемы AES. Центральное место в исследовании таких функций занимает проблема существования взаимно однозначных APN-функций (или APN-перестановок) при чётном n. В своё время была выдвинута гипотеза (и доказана для случая n = 4), что для чётного числа переменных APN-перестановок не существует, однако в 2009 г. Дж. Диллон и др. [3] опровергли это предположение, построив взаимно однозначную APN-функцию при n = 6. Более подробная информация содержится в [4, 5]. Настоящая работа посвящена изучению векторных функций со структурой множества значений определённого вида. Обозначим множество My = {x Е Fn : F(x) = y}. Рассмотрим некоторую функцию F для произвольного n, такую, что для каждого y выполняется |My | Е {0, 2}, то есть множество всех аргументов функции разбивается на пары, на которых значение F совпадает. Будем обозначать класс таких функций Fnn. Две векторные функции F и G называются аффинно эквивалентными, если существуют аффинные перестановки A1, A2, такие, что выполнено F = A1 oGoA2. Заметим, что взаимная однозначность, а также свойство функции быть APN сохраняются при таком преобразовании. Понятие аффинной эквивалентности расширяется следующим образом. Две векторные функции F и G называются EA-эквивалентными (расширенно аффинно эквивалентными), если существуют аффинные перестановки A1, A2 и аффинная функция A, такие, что выполнено F = A1 о G о A2 + A. Известно, что EA-эквивалентность сохраняет свойство функции быть APN, в то время как свойство взаимной однозначности может уже не сохраниться - прибавление аффинной функции может нарушить структуру перестановки. Первая APN-перестановка от шести переменных была получена путём применения специального преобразования к некоторой APN-функции (которая изначально не являлась взаимно однозначной), такого, что эти функции CCZ-эквивалентны (другая эквивалентность более сложного вида, которая так же, как и EA-эквивалентность, сохраняет свойство функции быть APN). В этой работе мы пробуем реализовать похожую идею, однако в качестве преобразования рассмотрим частный случай EA-экви-валентности - когда преобразования A1 и A2 являются тождественными. Хотелось бы выделить в множестве векторных булевых функций некоторый подкласс, состоящий из функций, отличающихся от перестановок на аффинную функцию, то есть таких, что добавление к ним аффинной функции приводит к взаимно однозначной функции. Если в таком классе при каких-то чётных n содержатся APN-функции, то мы бы получили конструктивное решение открытого вопроса о существовании взаимно однозначных перестановок от чётного числа переменных. Лемма 1. Для любой векторной функции F из класса Fln n существует векторная функция S, каждая координатная булева функция которой сбалансированна или константна, такая, что F + S - взаимно однозначная функция. Напомним, что аффинные функции, отличные от константы, являются сбалансированными. Заметим, что произвольная аффинная векторная функция принадлежит множеству векторных функций S из леммы 1. Поэтому естественно предположить, что в классе F'nn может находиться искомый подкласс функций, отличающихся от перестановок на аффинную функцию. Напомним, что под расстоянием между двумя булевыми функциями подразумевается расстояние Хэмминга между их векторами значений. Лемма 2. Для любой булевой функции f чётного веса от n переменных, которая находится на расстоянии не более чем 2n + 2 от константной функции, существует аффинная булева функция а, такая, что а + f - сбалансированная функция. Заметим, что все координатные булевы функции произвольной векторной функции F из класса F'nn имеют чётный вес. Значит, для векторных булевых функций, чьи координатные функции удовлетворяют условиям леммы 2, найдутся аффинные векторные функции, сумма с которыми даёт покоординатно сбалансированные векторные функции, частным случаем которых и являются перестановки. Пусть K - множество всех таких функций F из F'n n, что для каждой функции существует аффинная функция A, дающая в сумме с F взаимно однозначную функцию. Заметим, что множество K непусто. Действительно, для любого n в этом классе лежат функции F1 = (0, x2,... , xn), F2 = (x1, 0, x2,... , xn), ... , Fn = (x1, x2,... , xn-1, 0). Заметим, что если взять соответственно аффинные функции A1 = (x1, 0,..., 0), A2 = (0, x2, 0,... , 0), ..., An = (0,... , 0, xn), то их суммы равны Aj + Fj = (x1,... , xn), то есть являются тождественной функцией, которая взаимно однозначна. Сформулируем необходимое условие того, что функция из Flnn является APN-функцией. Лемма 3. Пусть APN-функция F от n переменных принадлежит F'nn, другими словами, множество наборов её аргументов разбивается на пары xi, 1,xi ,2, i = = 1,..., 2n-1, такие, что для каждого i выполнено F(xi; 1) = F(xi;2). Тогда для любых j,k Е {1,..., 2n-1}, 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-функций для соответствующего числа переменных.

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

векторная булева функция, APN-функция, взаимно однозначная функция, перестановка, vectorial Boolean function, APN function, bijective function, permutation

Авторы

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

Ссылки

Nyberg K. Differentily uniform mappings for cryptography // Eurocrypt 1993. LNCS. 1994. V. 765. P. 55-64.
Глухов М. М. О совершенно нелинейных и почти совершенно нелинейных функциях // Матем. вопр. криптограф. 2016. (в печати)
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.
Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3. С. 14-20.
Carlet C. Open questions on nonlinearity and on APN Functions // LNCS. 2015. V. 9061. P. 83-107.
 О специальном подклассе векторных булевых функций и проблеме существования APN-перестановок | ПДМ. Приложение. 2016. № 9.

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