IV. Конструкция бент-функции

Итак, разберем преобразование Уолша-Адамара. Для начала определим экспоненту булевой функции f:

exp(f) = (-1)^f(x)

Очевидно, что при 0 экспонента принимает значение 1, а при 1 – значение (-1).

Определение. Преобразованием Уолша—Адамара булевой функции f от n переменных называется целочисленная функция W_f, заданная на множестве Zⁿ₂равенством

W_f(v) = S uÎZⁿ₂exp(<u,v>Åf(u))

В [5, глава 6, §6.5] и [6, глава 2, §2.3] описан алгоритм преобразования Уолша-Адамара 2-го рода:

1. Посчитать экспоненту булевой функции f.

2. Делим полученный вектор пополам.

3. Первую половину складываем со второй и записываем результат в первую половину нового столбца.

4. Из первой половины вычитаем вторую и записываем результат во вторую половину нового столбца.

5. Каждые половинки делим еще на две половины.

6. Повторяем шаги 3-5 до тех пор, пока каждый кусочек не будет состоять из одного элемента.

Таким образом, мы получили вектор после преобразования Уолша-Адамара 2-го рода. Теперь осталось только посчитать нелинейность.

Формула подсчета нелинейности имеет вид:

N(f) = 2^n-1 – ½ * max(|W_f (v)|),

где аÎV_n, W_f (v) – значения элементов вектора, полученного после преобразования Уолша-Адамара 2-го рода. Она взята из [1, стр.10] и [2, глава 2, §2.2].

Докажем эту формулу. Вес Хэмминга функции f выглядит так:

wt(f)=S xÎZⁿ₂f(x)=S xÎZⁿ₂(1 - exp(f))/2

Очевидно, что S xÎZⁿ₂ exp(f)=W_f(q). Тогда получаем wt(f)=2ⁿ⁻¹ − W_f(q)/2. Из этого следует:

wt(f(x)Å<a,x>)=2ⁿ⁻¹ −W_f(x)Å<a,x>(q)/2=2ⁿ⁻¹− W_f(a)/2.

Аффинная функция g может задаваться либо g(x)=<a,x>, либо g(x)=<a,x>Å1. Посчитаем расстояние между функциями f и g в обоих случаях. В первом случае:

dist(f,g)=wt(f(x)Å<a,x>)=2ⁿ⁻¹− W_f(a)/2.

Во втором случае:

dist(f,g)= wt(f(x)Å<a,x>Å1)=2ⁿ - wt(f(x)Å<a,x>)=2ⁿ⁻¹+ W_f(a)/2.

Таким образом, минимальное расстояние от f до множества аффинных функций равно 2^n-1 – ½ * max(|W_f (v)|). Формула доказана.

Разберем этот алгоритм на примере 1, у которого n=3. Для начала посчитаем экспоненту.

А теперь выполним преобразование Уолша-Адамара над полученным вектором.

Как видно, max(|W_f (a)|) = 4. Значит, нелинейность N(f) равна 2.

Для криптографических целей булева функция должна быть максимально нелинейной. Иначе говоря, она должна как можно меньше быть похожей на аффинную функцию.

Определение. Бент-функцией называется такая булева функция от n переменных (n четно), что модуль каждого коэффициента Уолша-Адамара этой функции равен 2^n/2. Коэффициенты Уолша-Адамара – это значения вектора, полученного после преобразования Уолша-Адамара 2-го рода.

Теорема (Мэйоран—МакФарланд). Пусть T: Z^n/2₂→ Z^n/2₂— любое взаимно однозначное отображение, h ∈ F^n/2 — произвольная функция. Тогда функция f ∈ Fⁿ такая, что f(u’,u’’) = <u’,T(u’’)> Å h(u’’) является бент-функцией. Здесь введены следующие обозначения: Z^n/2₂ – множество из n/2 аргументов, принимающие значения 0 и 1, Fⁿ – множество булевых функций, u’, u’’Î Z^n/2₂ .

