Векторные 2-в-1 функции как подфункции взаимно однозначных APN-функций | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/11

Векторные 2-в-1 функции как подфункции взаимно однозначных APN-функций

Работа посвящена проблеме существования взаимно однозначных APN-функций от чётного числа переменных. Рассматриваются свойства подфункций взаимно однозначных APN-функций. Доказано, что любая (n - 1)-подфункция произвольной взаимно однозначной APN-функции может быть получена при помощи специальных символьных последовательностей. Данные результаты позволяют предложить новый алгоритм построения взаимно однозначных APN-функций из 2-в-1 функций и соответствующих координатных булевых функций. Получена нижняя оценка на число таких булевых функций.

Vectorial 2-to-1 functions as subfunctions of apn permutations.pdf Векторной булевой функцией F называется произвольное отображение F : Fn ^ Fm. Рассмотрим векторную булеву функцию F из F^ в F^. Для векторов a, b G Fn, где a = 0, определим величину £(a,b) = |{x G Fn : F(x + a) + F(x) = b}|. Обозначим за Ар следующий параметр: Af = max ^(a,b). Тогда F называется дифференциально AF-равномерной функцией. Чем меньше параметр А^, тем более устойчив к дифференциальному криптоанализу блочный шифр, содержащий функцию F в качестве S-блока. Для векторных функций из Fn в Fn минимально возможное значение Af равно 2. В этом случае функция F называется почти совершенно нелинейной функцией, или APN-функцией. Данные понятия введены К. Ньюберг в [1], однако известно [2], что APN-функции также изучались В. А. Башевым и Б. А. Егоровым в СССР в 60-х годах. Подробнее об APN-функциях можно прочесть в [3-5]. Одна из самых интересных проблем в данной области связана со взаимно однозначными APN-функциями [6]. Долгое время имела место гипотеза, что не существует взаимно однозначных APN-функций от чётного числа переменных. Однако в 2009 г. авторы работы [7] нашли первый и единственный (с точностью до эквивалентности) на данный момент пример взаимно однозначной APN-функции над F^. Для больших размерностей вопрос существования по-прежнему открыт. Векторная функция F : Fn ^ Fn называется 2-в-1 функцией, если её множество значений состоит из 2n-i элементов и каждое значение она принимает ровно на двух аргументах. Рассмотрим произвольную векторную функцию F = (/i,... , /n) из Fn в Fn. Будем называть векторную булеву функцию Fj из Fn в Fn-i (n - 1)-подфункцией функции F, если Fj = (/i,... , /j-i, /j+i,... , /n) для некоторого j Е {1,... , n}. Напомним, что множеству Fn можно сопоставить во взаимно однозначное соответствие целочисленное множество {0,..., 2n - 1}, где каждое число является десятичным представлением вектора из Fn . Тогда произвольную (n - 1)-подфункцию Fj из Fn в Fn-i можно рассматривать как векторную функцию из Fn в Fn, принимающую значения из множества {0,..., 2n-i - 1}. Рассмотрим произвольную 2-в-1 функцию, принимающую значения из {0,... , 2n-i - 1}, тогда вектор её значений может быть представлен в виде некоторой перестановки упорядоченного вектора (0,0,1,1,... , 2n-i - 1, 2n-i - 1). Будем обозначать множество таких 2-в-1 функций от n переменных через 7П. Можно заметить, что тогда любая (n - 1)-подфункция взаимно однозначной векторной функции принадлежит 7n. Имеет место следующее утверждение [8]. Лемма 1. Пусть F - взаимно однозначная APN-функция от n переменных. Тогда любая её (n - 1)-подфункция является дифференциально 4-равномерной функцией из 7^. В [8, 9] рассматривается алгоритм построения 2-в-1 APN-функций при помощи специальных так называемых допустимых символьных последовательностей. В [8] доказана следующая Теорема 1. Пусть F - взаимно однозначная APN-функция от n переменных. Тогда символьная последовательность, соответствующая вектору значений произвольной (n - 1)-подфункции F, является допустимой. Таким образом, любая взаимно однозначная APN-функция может быть получена из некоторой 2-в-1 дифференциально 4-равномерной функции, построенной при помощи допустимой последовательности. Данное наблюдение позволяет предложить следующий алгоритм для поиска новых взаимно однозначных APN-функций. С помощью аппарата допустимых последовательностей строим 2-в-1 векторную функцию S, принадлежащую 7^ (подробнее о данном построении см. в [8]) и проверяем её на дифференциальную равномерность. Если S дифференциально 4-равно-мерная, то она может являться (n - 1)-подфункцией некоторой взаимно однозначной APN-функции. Необходимо проверить, существует ли сбалансированная булева функция f, такая, что взаимно однозначная функция H = S U f является APN-функцией. Заметим, что требуется проверить 22п булевых функций, поскольку на каждую пару одинаковых значений 2-в-1 функции S приходится пара {0,1} из значений булевой функции f. Обозначим через nf (S) число булевых функций f, таких, что H = S U f является взаимно однозначной APN-функцией. Получена следующая нижняя оценка для данной величины: Теорема 2. Пусть S - векторная функция из 7П, построенная с помощью допустимой последовательности. Тогда если nf (S) = 0, то nf (S) ^ 2n. С помощью компьютерных вычислений проверено, что данная оценка является точной при n = 3, 5, а также при n = 6 для всех (n - 1)-подфункций APN-функции Диллона.

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

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

Авторы

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

Ссылки

Idrisova V.A. On an algorithm generating 2-to-1 APN functionsand its applications to "the big APN problem" // Cryptography and Communications. 2018. Published online.
Идрисова В. А. О построении APN-функций специального вида и их связи с взаимно однозначными APN-функциями // Прикладная дискретная математика. Приложение. 2017. № 10. С. 36-38.
Carlet C. Open questions on nonlinearity and on APN functions // LNCS. 2015. V. 9061. P. 83-107.
McQuistan M. T., Wolfe A. J., Browning K. A., and Dillon J. F. An apn permutation in dimension six // Amer. Math. Soc. 2010. No. 518. P. 33-42.
Blondeau C. and Nyberg K. Perfect nonlinear functions and cryptography // Fields and Their Appl. 2015. V. 32. P. 120-147.
Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3(5). С. 14-20.
Pott A. Almost perfect and planar functions // Des. Codes Cryptography. 2016. No. 78(1). P. 141-195.
Глухов М. М. О приближении дискретных функций линейными функциями // Математические вопросы криптографии. 2016. Т. 7. №4. С. 29-50.
Nyberg K. Differentily uniform mappings for cryptography // Eurocrypt 1993. LNCS. 1994. V. 765. P. 55-64.
 Векторные 2-в-1 функции как подфункции взаимно однозначных APN-функций | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/11

Векторные 2-в-1 функции как подфункции взаимно однозначных APN-функций | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/11