СВОЙСТВА БЕНТ-ФУНКЦИЙ, НАХОДЯЩИХСЯ НА МИНИМАЛЬНОМ РАССТОЯНИИ ДРУГ ОТ ДРУГА | ПДМ. 2009. № 4(6).

СВОЙСТВА БЕНТ-ФУНКЦИЙ, НАХОДЯЩИХСЯ НА МИНИМАЛЬНОМ РАССТОЯНИИ ДРУГ ОТ ДРУГА

В работе получено минимальное расстояние Хэмминга в классе бент-функций от п переменных, равное 2/. Доказано, что бент-функции находятся на минимальном расстоянии тогда и только тогда, когда они различаются на линейном многообразии и обе функции на нем аффинны. Описан алгоритм построения всех бент-функций на минимальном расстоянии от заданной бент-функции. Приведены экспериментальные данные для бент-функций от малого числа переменных.

PROPERTIES OF BENT FUNCTIONS WITH MINIMAL DISTANCE .pdf Данная работа посвящена исследованию метрических характеристик класса бент-функций. Бент-функции - это булевы функции от четного числа переменных, максимально удаленные от класса аффинных функций. Впервые бент-функции были введены еще в 60-х годах XX века О. Ротхаузом, и до сих пор интерес к ним не ослабевает. Причиной этого служат как многочисленные теоретические и практические приложения, так и множество открытых вопросов, с ними связанных (см. подробнее в [1]).Задача исследования метрических свойств бент-функций возникает в теории кодирования и находит свое применение в системах коллективного доступа [2], таких, как стандарты CDMA - Code Division Multiple Access (множественный доступ с кодовым разделением каналов) и OFDM - Orthogonal Frequency Division Multiplexing (ортогональное частотное мультиплексирование). Данные стандарты используют бент-функции для построения кодов постоянной амплитуды (constant-amplitude codes), что позволяет предельно снизить коэффициент отношения пиковой и средней мощностей сигнала (PARP - peak-to-average power ratio). Такие коды состоят из векторов значений бент-функций. Таким образом, являются актуальными задачи построения таких кодов с различными кодовыми расстояниями, что непосредственно связано с исследованием метрической структуры класса бент-функций.Данная работа имеет следующую структуру. В п. 1 показывается, что минимальное расстояние в классе бент-функций равно 2п/2, и бент-функции, находящиеся на этом расстоянии друг от друга, должны отличаться на линейном многообразии, причем обе функции должны быть на нем аффинны. Заметим, что этим результатам1 Работа выполнена при финансовой поддержке гранта Президента РФ для молодых российских ученых (грант МК-1250.2009.1) и РФФИ (проект № 08-01-00671).бН. А. Коломеец, А. В. Павловпредшествовали исследования В. В. Ященко [3] и К. Карле [4] построения различных бент-функций по заданной бент-функции. В п. 2 предлагаются простые способы построения бент-функций на минимальном расстоянии от заданной бент-функции. В п. 3 приводятся примеры бент-функций, для которых существуют бент-функции на минимальном расстоянии. В п. 4 используется аффинная классификация бент-функций для исследования существования бент-функций на минимальном расстоянии для бент-функций от малого количества переменных. В п. 5 приводятся алгоритм построения всех бент-функций на минимальном расстоянии от заданной бент-функции, а также экспериментальные данные для бент-функций от малого числа переменных.Приведем известные определения и факты, имеющие отношения к бент-функциям.Под расстоянием между булевыми функциями fug мы подразумеваем расстояние Хэмминга, обозначим его как dist(f, g). Через Еп будем обозначать n-мерный куб, через Fп - множество булевых функций от п переменных.Определение 1. Множество L С Еп называется линейным многообразием в Еп, если L = Хо ф U, где ж0 -элемент из Еп, a U - подпространство в Еп.Определение 2. Преобразование Wf : Еп -> Z следующего вида называется преобразованием Уолша - Адамара функции /:Wfiw) = E (-l)'^®^.хеЕпЧисло Wf(w) называется коэффициентом Уолша - Адамара в точке w (или просто коэффициентом Уолша).Известно, что две различные функции не могут иметь одинаковые коэффициентыУолша. Также справедливо равенство Парсеваля: пусть / Е Тп. Тогда имеет местоследующее равенство:£ W]{w) = 22п. и>еЕпИмеет место формула свертки: пусть f,gЈ ТП1 тогдаWm{w) = ± EWf(x)W9(x®w). z xeEnОпределение 3 (альтернативное определение бент-функций). Булева функция / от четного числа переменных называется бент-функцией, если все ее коэффициенты Уолша равны ±2га/2.Класс бент-функций от п переменных будем обозначать как 53п, а минимальное расстояние между функциями из него - как d(53n).Определение 4. Пусть / - бент-функция от п переменных. Определим дуальную функцию f(w), исходя из равенства(-1)^) .T/2 = Wf{w).Стоит заметить, что дуальная к бент-функции функция также является бент-функцией.Так как расстояние Хэмминга берется между бент-функциями, то здесь и далее будем считать, что п (так будет обозначаться количество переменных функции) является четным натуральным числом.Бент-функции на минимальном расстоянии71. Критерий расположения бент-функций на минимальном расстоянииПолучим минимальное расстояние между бент-функциями и описание всех бент-функций на минимальном расстоянии от заданной бент-функции.Обозначим через D(f,g) множество значений аргументов, на которых функции / и д от п переменных отличаются. Будем говорить, что D(f,g) -это множество разногласий функций fag. Заметим, что \D(f,g)\ = dist(f,g). Через Id(x) мы будем обозначать индикатор множества D, то есть булеву функцию, которая принимает значение 1 на всех элементах из D, и только на них. Через rank D обозначим размерность линейной оболочки векторов из D.Определение 5. Булева функция f от п переменных аффинна на множестве D С Еп, если для некоторых Wq Е Еп, с Е Е и для любого х Е D выполняется тождество f(x) = (w0,x) ф с.Для удобства введем следующее обозначение:xeD(f,g)Утверждение 1. Для любого w E Еп справедливо |a/;fl(u>)| ^ \D(f,g)\, причем равенство достигается тогда и только тогда, когда функция f(x) ф {w,x) является константой на D(f,g).Утверждение 2. Пусть f,gE Tn. Тогда для любого w из Еп выполняетсяWf(w)-Wg(w) = 2af,g(w).Доказательство. Запишем коэффициенты Уолша функций fug следующим образом:Wf{w) = Е (-1)/(ж)®^'^ + Е (-l)f(x)®(w>x)}xeD(f,g)xeE"\D(f,g)xeD(f,g)xeE"\D(f,g)Отсюда разность этих коэффициентов равнаWf{w) - Wg(w) = Т,хеОШ (-l)f^{w'x) - Т,хевш (-1)й(ж)фg(w) для любого w из Еп. Так как fug - бент-функции, то все их коэффициенты Уолша - Адамара по модулю равны 2п = w%g(o).z хеЕпхеЕпОсталось заметить, чтоWm9(0) = 2n-2\D(f,g)\,откуда и следует утверждение леммы. ■Следствие 1. Пусть f,gE 53n. Тогда dist(/, д) = а1, если и только если существует ровно d векторов w Е Еп, таких, что Wf(w) ф Wg(w).Лемма 3. Пусть D С Еп, \D\ = 2k, rankL* = k + 1 и для любых х,у Е D выполняется х ф у ^ D. Тогда D - линейное многообразие.Доказательство. Пусть (D)-линейная оболочка D, U = (D)\D, Xo G D. Покаж;ем, что U = Xq ф D. Очевидно включение Xq ф D С U. Также верно\U\ = |(£>)| - \D\ = 2k+l - 2fc = 2fc = |Ј>| = |ж0 Ф D\.Следовательно, U = Хо ф D.Теперь покаж;ем, что U - подпространство Еп. Множ;ество U непусто, следовательно, достаточно показать только его замкнутость относительно ф.Пусть х,у Е U, тогда х = Хо ф х',у = Хо ф у',х',у' Е D. Имеемх Ф у = (х0 Ф х') Ф (ж0 Ф у') = х'@у' eU,так как по условию леммы для любых х' ,у' Е D справедливо х' ®у' Е U.Таким образом, U - подпространство Еп. И следовательно, D - линейное многообразие. ■Лемма 4. Любая аффинная функция, заданная на линейном многообразии и не являющаяся константой, уравновешена (принимает значения 1 и 0 одинаковое количество раз).Доказательство. Пусть / - аффинная функция, заданная на линейном многообразии [/, и / - не константа. По определению линейного многообразия U = Xq®L для некоторого подпространства L и вектора xq. Рассмотрим функцию f'(x) = f(x®Xo) Ф ф/(жо), определенную на подпространстве L. Очевидно, что /' линейна на L. Также легко понять, что / уравновешена на U тогда и только тогда, когда /' уравновешена на L (сдвиг множества является взаимнооднозначным отображением, а прибавление к функции константы сохраняет свойство уравновешенности), поэтому нам достаточно доказать утверждение леммы для функции /'.Рассмотрим множества Lq = {х Е L | f'(x) = 0} и L\ = {х Е L | f'(x) = 1}. Покажем, что множества Lo и L\ равномощны.Функция /' - не константа на L, так как / - не константа на U. Поэтому выберем элемент у0 из L\. Тогда для любого х Е L0f'(x фуо) = f'(x) Ф /'Ы = 0 0 1 = 1.Бент-функции на минимальном расстоянии9Значит, уо 0 Lo С Li. Отсюда |Lo| ^ |bi| в силу взаимнооднозначности сдвига множе-ства на у0. Но для любого у G L\f(y®yo) = f(y)®f(yo) = l®l = 0.Следовательно, у0®Ь\ С L0 и |Li| ^ |£о|- Таким образом, |L0| = \Li\. А это и означает уравновешенность функции /'. ■Следующая теорема дает необходимые и достаточные условия принадлежности функции на расстоянии 2п (t0,x®y) = 0,с другой стороны, {to,x ф у) = 1. Следовательно, выполняется условие леммы 3 для множества D(f,g). Таким образом, D(f,g)-линейное многообразие. Необходимость доказана.Достаточность. Пусть D(f,g)-линейное многообразие и / аффинна на D(f,g). Для начала покажем, чтоа/;»е{0,2га/2,-2га/2}.Так как / аффинна на D(f, g), то функция hw(x) = f(x)(B(w, x) будет также аффинной на D(f,g). Если hw(x) не является константой на D(f,g), то по лемме 4 функция hw уравновешена на D(f,g). ПоэтомуЯ/,аМ= Е (-1)Мх) = 0.xeD(f,g)Если же hw(x) -константа на D(f,g), то \af>g(w)\ = \D(f,g)\ = 2га/2 по утверждению 1. Следовательно, afyg{w) E {0, 2га/2,-2га/2}. Осталось доказать, что д Е 53п. ИмеемWg(w) = Wf(w) - 2af>g(w).Следовательно,Wg{w) Е {2п/2, -2п/2, 3 2п/2, -3 2п/2}.Отсюдаmin\W9(w)\^2n/2,поэтому из равенства Парсеваля следует, что |Wfl(w)| = 2п>2 для любого w. Получаем, что д Е 53п. Достаточность доказана. ■Следствие 2 (минимальное расстояние в классе 53п). Справедливо d(53n) = 2nl2'.Доказательство. Как известно, j{x) = Х\Х2 Ф Ф хп-\хп является бент-функцией. ПустьD = {(yi,0,--- ,yn/2,0)\ угеЕ};очевидно, чтоD С Еп,I Г)\ - 9га/2 Ух Е D f(x) = 0.Бент-функции на минимальном расстоянии11Пусть д{х) = f{x) ф Id(x). Понятно, что D(f,g) = D. Тогда по теореме 1 д Е 23га, т.е. f,gE 23ri, dist(/,д) = 2га/2. А из леммы 1 мы знаем, что d(53n) ^ 2га/2. Следовательно, d(«8ra) = 2га/2. ■Пусть Lan(/)-всевозможные линейные многообразия размерности тг/2, на которых / аффинна. Теперь можно более компактно описать бент-функции на минимальном расстоянии от заданной бент-функции.Следствие 3 (общий вид функций на минимальном расстоянии). Пусть / Е *Зп. Тогда существует д Е *Зп на минимальном расстоянии от /, если и только если множество Lan(/) непусто, причем д(х) = f{x) ф IL(x), где L Е £ац(/).Следствие 4. Бент-функция от п переменных не может быть аффинна на линейных многообразиях размерности больше чем п/2.Доказательство. Предположим, что для бент-функции / и линейного многообразия L утверждение неверно. Введем д{х) = f(x)(Blb(x) и hw{x) = f(x)(B(w, x). Далее приводим рассуждения, аналогичные доказательству достаточности теоремы 1: так как / аффинна на L, то и hw аффинна на L. Если размерность D(f, g) больше чем п/2, то для всех элементов w, таких, что hw константа (т.е. aft9(w) ф 0) |a/;fl(w)| > 2пg(w) = 0 в силу уравновешенности функции hw на L (лемма 4). Тогда из Wg(w) = Wf(w) - 2aft9(w) следуетmm \Wg{w)\> Г'2,но у различных функций все коэффициенты Уолша совпадать не могут. Таким образом, существует Wo, для которого a/;fl(wo) ф 0 и, следовательно, |Wfl(wo)| > 2п

Ключевые слова

бент-функция , CDMA , OFDM , bent function , CDMA , OFDM

Авторы

ФИООрганизацияДополнительноE-mail
Коломеец Николай Александрович Новосибирский государственный университет студент nkolomeec@gmail.com
Павлов Андрей Владимирович Новосибирский государственный университет студент apavlov.nsk@gmail.com
Всего: 2

Ссылки

Токарева Н. Н. Бент-функции: результаты и приложения. Обзор работ // Прикладная дискретная математика. 2009. №3. С. 15-37.
Paters on К. G. Sequences For OFDM and Multi-code CDMA: two problems in algebraic Coding Theory // Sequences and their applications. Seta 2001. Second Int. Conference (Bergen, Norway, May 13-17, 2001). Proc. Berlin: Springer, 2002. P. 46-71.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 470 с.
Cariet С. Boolean Functions for Cryptography and Error Correcting Codes // Chapter of the monograph «Boolean Methods and Models», Cambridge Univ. Press / eds. P. Hammer, Y. Crama, to appear. Prelim. version is available at www.<rocq.inria.fr/secret/Claude.Carlet/chap-fcts-Bool.pdf>.
McFarland R. L. A family of difference sets in non-cyclic groups // J. Combin. Theory. Ser. A. 1973. V. 15. No. 1. P. 1-10.
Ященко В. В. О критерии распространения для булевых функций и о бент-функциях // Пробл. передачи информации. 1997. Т. 33. Вып. 1. С. 75-86.
Dillon J. F. Elementary Hadamard Difference sets // Ph. D. Thesis. Univ. of Maryland, 1974.
Dillon J. F. A survey of bent functions // The NSA Technical J. 1972. Special Issue. P. 191-215.
Rothaus O. On bent functions // J. Combin. Theory. Ser. A. 1976. V. 20. No. 3. P. 300-305.
Braeken A. Cryptographic properties of Boolean functions and S-boxes // Ph. D. Thesis, Katholieke Univ. Leuven, 2006.
 СВОЙСТВА БЕНТ-ФУНКЦИЙ, НАХОДЯЩИХСЯ НА МИНИМАЛЬНОМ РАССТОЯНИИ ДРУГ ОТ ДРУГА             | ПДМ. 2009. № 4(6).

СВОЙСТВА БЕНТ-ФУНКЦИЙ, НАХОДЯЩИХСЯ НА МИНИМАЛЬНОМ РАССТОЯНИИ ДРУГ ОТ ДРУГА | ПДМ. 2009. № 4(6).

Полнотекстовая версия