Эту теорему осуществляет программа meyoran-mcfarland. Опишем, как она действует. Теорема взята из [3, глава 1, §1.2].

Сначала генерируется случайная перестановка. Этот процесс основан на алгоритме Фишера-Йетса. Он выглядит следующим образом:

1. Число i идет по порядку от 1 до n, где n – число переменных (четное).

2. Генерируется случайное число в интервале [1; i] (назовем его k).

3. Меняем местами числа на местах i и k в массиве per, где per – это массив, перед выполнением цикла имеющий вид: <1, 2, 3, …, n>

4. Повторяем шаги 2,3 до тех пор, пока i не будет больше n.

Алгоритм описан в [4].

Случайная перестановка нам нужна для того, чтобы построить взаимно однозначное отображение Т. То есть благодаря перестановке можно поменять местами все аргументы отображения и записать их в значения.

Чтобы вывести все возможные аргументы функции f от n переменных, нужно перевести по порядку все числа от 0 до 2ⁿ-1 из десятичной системы счисления в двоичную. Этот процесс осуществляет процедура conversion.

А для создания значений функции h применяется обыкновенная генерация нулей и единиц, происходящая 2^n/2 раз.

Далее действуем точно так же, как и сказано в условии теоремы. То есть сначала считаем скалярное произведение пары u’ и T(u’’), потом складываем полученное произведение и h(u’’) по модулю 2. Полученные значения являются значениями бент-функции f.

Разберем этот алгоритм на примере. Пусть n=4, тогда m=n/2=2. Допустим, что случайным образом сгенерировалась перестановка «2,4,3,1». С помощью этой перестановки меняем местами аргументы и записываем их в значения. То есть отображение Т получается следующим образом:

Пусть также случайным образом сгенерировались значения функции h в таком виде:

Далее действуем так, как сказано по условию теоремы. Возьмем, к примеру, аргумент функции f, равный 1011. Получается, что u’=10, u’’=11, T(u’’)=00, h(u’’)=0. Из этого следует, что

f(u’,u’’) = <u’,T(u’’)> Å h(u’’) = 1*0 Å 0*0 Å 0 = 0.

Таким образом, бент-функция f выглядит следующим образом:

V. Заключение

Методов конструирования бент-функций огромное количество: теорема Диллона, теоремы Ротхауса и многие другие. В данной работе был разобран один из этих методов – это теорема Мэйорана-МакФарланда.

Также были написаны на языке Pascal и протестированы программы, реализующие алгоритмы построения полинома Жегалкина, преобразования Уолша-Адамара 2-го рода и построения бент-функции на основании теоремы Мэйорана-МакФарланда. На компьютере автора работы все программы работают без проблем до 9 переменных включительно. Так, к примеру, функция, имеющая значения AB16DA3B061877353AD14BFC97DFE6F2705E0173DD50AC7DE19990B44C973DBA, является бент-функцией. Полином Жегалкина этой функции имеет вид: 1+X₈+X₆X₇X₈+X₅+X₅X₈+X₅X₇X₈+X₅X₆X₈+X₅X₆X₇+X₄X₈+X₄X₇+X₄X₇X₈+X₄X₆X₈+X₄X₆X₇+X₄X₅X₈+X₄X₅X₆+X₄X₅X₆X₈+X₄X₅X₆X₇+X₃+X₃X₈+X₃X₆X₈+X₃X₆X₇+X₃X₆X₇X₈+X₃X₅+X₃X₅X₈+X₃X₅X₆+X₃X₅X₆X₈+X₃X₅X₆X₇+X₂+X₂X₈+X₂X₇+X₂X₆+X₂X₆X₈+X₂X₆X₇+X₂X₆X₇X₈+X₂X₅X₈+X₂X₅X₆X₇+X₁+X₁X₇+X₁X₇X₈+X₁X₆X₈+X₁X₆X₇X₈. Степень этого полинома равна 4, а ее нелинейность равна 120.

Поиск по сайту: