On some properties of self-dual bent functions.pdf Булевой функцией f называется любое отображение f : Fn ^ F2. Скалярным про изведением (x,y} двух векторов x = (x1;x2,..., xn) G Fn,y = (yi,y2,..., yn) G Fn на- 2 2 > y = (У1> У2 > . . . > yn) G F 2 n зывается значение ф x^. Преобразованием Уолша - Адамара булевой функции f от i= 1 n переменных называется целочисленная функция Wf : Fn ^ Z, заданная равенством Wf(y) = (-1)f(x)®(x>y). Булева функция f от чётного числа переменных n назыxeF^ вается бент-функцией, если |Wf (y)| = 2n/2 для каждого y G Fn [1]. Для множества бент-функций от n переменных используется обозначение Bn. Булева функция f называется дуальной к бент-функции f, если Wf (x) = (-1)/(x)2n/2 для каждого x G Fn. Бент-функция f называется самодуальной (антисамодуальной), если f = f (соответственно f = f ф 1). Множества самодуальных и антисамодуальных бент-функций от n переменных обозначаются через SB+(n) и SB-(n) соответственно. Расстояние Хэмминга между булевыми функциями f, g от n переменных - число двоичных векторов длины n, на которых эти функции принимают различные значения, обозначается dist(f,g). Степенью булевой функции называется максимальная из степеней мономов, входящих с ненулевыми коэффициентами в её алгебраическую нормальную форму (АНФ, полином Жегалкина). Всюду далее предполагается, что n - чётное натуральное число. В [2] исследованы ограничения бент-функций на подпространства коразмерности 2 и их сдвиги и установлена связь между максимальной нелинейностью получаемых подфункций и второй производной дуальной функции. На основании данного результата была предложена итеративная конструкция бент-функций от n + 2 переменных из четырёх бент-функций f0,f1,f2, fз от n переменных: f (a,b,x) = fa+2b(x), где a,b G F2; x G Fn. Известно [3], что функция f является бент-функций от n + 2 переменных в том и только в том случае, когда f0(x) ф /1(x) ф f2(x) ф f3(x) = 1. Множество Исследование выполнено при финансовой поддержке РФФИ (проекты №18-07-01394, 18-3100374). бент-функций от 2k переменных, построенных с помощью данной конструкции, обозначается BI2к. Для множества самодуальных бент-функций из BI2k используется обозначение SB+X (2k). Открытой проблемой является полная характеризация и описание класса самодуальных бент-функций. Этому вопросу посвящены несколько работ за рубежом (C. Carlet, L. E. Danielson, M.G.Parker, P. Sole, X. Hou, T. Feulner, L. Sok, A. Wassermann и др.). В частности, в [4] перечислены все самодуальные бент-функции от 2, 4, 6 переменных и все квадратичные самодуальные бент-функции от 8 переменных. В [5] приведена классификация всех квадратичных самодуальных бент-функций. Аффинную классификацию квадратичных и кубических самодуальных бент-функций от 8 переменных относительно преобразования, сохраняющего самодуальность, можно найти в [6]. В [7] найден спектр расстояний Хэмминга между самодуальными бент-функциями из класса Мэйорана - МакФарланда. В данной работе найдены необходимые и достаточные условия самодуальности функций из класса BI. На основании данного результата предложена итеративная конструкция самодуальных бент-функций и получена оценка на количество самодуальных бент-функций из класса BI. Доказано, что существуют самодуальные бент-функции всех возможных для бент-функций степеней. Найдено минимальное расстояние Хэм-минга между самодуальными бент-функциями. Доказано, что множества самодуальных и антисамодуальных бент-функций являются метрически регулярными. Теорема 1. Пусть / G BIn+2. Тогда / является самодуальной бент-функций в том и только в том случае, когда существует такая пара функций g1,g2 G Bn и булева функция h от n переменных, что /(00, x) = (g1 e g2) h(x) e g1(x) = fl2(x), /(01, x) = (g1 e g2) h(x) e g2(x) = g^Th(x), /(10, x) = (g1 e g2) h(x) e g2(x) e h(x) = ^(x), /(11, x) = (g1 e g2) h(x) e g1(x) e h(x) e 1 = 92 e h(x) e 1. Можно показать, что функция h однозначно определяется парой функций g1,g2. Следствие 1. Бент-функции /1 (y1,y2, x) = (y1 e У2) (/(x) e/(x)) e /(x) e У1У2, /"2 (У1,У2, x) = (У1 e У2) (^(x) e ^(x)) e ^(x) e yi e У1У2, У1,У2 G F2, x G Fn, = 1, 2, где / G Bn, ^ G SB+(n), ш G SB-(n), являются самодуальными бент-функциями от n + 2 переменных. Заметим, что первая конструкция уже фигурировала в работе [4], но была получена другим способом - с помощью непрямой суммы бент-функций. Следствие 2. Справедлива следующая оценка на количество итеративных самодуальных бент-функций: |Bn-21 + |SB+(n - 2)|2 ^ |SB+X(n)| ^ |Bn-212. Множество SB+(2) содержит только две функции: x1 x2 и x1 x2 e 1. В утверждениях 1, 2, 3 предполагается, что n ^ 4. Утверждение 1. Для каждого d G {2, 3,... , n/2} существует самодуальная бент-функция от n переменных степени d. Утверждение 2. Для любых различных u,v G Fn найдётся пара самодуальных бент-функций f, g G SB+(n), такая, что f (u) ф f (v) ф g(u) ф g(v) = 1. Известно [8], что минимальное расстояние Хэмминга между бент-функциями равно 2n/2. Данное расстояние достижимо на множестве самодуальных бент-функций. Утверждение 3. Справедливо min dist(f,g) = 2n/2. f,geSB+(n),f=g Пусть A С Fn - произвольное множество, y G Fn - произвольный двоичный вектор. Расстояние от вектора y до множества A определяется как dist(y,A) = = mindist(y,x). Радиусом покрытия множества A называется d(A) = maxdist(y, A). x£A yEfrj Множество двоичных векторов, находящихся на расстоянии d(A) от множества A С Fn, называется метрическим дополнением [9] множества A и обозначается A. Если A = A, то множество A называется метрически регулярным. Следующая теорема описывает метрическое дополнение множества самодуальных бент-функций. Теорема 2. Пусть n ^ 4. Тогда - метрическим дополнением множества самодуальных бент-функций от n переменных является множество антисамодуальных бент-функций от n переменных; - метрическим дополнением множества антисамодуальных бент-функций от n переменных является множество самодуальных бент-функций от n переменных. Следствие 3. Множества самодуальных и антисамодуальных бент-функций являются метрически регулярными.

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

