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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 Вычислительное ядро алгоритма

Вычислительным ядром данного алгоритма является перебор всех возможных функций от заданного количества переменных, так как количество таких функций равно [math]2^{2^n}[/math]. Функции можно отождествить с их вектором значений, который в свою очередь можно перевести в число из двоичной системы в десятичную. Таким образом, генерация или перебор всех возможных булевых функций от [math]n[/math] переменных сводится к перебору всех возможных чисел в диапазоне от [math]0[/math] до [math]2^{2^n}[/math], не включая последнее значение.

1.4 Макроструктура алгоритма

Распределение функций на гиперсферу Евклидового пространства производится несколько этапов:

1. Генерация и перебор всех возможных булевых функций от заданного числа переменных.
2. Вычисление спектра Уолша для каждой функции по указанной ранее формуле.
3. На основе спектра Уолша создание вектора значений функции-номера секции.

1.5 Схема реализации последовательного алгоритма

В данном разделе представлена схема реализации последовательного алгоритма на языке Python.

1 этап Прямой перебор по порядку чисел в диапазоне [math][0, 2^{2^n}][/math].

2 этап Перевод числа в вектор значений функции:

  vv = bin(value)
  vv = vv[2:]
  vv = vv.rjust(2**n, '0')

3 этап Вычисление спектра Уолша (ws): (на данном этапе [math]scalar(x, y, n)[/math] - скалярное произведение векторов [math]x[/math] и [math]y[/math] в пространстве [math]V_n[/math])

  ws = [0] * (2**n)
  for u in range(0, 2**n):
     res = 0
     for x in range(0, 2**n):
        power = 0
        power += scalar(x, u, n)
        power += int(vv[x])
        power %= 2
        if power == 0:
           res += 1
        else:
           res += (-1)
     ws[u] = res

4 этап Вычисление вектора значений функции-номера секции на основе спектра Уолша:

  section_number = [0] * (2**n)
  for index in range(0, 2**n):
     if ws[index] > 0:
        section_number[index] = 0
     if ws[index] < 0:
        section_number[index] = 1

1.6 Последовательная сложность алгоритма

Обозначим через [math]w[/math] значение, равное [math]2^n[/math].

Тогда сложность вычисления коэффициента Уолша для определенной функции: [math]w[/math] вычислений скалярного произведения, затем суммирование полученных величин -> сложность: [math]w-1[/math]. Т.е. общая сложность равна [math]2w-1[/math].

Следовательно вычисление спектра Уолша зафиксированной функции имеет сложность: [math]w*(2w-1) = 2w^2-w[/math].

Всего нужно вычислить спектр Уолша для каждой функции, т.е. [math](2w^2-w)*2^w = O(w^2 * 2^w)[/math].

А генерация вектора значения функции-номера секции просто генерируется на основе значений спектра Уолша. Таким образом, общая сложность последовательной реализации алгоритма составляет [math]O(2^{2^n}*2^{2n})[/math]

3 Литература

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