Properties of bent functions constructed by a given bent function using subspaces.pdf Данная работа является продолжением исследований, начатых в [1]. Центральный объект исследований - бент-функции [2]. Это булевы функции от чётного числа переменных, обладающие максимальной возможной нелинейностью. В первую очередь они представляют интерес для криптографии. Подробную информацию об этом классе булевых функций можно найти в [3, 4]. Введём необходимые обозначения. Отображение вида / : Fn - F2 называется булевой функцией от n переменных. Пусть (ж,у) = ж1у1 ф ... ф жпуп, где ж, у Е Fn. Обозначим через Inds характеристическую булеву функцию множества S С Fn и через B2k - множество всех бент-функций от 2k переменных. Для любой бент-функции / Е B2k существует дуальная к ней бент-функция / Е B2k, определяемая знаками коэффициентов Уолша - Адамара функции /. Как и в [1], в работе исследуются свойства конструкции бент-функций / ф IndL, где / Е B2k и L С F^ - аффинное подпространство. (1) К. Карле [5] доказал критерий принадлежности / ф Ind^ множеству бент-функций B2k. Обозначим через C(/, m), где / Е B2k, множество всех бент-функций, порождаемых конструкцией (1) по функции / с помощью аффинных подпространств размерности m. Рассмотрим, как связаны мощности C(/, m) и C(/, m). Во-первых, отметим, что при m < k конструкция не может порождать бент-функции. Во-вторых, размерности m = 2k и 2k - 1 являются тривиальными, так как для подпространств таких размерностей конструкция порождает бент-функции при любой заданной начальной бент-функции, т. е. |C(/, m)| = |C(/,m)| при m Е {0,..., k - 1, 2k - 1, 2k}. Таким образом, нетривиальными размерностями можно считать m Е {k,... , 2k - 2}. Из [5] известно взаимно-однозначное соответствие между функциями из C(/, k) и C(/,k), таким образом, |C(/, k)| = |C(/,k)|. Оказывается, аналогичное утверждение справедливо и для m = k + 1. Теорема 1. Пусть / Е ^. Тогда |C(/, k + 1)| = |C(/, k + 1)|. Приведём экспериментальные результаты с учётом известной аффинной классификации бент-функций. В табл. 1-4 для функции / указаны |C(/, m)| и |C(/,m)| при m Е {k, • • • , 2k - 2} (или одно число, если эти мощности совпадают). Для всех бент-функций из B6 количество функций в C(-,m) совпадает с |C(/,m)| для некоторой / из табл. 1. Для всех бент-функций из Bg степени не выше 3 количество функций в C(-,m) совпадает с |C(/,m)| для некоторой / из табл.2. Начиная уже с 8 переменных, в C(/, m) может не быть функций даже в нетривиальных случаях. Хорошо иллюстрируют это свойство мономиальные функции с показателем Касами (табл. 3). Отметим, что для всех приведённых в табл. 1-3 функций f Е B2fc и всех m справедливо |C(f,m)| = |C(/,m)|. Напомним, что [5] и теорема 1 гарантируют это только при m = k и m = k + 1. Более того, в классе бент-функций Мэйорана - МакФарланда [6], начиная уже с 8 переменных, есть функции c |C (f, 6)| = |C (/, 6)| (табл.4). Таблица 1 № п/п Функция f (6 переменных) 3 4 1 Ж1Ж2 ф Х3Х4 ф Х5Х6 1080 1260 2 Х1Х2Х3 ф Х1Х4 ф Х2Х5 ф Х3Х6 568 364 3 Х1Х2Х3 ф Х2Х4Х5 ф Х1Х2 ф Х1Х4 ф Х2Х6 ф Х3Х5 ф Х4Х5 440 140 4 Х1Х2Х3 ф Х2Х4Х5 ф Х3Х4Х6 ф Х1Х4 ф Х2Х6 ф ХзХ4 ф Х3Х5 ф Х3Х6 ф Х4Х5 ф Х4Х6 376 28 Таблица 2 № п/п Функция f (8 переменных) 4 5 6 1 Х1Х2 ф Х3Х4 ф Х5Х6 ф Х7Х8 36720 91800 21420 2 Х1Х2Х3 ф Х1Х4 ф Х2Х5 ф Х3Х6 ф Х7Х8 12144 16024 7084 3 Х1Х2Х3 ф Х2Х4Х5 ф Х1Х7 ф Х2Х6 ф Х3Х4 ф Х5Х8 6000 5272 3500 4 Х1Х2Х3 ф Х2Х4Х5 ф Х1Х3 ф Х1Х5 ф Х2Х6 ф Х3Х4 ф Х7Х8 6000 4760 3500 5 Х1Х2Х7 ф Х3Х4Х7 ф Х5Х6Х7 ф Х1Х4 ф Х2Х5 ф Х3Х6 ф Х4Х5 ф Х7Х8 4464 3096 2604 6 Х1Х2Х3 ф Х2Х4Х5 ф Х3Х4Х6 ф Х1Х6 ф Х2Х7 ф Х3Х5 ф Х4Х8 2928 1944 1708 7 Х1Х2Х3 ф Х2Х4Х5 ф Х3Х4Х6 ф Х1Х7 ф Х2Х5 ф Х2Х6 ф Х3Х5 ф Х4Х8 2928 1432 1708 8 Х1Х2Х3 ф Х2Х4Х5 ф Х3Х4Х6 ф Х1Х3 ф Х1Х4 ф Х2Х7 ф Х3Х5 ф Х6Х8 2928 1432 1708 9 Х1Х2Х3 ф Х2Х4Х5 ф Х3Х4Х6 ф Х1Х2 ф Х1Х3 ф Х1Х4 ф Х2Х5 ф Х2Х6 ф ф Х3Х5 ф Х7Х8 2928 1048 1708 10 Х1Х2Х3 фХ1Х4 Х7 фХ2Х4Х5 фХ3 Х4Х6 фХ1Х5 фХ1 Х6 фХ2Х7 фХ3Х5 фХ4Х8 1392 792 812 Таблица 3 Функция f (8 переменных) 4 5 6 1г(«Х57), х Е F28, a - порождающий элемент F2S 493 0 0 Таблица 4 Функция f (8 переменных) 4 5 6 (Х,П1(у)) ф 1(y), где Х,у Е F2 и п1 = (9,10, 4, 3, 5, 7,11,13,12,14, 2,15,1, 6, 8,0), ¥>1(y) = У1У2У3фУ1У3У4 фУ2У3У4 фУ1У3фУ2У3 фУ2У4 фУ1 фУ3 фУ4 ф1 1392 408 300/236 Усилим теорему 3 из [1]. Пусть S С F^2 и S = {x Е F2k : (x, a, b) Е S для некоторых a, b Е F2}, F020k = {(x, 0, 0) : x Е F2k}. Теорема 2. Пусть для g(xi,... , x2fc+2) = f (xi,... , x2fc) ф x2fc+ix2fc+2 Е 02fc+2 верно g ф Indaffiu Е B2fc+2, где U С F;f+2 - линейное подпространство и a Е F2k+2. Тогда существует линейное подпространство L С F2k, такое, что f ф Indb®L Е B2k для некоторого b Е F2k, причём U П F00 С L С U и dim L < dim U. Теорема 2 отличается от теоремы из [1] соотношением U П F020k С L С U.

Скачать электронную версию публикации