О разложении дуальной бент-функции в сумму двух бент-функций | ПДМ. 2014. № 4(26).

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

Установлено, что бент-функции и функции, дуальные к ним, разложимы или не разложимы в сумму двух бент-функций одновременно.

On decomposition of a dual bent function into sum of two bent functions.pdf Введение Бент-функции - булевы функции с экстремальными нелинейными свойствами - интенсивно исследуются в связи с многими приложениями в криптографии, теории кодирования, дискретной математике [1]. Одним из нерешённых вопросов этой области остаётся вопрос об оценках числа таких функций. В работе [2] предложен новый подход к этой проблеме и выдвинута гипотеза: произвольная булева функция от n переменных степени ^ n/2 может быть представлена в виде суммы двух бент-функций от n переменных (n чётно, n ^ 2). При малых n = 2, 4, 6 гипотеза проверена в [2], при n = 8 доказано [3], что каждая функция степени не выше трёх представима в виде суммы не более четырех бент-функций. Для произвольного n доказан [4] ослабленный вариант гипотезы. Авторы [5] доказали, что в виде суммы двух бент-функций может быть представлена любая квадратичная булева функция, любая бент-функция Мак-Фарланда, произвольная функция частичного расщепления. В работе [6] отмечается связь гипотезы с открытыми вопросами о метрических свойствах класса бент-функций. В данной работе продолжено исследование разложимости произвольной булевой функции от чётного числа переменных в сумму двух бент-функций. Доказано, что бент-функции и функции, дуальные к ним, разложимы или не разложимы в сумму двух бент-функций одновременно. 1. Основные определения Пусть x = (xi,... ,xn) - двоичный вектор. Вектор x предшествует вектору y, если для всех i = 1,...,n выполняется xi ^ yi. Будем обозначать предшествование так: x y. Через wt(x) обозначим вес вектора x, т.е. число его ненулевых координат. Напомним, что произвольная булева функция f от n переменных однозначно представляется с помощью алгебраической нормальной формы (АНФ): f (x) = Е fy xi1 ■ ... ■ x«", где fy = E f (z). (1) У z^y Здесь и далее под знаком суммы мы опускаем области значений векторов y, z, предполагая, что каждый вектор принимает все значения из множества Z^, возможно, с некоторыми ограничениями, как во втором случае: все такие z, что z y. Степенью булевой функции называется число множителей в самом длинном слагаемом, присутствующем в её АНФ. Преобразованием Уолша - Адамара булевой функции f от n переменных называется целочисленная функция Wf, заданная на множестве Z^ равенством Wf (у) = £(-1)y>®f (x), x где (x, у) = xiyi 0 ... 0 x„y„. Булева функция f от чётного числа переменных n называется бент-функцией, если Wf (x) = ±2n/2 для любого вектора x. Дуальной функцией к бент-функции f называется булева функция f от n переменных, определяющая знаки коэффициентов Уолша - Адамара функции f, т.е. f для каждого x определяется равенством Wf (x) = (-1)f(x) 2n/2. Несложно показать, что дуальная функция - всегда бент-функция, более того, f = f. Согласно [1], выполняется Утверждение 1. Степень бент-функции от n ^ 4 переменных не превышает n/2. Известен следующий факт [7, лемма 5.17]: Утверждение 2. Пусть f - бент-функция от n переменных, n ^ 4. Тогда Е f (x) = 2wt(y)-1 - 2n/2-1 + 2wt(y)-n/2 £ f(x). x^y x^y®1 Бент-функции и функции, дуальные к ним, нередко исследуются вместе. Так, в работе [8] получен ряд результатов, направленных на характеризацию самодуальных бент-функций, т. е. таких, что f = f .За исключением самодуальных функций, весь класс бент-функций разбивается на пары функций, связанных отношением дуальности. Интересно, что бент-функции из одной такой пары не обязательно имеют похожие свойства. Например, дуальные функции к бент-функциям Касами не являются мономиальными [9], а возможно (но пока это не доказано), и не эквивалентны им. Поэтому, если удаётся исследовать какое-либо свойство одновременно для бент-функций и функций, дуальных к ним, то «пространство исследования» сокращается в 2 раза (за исключением самодуальных функций). Далее покажем, что таким свойством как раз является разложимость функции в сумму двух бент-функций. 2. Разложение дуальных бент-функций Теорема 1. Бент-функция от n переменных, n ^ 4, разложима в сумму двух бент-функций от n переменных тогда и только тогда, когда таким свойством обладает дуальная к ней бент-функция. Доказательство. Пусть g - бент-функция от n переменных, такая, что g = f 0h, где f, h - бент-функции. Тогда для каждого ненулевого коэффициента gy АНФ функции g справедливо представление gy = fy 0 hy, где у - произвольный вектор. Можем рассматривать лишь векторы веса не больше n/2, т.е. wt(y) ^ n/2, поскольку в соответствии с утверждением 1 все коэффициенты gy, fy, hy равны нулю, если wt(y) > n/2. Согласно представлению (1), имеем gy = Е g(x) =( Е f (x)) 0( Е h(x) x^y \x^y / \x^y Используя равенство a ф b = a + b - 2ab, можем перейти в правой части к знакам обычного сложения и вычитания. По утверждению 2 выполняется равенство Е g(x) = 2wt(y)-1 - 2n/2-1 + 2wt(y)-n/2 E g(x). x^y x^y®1 Используя его и аналогичные равенства для функций f, h, получаем 2wt(y)-n/2 f Е g(x) - Е f(x) - Е h(x^ = 2wt(y)-1 - 2n/2-1 - 2fyhy. \x^y x^y x^y / Домножим равенство на 2n/2 wt(y). Тогда Е g(x) - Е f(x) - Е h(x) = 2n/2-1 - 2n-wt(y)-1 - 2n/2-wt(y)+1fyhy. x^y x^y x^y Заметим, что выражение в правой части чётное, поскольку wt(y) ^ n/2 и n ^ 4. Поэтому, рассматривая равенство по модулю два, получаем Е g(x) = Е f(x) ф Е h(x), x^y x^y x^y т. е. gy = fy ф hy для произвольного вектора y веса ^ n/2. Напомним, что для векторов большего веса это равенство автоматически выполняется. Таким образом, g = f ф h. Очевидно, что в обратную сторону теорема доказывается аналогично. ■ Следствие 1. Пусть g, f, h - бент-функции от n переменных, n ^ 4. Тогда если g ф f ф h = 0, то справедливо g ф f ф h = 0. Следствие 1 говорит о том, что, зная разложение бент-функции в сумму двух других, можно простым способом перейти к разложению дуальной бент-функции. Следствие 2. Число различных разложений бент-функции g в сумму двух бент-функций равно числу аналогичных разложений дуальной бент-функции g.

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

