An affine property of boolean functions on subspaces and their shifts.pdf Рассматривается свойство булевых функций, связанное с их аффинностью на аффинных подпространствах. Введём необходимые определения. Отображение f : Z^ ^ Z2 называется булевой функцией от n переменных. Алгебраической степенью или просто степенью булевой функции называется степень её алгебраической нормальной формы (полинома Же-галкина). Булева функция называется аффинной, если её алгебраическая степень не больше 1, и квадратичной, если её степень равна 2. Множество U С Z^ называется аффинным подпространством, если U = a ф L, где a Е Z^ и L является линейным подпространством в Z^. Будем называть U сдвигом подпространства L. Через Ind^ обозначим характеристическую функцию множества D С Z^. Через (u,v) обозначим скалярное произведение векторов u и v. Булева функция f от n переменных аффинна на множестве D С Z^, если существуют a Е Z^, c Е Z2, такие, что для любого x Е D верно f (x) = (a, x) ф c. Под расстоянием между двумя булевыми функциями подразумевается расстояние Хэмминга между их векторами значений. Все квадратичные булевы функции обладают следующим свойством. Утверждение 1. Пусть f — квадратичная булева функция от n переменных. Тогда для любого аффинного подпространства L функция f аффинна на L, если и только если f аффинна на любом сдвиге L. Доказательство утверждения следует из неравенства deg(f (x) ф f (x ф s)) ^ 1, верного для любого s Е Z^. Исследование выполнено при поддержке РФФИ (проект №12-01-31097). Отметим, что не для всех квадратичных функций существует хотя бы одно аффинное подпространство размерности больше чем [n/2], на котором функция аффинна. Например, если f является бент-функцией (n чётно), то не существует подпространств размерности n/2 + 1, на которых f аффинна. Бент-функция — это булева функция от чётного числа переменных, максимально удаленная от множества всех аффинных функций. Понятие бент-функций ввел О. Ротхаус [1]. Бент-функции представляют интерес в криптографии и теории кодирования, поскольку имеют в этих областях множество различных приложений. Тем не менее до сих пор существует большое количество нерешённых проблем, связанных с бент-функциями [2]. Внесём ограничение на размерность подпространств в условие утверждения 1. Утверждение 2. Пусть f — квадратичная булева функция от n переменных. Тогда для любого аффинного подпространства L размерности [n/2] функция f аффинна на L, если и только если f аффинна на любом сдвиге L. Если f является бент-функцией, то по подпространствам размерности n/2, на которых она аффинна, можно строить другие бент-функции. Утверждение 3 [3]. Пусть f — бент-функция от 2 k переменных и L С Z^k, |L| = 2k. Тогда f (x) ф IndL(x) является бент-функцией тогда и только тогда, когда L является аффинным подпространством и f на нём аффинна. Таким образом, существует взаимно однозначное соответствие между бент-функциями на расстоянии 2k от f и аффинными подпространствами, на которых f аффинна. Следующая теорема показывает, для каких функций, помимо квадратичных, справедливо утверждение 2. Теорема 1. Пусть f — булева функция от n переменных и для любого аффинного подпространства L размерности [n/2] функция f аффинна на L, если и только если f аффинна на любом сдвиге L. Тогда либо deg f ^ 2, либо не существует ни одного аффинного подпространства размерности [n/2], на котором функция f аффинна.

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