On some open questions about apn functions.pdf Работа К. Ньюберг [1] положила начало новому направлению в исследовании векторных булевых функций - изучению совершенно и почти совершенно нелинейных векторных булевых функций, обладающих наилучшей стойкостью к дифференциальному криптоанализу. Векторная булева функция из Fn в Fn называется APN-функцией (Almost Perfect Nonlinear), если уравнение F(x ф а) ф F(x) = b имеет не более двух решений для любых a G Fn \ {0}, b G Fn. В настоящее время APN-функции активно изучаются, но до сих пор многие важные вопросы остаются открытыми. Например, не известно точное число таких функций, нижние и верхние оценки числа APN-функций, оценка их алгебраической степени. Не так многочисленны и известные конструкции APN-функ-ций - степенные функции вида F(x) = xd и несколько полиномиальных (см. подробнее обзоры в [2, 3]). Очень интересен вопрос о конструкции APN-функции с помощью композиции или суммы двух функций и о нахождении итеративных конструкций [4]. Важное место в исследовании векторных функций занимает проблема существования взаимно однозначных APN-функций при чётном п. В своё время была выдвинута гипотеза, что для чётного числа переменных APN-перестановок не существует, однако в 2009 г. Дж. Диллон и др. [5] опровергли это предположение, построив взаимно однозначную APN-функцию над F26, которая CCZ-эквивалентна APN-функции, не являющейся перестановкой. Разработанный авторами [5] метод обобщался для большего числа переменных, однако с его помощью им не удалось найти APN-перестановки от 8 и 10 переменных. Интересно, что при решении этой задачи авторы [5] в неявном виде использовали для построения композицию двух перестановок. Пусть векторная булева функция F имеет следующий вид: F (x) = (/i(x),..., fn(x)), где fi(x) = af о 0 af^xi 0 ... 0 afL..„x 1X2 ...xn. i 0 0 й* i 1^1 0---0U. i i...nJ Утверждение 1. Пусть F1 и F2 - APN-функции из F2 в F2. Тогда F = F1 0 F2 12 0 a1 ,12) v (afl12 0 a2,12) 22 APN-функция тогда и только тогда, когда (afl12 0 af 212) V (a2112 0 a2 212) - 1. Всего в F2 существует 192 APN-функции, значит, всевозможных пар C292 = 18 3 36. Из них 12288 пар F1 и F2, сумма которых является APN-функцией, что составляет около 67%. Перечислим некоторые интересные открытые вопросы в области APN-функций, связанные с проблемой их построения. • Как построить APN-функцию путём композиции или суммы двух векторных функций? Какими свойствами должна обладать такая пара функций? • Можно ли представить произвольную APN-функцию в виде композиции двух векторных функций? В том числе функций, обладающих более «простыми» характеристиками (например, меньшей алгебраической степенью или более коротким полиномиальным представлением)? Так, в работе [5] приведён пример взаимно однозначной APN-функции над F26 алгебраической степени 4, которую можно представить через композицию двух векторных булевых функций меньших степеней - 2 и 3. • Пусть F - APN-функция, действующая из Fn в Fn. Какими свойствами обладают её подфункции? Существует ли характеризация APN-функции через её компонентные булевы функции? Одна из возможных характеризаций APN-функций через подфункции предложена в [4]. • Описать группу автоморфизмов класса APN-функций, APN-перестановок. Какие преобразования не выводят функцию (перестановку) за рамки класса? • Исследовать метрические свойства класса APN-функций. Некоторые продвижения по этому вопросу недавно получены в [6]. • Осуществить классификацию квадратичных APN-функций от п переменных. Напомним, что квадратичная APN-функция также является AB-функцией, т. е. её компонентные функции находятся на максимальном расстоянии от класса аффинных функций, что означает оптимальную стойкость к линейному криптоанализу. Ответы на эти вопросы помогут получить новые конструкции APN-функций, включая итеративные и композиционные, а также упростить их программную и аппаратную реализацию в симметричных шифрах.

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