Участник:One/Алгоритм распределения булевых функций на гиперсфере

Автор - Бартель Артем.

Одним из самых интересных свойств булевых функций, часто используемых в криптографии, является нелинейность. Для булевых функций, зависящих от четного количества переменных существует точная формула для подсчета нелинейности, а вот с функциями, зависящими от нечетного числа переменных такой формулы нет. Конечно же, существует общая формула вычисления нелинейности, но при достаточно больших [math]\displaystyle{ n }[/math] (количество переменных) ей практически невозможно пользоваться, так как она подразумевает перебор всех возможных векторов длины [math]\displaystyle{ n }[/math]. Именно поэтому хочется попытаться расширить используемый математический аппарат, чтобы получить более удобное решение поставленной проблемы. В данной статье будет рассматриваться метод распределения булевых функций на гиперсфере. На основе этого метода будут предприняты попытки нахождения закономерностей и связей между степенью нелинейности булевой функции и ее расположением на гиперсфере в евклидовом пространстве.

Свойства и структура алгоритма

Общее описание алгоритма

Объекты, с которыми работает данный алгоритм - булевы функции. Фактически, при задании [math]\displaystyle{ n }[/math] - количество переменных, от которых зависит функция - будет выполнен полный перебор всех возможных векторов длины [math]\displaystyle{ 2^{n} }[/math] (это вектора, которые соответствуют значениям, которые функция принимает на всевозможных лексико-графически упорядоченных наборах длины [math]\displaystyle{ n }[/math]), количество коих равно [math]\displaystyle{ 2^{2^{n}} }[/math]. Для каждого такого вектора будет подсчитана нужная характеристика - спектр Уолша, на основе которой будет составляться вектор так называемой функции-сектора, которая отвечает за то, в каком секторе гиперсферы находится исследуемая функция. На основе полученного распределения булевых функций на гиперсфере будут предприняты попытки нахождения зависимостей между функцией-сектором данной булевой функции и ее показателем нелинейности. Конечно же, особое внимание уделяется функциям, зависящим от нечетного числа переменных.

Математическое описание алгоритма

Через [math]\displaystyle{ V_{n} }[/math] обозначим множество всевозможных двоичных векторов длины [math]\displaystyle{ n }[/math]. Тогда отображение [math]\displaystyle{ f: V_{n} → V_{n} }[/math] - булева функция. Коэффициентом Уолша заданной функции на векторе [math]\displaystyle{ u }[/math] называется величина [math]\displaystyle{ W_{f}(u) }[/math], определяемая формулой:

[math]\displaystyle{ W_{f}(u) = Σ_{x\in V_{n}} (-1)^{f(x)+\lt u,x\gt } }[/math],

где [math]\displaystyle{ \lt u,x\gt }[/math] - скалярное произведение соответствующих векторов: [math]\displaystyle{ \lt u,x\gt = Σ_{i=1}^{n}x_{i}u_{i} }[/math], где [math]\displaystyle{ Σ }[/math] - сложение по модулю 2. Соответственно спектром Уолша данной функции называется вектор вида [math]\displaystyle{ (W_{f}(0^{n}), ..., W_{f}(1^{n})) }[/math].

На основе данного вектора составляется вектор значений функции-сектора [math]\displaystyle{ g(x) }[/math] по правилу:

[math]\displaystyle{ W_{f}(x)\gt 0 → g(x) = 0; W_{f}(x)\lt 0 → g(x) = 1 }[/math]

Таким образом, мы получаем вектор значений функции, которая 'нумерует' определенную секцию гиперсферы. Легко видеть, что для булевых функций, у которых существует хотя бы один нулевой коэффициент Уолша, невозможно точно и однозначно определить секцию, в которой они лежат, то есть они находятся на стыке двух секторов. В дальнейшем будут исследоваться свойства полученных функций-секторов и их взаимосвязь с исходными булевыми функциями.

Литература

1. ↑ О.А. Логачев, С.Н. Федоров, В.В. Ященко. Булевы функции как точки гиперсферы в евклидовом пространстве // Общероссийский математический портал Math-Net.ru. 2018, том 30, выпуск 1, стр. 39-55
2. ↑ О.А. Логачев, А.А. Сальников, С.В. Смышляев, В.В. Ященко. Булевы функции в теории кодирования и криптологии. 2012.
3. ↑ Tomas Cusick, Pantelimon Stanica. Cryptographic Boolean Functions and Applications. 2009.