бент-функция, дуальная функция, bent function, dual function

Авторы

ФИООрганизацияДополнительноE-mail
Токарева Наталья НиколаевнаИнститут математики им. С. Л. Соболева, г. Новосибирсккандидат физико-математических наук, старший научный сотрудникtokareva@math.nsc.ru
Всего: 1

Ссылки

Rothaus O. On bent functions // J. Combin. Theory. Ser.A. 1976. V.20. No.3. P. 300-305.
Tokareva N. N. On the number of bent functions from iterative constructions: lower bounds and hypotheses // Adv. Math. Comm. 2011. V. 5. No. 4. P. 609-621.
Tokareva N. N. Every cubic Boolean function in 8 variables is the sum of not more than 4 bent functions // Прикладная дискретная математика. Приложение. 2014. №7. С. 38-39.
Токарева Н. Н. О разложении булевой функции в сумму бент-функций // Прикладная дискретная математика. Приложение. 2012. №5. С. 30.
Qu L. and Li C. When a Boolean function can be expressed as the sum of two bent functions // Cryptology ePrint Archive. 2014/048.
Коломеец Н.А. Верхняя оценка числа бент-функций на расстоянии 2k от произвольной бент-функции от 2k переменных // Прикладная дискретная математика. 2014. №3. С.28-39.
Cusick T. W. and Stanica P. Cryptographic Boolean Functions and Applications. San Diego: Acad. Press, 2009. 245 p.
Carlet C., Danielsen L.-E., Parker M. G., and Sole P. Self-dual bent functions // Int. J. Inform. and Coding Theory. 2010. V. 1. No. 4. P. 384-399.
Langevin Ph. and Leander G. Monomial bent functions and Stickelberger's theorem // Finite Fields and Their Applications. 2008. V. 14. No. 3. P. 727-742.
 О разложении дуальной бент-функции в сумму двух бент-функций | ПДМ. 2014. № 4(26).

О разложении дуальной бент-функции в сумму двух бент-функций | ПДМ. 2014. № 4(26).