Связь между кватернарными и компонентными булевыми бент-функциями | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/10

Связь между кватернарными и компонентными булевыми бент-функциями

Исследуются кватернарные бент-функции. Функция д : Zn -у Z4 называется кватернарной функцией от n переменных. Доказано, что свойство кватернарной функции д(х + 2y) = a(x, y) + 2b(x, y) быть бент напрямую не зависит от того, являются ли функции b и a 0 b булевыми бент-функциями. Получено количество кватернарных бент-функций от одной и двух переменных с описанием свойств булевых функций b и a 0 b. Представлены простые конструкции кватернарных бент-функций от любого числа переменных.

Connections between quaternary and component boolean bent functions.pdf Пусть (x, y) обозначает скалярное произведение двоичных векторов x и y по модулю 2, а x.y - их скалярное произведение по модулю 4. Функция f : Zn - Z2 называется булевой функцией от n переменных. Преобразованием Уолша - Адамара булевой функции f от n переменных называется целочисленная функция Wf (x), заданная на множестве Zn равенством Wf(x) = £ (-1)(x,y)®f(y). yezn Булева функция f от чётного числа n переменных называется бент-функцией, если |Wf (x)| = 2n/2 для любого x Е Z!?. Шифры, в которых используются бент-функции, более устойчивы к линейному криптоанализу [1], потому что бент-функции крайне плохо аппроксимируются аффинными функциями. Бент-функции используются в блочном шифре CAST как координатные функции S-блоков [2], а также для построения регистра сдвига с нелинейной обратной связью в поточном шифре Grain [3]. Бент-функции связаны также с некоторыми объектами теории кодирования, например с кодами Рида - Маллера [4]. Функция g : Zn - Z4 называется кватернарной функцией от n переменных [5]. Преобразование Уолша - Адамара кватернарной функции g определяется следующим образом: Wg (x) = £ ix.y+g(y), yeZ n где « +» означает сложение по модулю 4. Кватернарная функция g от n переменных называется бент-функцией, если |Wg (x)| = 4n/2 для любого x G Zn Целью данной работы является изучение связи свойств «быть бент» кватернарных и булевых функций. Эта задача впервые поставлена в работе [6] (см. также [7]). Каждая кватернарная функция g от n переменных может быть представлена для любых x,y G Zn следующим образом: g(x + 2y) = a(x, y) + 26(x, y). Здесь сложение производится по модулю 4, а функции а и b - это компонентные булевы функции от 2n переменных. Утверждение 1. Для любой кватернарной функции g(x + 2y) = a(x, y) + 2b(x, y) от одной переменной, где x,y G Z2, справедливо, что g - кватернарная бент-функция тогда и только тогда, когда b(x,y) -бент-функция и a(x,y) равна 0,1,x или x ф 1. Кроме того, если g - кватернарная бент-функция, то b и аф b - булевы бент-функции. Компьютерные вычисления показали, что количество кватернарных бент-функций от одной переменной равно 32. Количество кватернарных бент-функций при n = 2 равно 200704. Среди них 98304 таких функций, что ни одна из булевых функций a, b и aфb не является бент-функцией, но при этом для 3072 из них а линейная. Существуют 36864 функции, таких, что b и а ф b - бент-функции, при этом для 33792 из них функция а нелинейная, а для 2304 и 768 а является линейной функцией или константой соответственно. Количество кватернарных функций, для которых каждая из функций а, b и а ф b - бент-функция, равно 16384. Для оставшихся 49152 функций а является бент-функцией, b и а ф b - нелинейные булевы функции. Теорема 1. Пусть g(x + 2y) = a(x,y) + 2b(x,y) -кватернарная бент-функция, где x,y G Zn; а, b - булевы функции от 2n переменных. Тогда b и а ф b - нелинейные функции при любом числе переменных n ^ 1. Следующие два утверждения показывают, что между свойствами «быть бент» кватернарной функции g и её компонентных булевых функций b и а ф b нет прямой связи. Утверждение 2. Для любого n ^ 2 существует кватернарная бент-функция g(x + 2y) = a(x, y) + 2b(x, y) от n переменных, где b и афb не являются бент-функциями от 2n переменных. Утверждение 3. Для любого n существует кватернарная функция g(x + 2y) = = a(x,y) + 2b(x,y) от n переменных, которая не является бент-функцией, когда b и а ф b - булевы бент-функции от 2n переменных. Представим две простые конструкции для кватернарных бент-функций от любого числа переменных. Утверждение 4. Кватернарная функция от n переменных n g(xi + 2xn+1, . . . , xn + 2x2n) - 2xixi+n + cxj, i=1 где c G Z2, j G {1,... , n} и «+» - сложение по модулю 4, является бент-функцией при любом n. Заметим, что при этом nn b(xi, . . . , x2n) = 0 xixi+n и a(Xl, . . . , x2n) ф b(xi, . . . , x2n) = 0 xixi+n ф Cxj i=1 i=1 - бент-функции от 2n переменных. Утверждение 5. Пусть g(x + 2y) = a(x, y) + 2b(x, y), где x, y G Zn и a, b - булевы функции от 2n переменных, является бент-функцией. Тогда функция g'(x + 2y) = = 3a(x, y) + 2b(x, y) также является кватернарной бент-функцией от n ^ 1 переменных. Отметим, что утверждение верно и в обратную сторону.

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

кватернарные функции, булевы функции, бент-функции, quaternary functions, Boolean functions, bent function

Авторы

ФИООрганизацияДополнительноE-mail
Шапоренко Александр СергеевичИнститут математики им. С. Л. Соболева СО РАН; Новосибирский государственный университетмладший научный сотрудник; студент; исследователь Лаборатории криптографии JetBrains Researchshaporenko.alexandr@gmail.com
Всего: 1

Ссылки

Matsui M. Linear cryptanalysis method for DES cipher // Eurocrypt'1993. LNCS. 1994. V. 765. P. 386-397.
Adams C. Constructing symmetric ciphers using the CAST design procedure // Design, Codes, and Cryptography. 1997. V. 12. No.3. P. 283-316.
Hell M., Johansson T., Maximov A., and Meier W. A stream cipher proposal: Grain-128 // IEEE Intern. Symp. Inform. Theory. Seattle, WA, 2006. P. 1614-1618.
Tokareva N. Bent Functions: Results and Applications to Cryptography. Acad. Press, Elsevier, 2015. 230 p.
Kumar P. V., Scholtz R. A., and Welch L. R. Generalized bent functions and their properties // J. Combin. Theory. 1985. V. 40. No. 1. P. 90-107.
Sole P. and Tokareva N. Connections Between Quaternary and Binary Bent Functions // Cryptology ePrint Archive, Report 2009/544. http://eprint.iacr.org/.
Sole P. and Tokareva N. On quaternary and binary bent functions // Прикладная дискретная математика. Приложение. 2009. №1. С. 16-18.
 Связь между кватернарными и компонентными булевыми бент-функциями | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/10

Связь между кватернарными и компонентными булевыми бент-функциями | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/10