О взаимосвязи между кватернарными и булевыми бент-функциями | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/22

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

Исследуются кватернарные бент-функции вида f : Zn ^ Z4. Показано представление коэффициентов Уолша - Адамара кватернарной функции через коэффициенты двух булевых функций. Получено, что любая кватернарная бент-функция является регулярной. Изучается связь кватернарных бент-функций от одной и двух переменных с булевыми бент-функциями от двух и четырёх переменных соответственно.

Connections between quaternary and boolean bent functions.pdf Пусть (x,y) -скалярное произведение векторов, где суммирование производится по модулю 2, а x.y - скалярное произведение векторов с суммированием по модулю 4. Преобразованием Уолша - Адамара булевой функции f от n переменных называется целочисленная функция W/ (х), заданная на множестве Zn равенством Wf(х) = £ (-i)(x>y)®/(y). yezn Булева функция f от n (n - чётное) переменных называется бент-функцией, если |Wf (х)| = 2n/2 для любого х Е Zn Функция g : Zn ^ Z4 называется кватернарной функцией от n переменных [1]. Преобразование Уолша - Адамара кватернарной функции g определяется следующим образом: Wg (х) = £ ix.y+g(y). yeZj Здесь «+» означает сложение по модулю 4. Кватернарная функция g от n переменных называется бент-функцией, если |Wg (х)| = 4n/2 для любого х Е Zn Пусть кватернарная функция g от n переменных задается для любых x,y Е Z^ следующим образом: g(x + 2У) = ^^ + 2b(x,y^ где сложение производится по модулю 4; а и b - булевы функции от 2n переменных. Лемма 1. Справедлива следующая связь коэффициентов Уолша - Адамара функций g, b и а Ф b: 1 21 Wg(x + 2y) = ^(W6(x Ф y,y) + W„eb(y,x) - 2c1 - 2d0 + +22(Wb(y,x) - W„®6(x Ф y,x) - 2c2 + 2^), где C1 = ^ (-1)b(x',y')®(x,y')®(y,x')®(x,x'>, C2 = ^ (-1)b(x',y')®(x,y')®(y,x'>, d1= £ (-1)b(x',y')®«(x',y' )®(x,y')®(y,x'>, d2= £ (-1)b(x',y')®a(x',y')®(x,y')®(y,x')®(x,x'>. x'eX1,y'ezn x' eX1,y'ezn Множество X1 состоит из всех таких x' Е Z^, для которых равенство (x,x') = x.x' не выполняется. Кватернарная бент-функция g : ZJ ^ Z4 называется регулярной [2], если каждый коэффициент Уолша - Адамара этой функции может быть представлен в виде Wg (x) = 4n/2ih(x), где h(x) -некоторая кватернарная функция. Теорема 1. Кватернарная бент-функция g : ZJ ^ Z4 является регулярной при любом n. Wg(x + 2y) = -(Wb(x Ф y,y) + W0®b(y,x)) ^(Wb(y,x) - W„®6(x Ф y,x)), Из леммы 1 следует, что для n = 1 1 i 2(Wb(x Ф y,y) + Wa®b(y,x)) + 2. так как множество X1 пусто для любого x. Утверждение 1. Пусть функция g(x + 2y) = a(x,y) + 2b(x,y), где x,y Е Z2; а и b - булевы функции от двух переменных, является бент-функцией. Тогда b и а Ф b - бент-функции. Обратное, вообще говоря, не верно. Так, функция g(x1+2x2) = x2+2x1x2 не является бент-функцией, но b(x1, x2) = x1x2 и a(x1, x2) Ф b(x1, x2) = x1x2 Ф x2 - бент-функции. Компьютерные вычисления показали, что количество кватернарных бент-функций от одной переменной равно 32. Чтобы получить каждую из них, достаточно взять в качестве функции b(x1, x2) любую из восьми булевых бент-функций от двух переменных и использовать одну из четырёх функций 0,1, x1 или x1 Ф1 в качестве функции a(x1, x2). Количество кватернарных бент-функций при n = 2 равно 200704. Среди них 98304 - таких, что ни одна из булевых функций a, b и аФ b не является бент-функцией, но при этом для 3072 из них а линейная. Существуют 36864 функции, таких, что b и а Ф b - бент-функции, при этом для 33792 из них функция а нелинейная, а для 2304 и 768 является линейной функцией и константой соответственно. Количество кватер-нарных функций, для которых каждая из функций а, b и а Ф b - бент-функция, равно 16384. Для оставшихся 49152 функций а является бент-функцией, а b и а Ф b - нелинейные булевы функции. Интересно, что среди всех кватернарных бент-функций нет ни одной, для которой b или а Ф b были бы линейными или константами.

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

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

Авторы

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

Ссылки

Kumar P. V., Scholtz R. A., and Welch L. R. Generalized bent functions and their properties // J. Combin. Theory. Ser.A40. 1985. P. 90-107.
Tokareva N. Bent Functions: Results and Applications to Cryptography. Acad. Press, 2015.
 О взаимосвязи между кватернарными и булевыми бент-функциями | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/22

О взаимосвязи между кватернарными и булевыми бент-функциями | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/22