Облаухов А. К. О метрическом дополнении подпространств булева куба // Дискретный анализ и исследование операций. 2016. Т. 23. №3. С. 93-106.

Коломеец Н. А., Павлов А. В. Свойства бент-функций, находящихся на минимальном расстоянии друг от друга // Прикладная дискретная математика. 2009. №4(6). С. 5-20.

Hou X. Classification of self dual quadratic bent functions // Des. Codes Cryptogr. 2012. V. 63. P. 183-198.

Feulner T., SokL., Sole P., and Wassermann A. Towards the classification of self-dual bent functions in eight variables // Des. Codes Cryptogr. 2013. V. 68. P. 395-406.

Куценко А. В. Спектр расстояний Хэмминга между самодуальными бент-функциями из класса Мэйорана -МакФарланда // Дискретный анализ и исследование операций. 2018. Т. 25. №1. C. 98-119.

Carlet C., Danielson L. E., Parker M. G., and Sole P. Self dual bent functions // Int. J. Inform. Coding Theory. 2010. No. 1. P. 384-399.

Canteaut A. and Charpin P. Decomposing bent functions // IEEE Trans. Inf. Theory. 2003. V. 49. No. 8. P. 2004-2019.

Tokareva N. N On the number of bent functions from iterative constructions: lower bounds and hypotheses // Adv. Math. Commun. 2011. No. 4. P. 609-621.

Rothaus O. On bent functions // J. Combin. Theory. Ser.A. 1976. V.20. No.3. P. 300-305.