О построении APN-функций специального вида и их связи с взаимно однозначными APN-функциями | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/14

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

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

On constructing special apn functions and their link with apn permutations.pdf Стойкость криптосистемы существенно зависит от правильного выбора её нелинейных компонент (S-блоков). Математически S-блок представляет собой векторную булеву функцию. Векторной булевой функцией F называется произвольное отображение F : Fn - Fm. Далее рассматриваются только функции вида F : Fn - Fn. Среди требований, выдвигаемых к криптографическим булевым функциям, важное место занимает устойчивость к дифференциальному криптоанализу. Векторные функции, обладающие оптимальной такой стойкостью, называются APN-функциями, или почти совершенно нелинейными. Понятие APN-функции введено К. Ньюберг в 1992 г. [1], однако известно [2], что APN-функции изучались в СССР В. А. Башевым и Б. А. Егоровым начиная с 1968 г. Векторная булева функция называется APN-функ-цией, если уравнение F(x ф a) ф F(x) = b имеет не более двух решений для любых a e Fn \ {0}, b e Fn В SP-сети для обратимости процесса шифрования используются взаимно однозначные векторные функции, или перестановки. Поэтому центральное место в изучении почти совершенно нелинейных функций занимает проблема существования взаимно однозначных APN-функций для чётного числа переменных, известная в англоязычной литературе как «the Big APN Problem». Лишь в 2009 г. была представлена первая APN-перестановка для n = 6 [3], причём до этого долгое время считалось, что при чётных n таких функций нет. Интересно, что данная функция сразу же нашла применение в легковесном блочном шифре FIDES. Для чётных размерностей, превосходящих 6, вопрос до сих пор открыт и значительных продвижений не получено. Подробную информацию об исследованиях в данной области можно найти в обзорах [4, 5]. В данной работе рассматривается множество 2-в-1 векторных функций. Векторная функция F : Fn - Fn называется 2-в-1 функцией, если её множество значений состоит из 2n-1 элементов и каждое значение она принимает ровно на двух аргументах. Лемма 1 [6]. Для любой 2-в-1 векторной функции F от n переменных существует векторная функция G, каждая координатная булева функция которой сбалансирована или константна, такая, что F ф G - взаимно однозначная функция. Данный факт влечёт за собой интересное свойство: если F - APN-функция, а G - аффинная, то F ф G является APN-перестановкой, поскольку полученная функция EA-эквивалентна исходной. Две векторных функции F и H называются расширенно аффинно эквивалентными, или EA-эквивалентными, если F = A1 о H о A2 ф A, где A1,A2 - аффинные перестановки; A - аффинная функция. Важным фактом является то, что свойство APN инвариантно относительно расширенного аффинного преобразования. Возможность получения перестановки путём сложения APN-функции с аффинной функцией уже рассматривалась в [7]. Авторы исследовали мономиальные APN-функции, то есть APN-функции вида F(x) = xd над конечным полем GF(2n). Были получены некоторые ограничения на выбор d, при которых не существует такой линейной векторной функции L, что F + L - взаимно однозначная APN-функция. В данной работе предложен алгоритм поиска взаимно однозначных APN-функций через 2-в-1 APN-функции. Алгоритм можно разбить на три этапа. На первом этапе строятся всевозможные символьные последовательности, потенциально представляющие собой вектор значений некоторой 2-в-1 APN-функции. На следующем этапе символам в построенных последовательностях присваиваются двоичные векторы, удовлетворяющие специальным ограничениям, в результате чего получаются 2-в-1 APN-функции. На заключительном этапе для каждой построенной функции F мы ищем аффинную функцию, если таковая существует, которая в сумме с F даёт APN-пере-становку. В работе для n = 5 и 6 найдены примеры 2-в-1 APN-функций и соответствующих линейных функций, дающих в сумме взаимно однозначные функции. Ниже представлены 2-в-1 функция F от пяти переменных, которая эквивалентна APN-перестановке, и сответствующая линейная функция A: F = (0 9 29 19 16 29 4 20 23 16 2 30 18 20 1 2 1 28 0 4 25 19 18 30 14 23 28 14 25 6 9 6); A = (x2 ф x3 ф x4, x4 ф x5, xi Ф x4, xi Ф x2 Ф x3 ф x4, x3 ф x4). Интересно, что при n = 5 для всех пяти существующих (с точностью до аффинной эквивалентности) APN-перестановок найдены 2-в-1 APN-функции, которые в сумме с линейными функциями дают эти перестановки. Ниже представлены 2-в-1 APN-функция F от шести переменных и соответствующая линейная функция A, такие, что Fф A - единственная известная (с точностью до эквивалентности) на данный момент APN-перестановка от чётного числа переменных, полученная в работе [3]: F = (54 63 48 50 4 38 40 1 63 38 45 11 8 32 42 29 54 11 7 36 14 46 23 8 36 51 4 25 9 25 59 32 16 60 59 8 42 1 41 14 50 31 9 23 60 12 21 29 27 24 21 46 27 41 53 53 40 16 51 7 12 31 45 24); A = (xi ф x2 ф x6, xi ф x2 ф x6, xi ф x2 ф x4 ф x6, xi ф x2 ф x6, xi ф x2 ф x4 ф x6, x4 ф xa).

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

векторная булева функция, APN-функция, взаимно однозначная функция, 2-в-1 функция, перестановка, vector Boolean function, APN function, bijective function, 2-to-1 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. Т. 7. №4. С. 29-50.
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.
Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. №3(5). С. 14-20.
Carlet C. Open questions on nonlinearity and on APN functions // LNCS. 2015. V. 9061. P. 83-107.
Виткуп В. А. О специальном подклассе векторных булевых функций и проблеме существования APN-перестановок // Прикладная дискретная математика. Приложение. 2016. №9. С. 19-21. URL: http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000547585
Pasalic E. and Charpin P. Some results concerning cryptographically significant mappings over GF(2n) // Designs, Codes and Cryptography. 2010. V. 57. P. 257-269.
 О построении APN-функций специального вида и их связи с взаимно однозначными APN-функциями | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/14

О построении APN-функций специального вида и их связи с взаимно однозначными APN-функциями | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/14