О некоторых мерах нелинейности булевых функций

2011 Теоретические основы прикладной дискретной математики №2

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИКЛАДНОЙ ДИСКРЕТНОЙ МАТЕМАТИКИ

УДК 519.7

О НЕКОТОРЫХ МЕРАХ НЕЛИНЕЙНОСТИ БУЛЕВЫХ ФУНКЦИЙ1

Е. К. Алексеев

Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия

E-mail: geni-cmc@mail.ru

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

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

Введение

Одним из приемов современного криптоанализа является использование близости (относительно некоторой метрики) криптографических отображений к отображениям, позволяющим свести исходную криптографическую задачу к менее трудоемкой. Яркими примерами этого являются корреляционный [1] и линейный [2] методы криптоанализа. Одна из возможных характеристик, показывающая эффективность этих методов, была названа нелинейностью булевой функции [3]. Однако могут быть использованы не только линейные (аффинные) приближения. В работе [3] также рассматривались меры близости к другим «слабым» с криптографической точки зрения классам функций. Множество алгебраически вырожденных функций в этом плане представляет определенный практический и теоретический интерес.

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

1. Основные определения и обозначения

Пусть F2 — конечное поле из двух элементов. Пусть Vn = F2 х ... х F2 — векторное

4----v----'

n

пространство наборов длины n с компонентами из F2. Булевой функцией от n переменных будем называть отображение из Vn в F2. Множество всех булевых функций от n переменных будем обозначать Fn. Носителем функции f Е Fn называется множество

1 f = {x Е Vn : f (x) = 1}. Весом wt(f) булевой функции f Е Fn называется мощность ее носителя 1f.

хРабота поддержана РФФИ (проект №09-01-00653-а).

В дальнейшем будем придерживаться следующих обозначений: x(i) — i-й вектор из некоторой совокупности векторов; xj — j-я компонента вектора x. Если n — натуральное число, а с Є {0,1}, то через cn будем обозначать вектор длины n, все компоненты которого равны c. Константные булевы функции будем обозначать через 0 и 1.

Пусть L — подмножество пространства Vn. Тот факт, что L является подпространством пространства Vn, будем обозначать так: L < Vn. Для произвольного линейного подпространства L < Vn через L* будем обозначать множество L \ {0n}. Плоскостями в Vn будем называть смежные классы по подпространствам этого пространства.

Индикаторной функцией множества S С Vn называется такая функция Is Є Fn, что Is(x) = 1 тогда и только тогда, когда x Є S.

Для булевой функции f от n переменных и вектора u Є Vn будем обозначать через fu функцию f u(x) = f (x Ф u). Производной булевой функции f по направлению u Є Vn* называется функция Duf = f  fu. Через J(f) будем обозначать подпространство {u Є Vn : fu = f} пространства Vn.

Пусть A — (n x ^-матрица над F2, а g — булева функция от k переменных. Через gA будем обозначать функцию от n переменных gA(x) = g(xA).

Утверждение 1 [4]. Любая функция f Є Fn представима в виде

2n — dim J

f = ф £iIJ(f )z(i),

i= 1

где Єі Є {0,1}; z(i) Є Vn.

Определение 1 [5]. Порядком алгебраической вырожденности AD(f) булевой функции f Є Fn называется максимально возможное значение n — k, где для целого числа k, 0 ^ k ^ n, существуют такие функция g Є Fk и (n x к)-матрица D над F2, что выполнено равенство f = gD. Функции, для которых AD(f) > 0, называются алгебраически вырожденными. Множество всех алгебраически вырожденных функций от n переменных обозначим через

DG(n) = {f Є Fn : AD(f) > 0}.

Определение 2. Булева функция f Є Fn обладает нетривиальной линейной структурой, если существует такой вектор u Є V*, что Du f Є {0,1}. Подпространство Lf = {u Є Vn : Du f Є {0,1}} называется пространством линейных структур функции f.

Множество булевых функций f Є Fn, имеющих нетривиальную линейную структуру, обозначается через [6]. Легко показать, что если для f Є Fn существует такой вектор u Є V*, что Du f = 1, то Lf = J(f) U (J(f) Ф u).

Определение 3. Преобразованием Уолша — Адамара булевой функции f называется целочисленная функция на Vn, определяемая следующим равенством:

Wf(u) = £ (—1)f(x)<x,u>

хЄУп

(суммирование производится в действительной области). Для каждого u Є Vn значение Wf (u) называется коэффициентом Уолша — Адамара.

Определение 4. Пусть f Є Fn. Целочисленная функция

Af (u) = Е (—1)f(x)f(xu),

хЄУп

определенная на пространстве Vn, называется автокорреляционной функцией, или автокорреляцией булевой функции f.

Справедлива следующая теорема о связи автокорреляционной функции с преобразованием Уолша — Адамара.

Теорема 1 [6]. Пусть f Е Fn. Тогда для любого вектора v Е Vn справедливы соотношения

Wf2(v) = Е Af(u)(-1)<u’v>,

Af(v) = 2-n E Wf2(u)(—1)<u’v>.

Определение 5. Булева функция f Е Fn называется корреляционно-иммунной порядка m, 0 < m ^ n, если для любого вектора и Е Vn, такого, что 1 ^ wt(u) ^ m, выполнено равенство Wf (и) = 0.

Корреляционно-иммунная порядка m функция является корреляционно-иммунной любого меньшего порядка, поэтому введем обозначение

corf = max{m Е N : f — корреляционно-иммунна порядка m}.

Справедливо следующее соотношение между порядком корреляционной иммунности corf булевой функции f и ее алгебраической степенью deg f.

Теорема 2 (неравенство Зигенталера). Для любой функции f Е Fn справедливо неравенство deg f + corf ^ n.

Определение 6. Функция f Е Fn называется бент-функцией, если все ее коэффициенты Уолша — Адамара равны ±2n/2.

Определение 7. Булева функция f от n переменных называется уравновешенной, если wt(f) = 2n-1. Уравновешенная корреляционно-иммунная порядка d функция f Е Fn называется d-устойчивой.

Теорема 3 (критерий Ротхауза). Булева функция f Е Fn является бент-функци-ей тогда и только тогда, когда ее производная Df по каждому ненулевому направлению и Е VT уравновешена.

Определение 8. Пусть f Е Fn. Если существует такое натуральное число r Е N, 0 ^ r ^ n, что квадрат каждого коэффициента Уолша — Адамара равен либо 22n-2r, либо 0, то функция f называется платовидной функцией порядка 2r.

Лемма 1. Пусть f Е Fn, deg f = d ^ 1. Тогда

2n-d ^ wt(f) ^ 2n — 2n-d.

2. Невырожденность булевых функций

Рассмотрим соотношение между параметром AD(f) и подпространством J(f).

Утверждение 2. Для любой булевой функции f Е Fn справедливо равенство

AD(f) = dim J (f )-

Доказательство. Пусть dim J(f) = n — k. Пусть C = J(f) и u(1), ...,u(k) — базис пространства C^. Пусть D — (n х к)-матрица, столбцами которой являются векторы

u(1),u(k). По утверждению 1 функция f может быть представлена следующим образом: f = ZCez(i)  ...  , где t ^ 2k. Пусть функция g G Fk такова, что g(x) = 1

тогда и только тогда, когда существует номер i =1, ...,t, что x = z(i)D.

Покажем, что f (x) = g(xD) для любого вектора x G Vn. Поскольку множество 1/ представимо в виде объединения смежных классов Cфz(1),..., C z(t), то для векторов x G 1/ и только для них справедливо представление x = z(i) фс, где i G {1,..., t}, с G C. Поэтому верно соотношение g(xD) = g(z(i)D ф cD) = g(z(i)D) = 1 = f (x). Таким образом, AD(f) ^ dim J(f).

Пусть AD(f) = n — k и D — такая (n x к)-матрица ранга k, столбцами которой являются векторы u(1),u(2), ...,u(k) пространства Vn, что f (x) = g(xD). Пусть C — линейное подпространство пространства К, с базисом u(1), ...,u(k). Тогда для любого u G Cx и любого x G Vn выполнено f (xфu) = g((xфu)D) = g(xD фuD) = g(xD) = f (x). Таким образом, Cx С J(f) и AD(f) = dim Cx ^ dim J(f).

Учитывая ранее доказанное обратное неравенство, получаем AD(f) = dim J(f).

В работе [3] были введены следующие меры нелинейности булевых функций:

nl(f) = dist(f, An) = 2n-1 — 1 max |W/(u)|;

2 ueVn

i(f) = dist(f, ) = 2n-2 — 1 max |А/(u)|.

4 u€Vn*

Будем называть невырожденностью функции f G Fn значение

P(f) = dist(f,DG(n)).

Заметим, что параметры AD(f), nl(f), $(f) и p(f) являются аффинными инвариантами.

Утверждение 3. Пусть f G Fn и u — произвольный вектор из Vn. Если функция g G DG(n) такова, что u G J(g) и dist(f, g) = min dist(f, g'), то g представима в виде

s':«€J

g = f  fu ф h, где для функции h G Fn выполняется условие Du f  h = h и u G J(h).

Доказательство. Покажем, что 1s С 1/v/u и 1// С 1s.

Пусть h1 = g ((f V fu) ф 1). Тогда u G J(h1). Но dist(g ф h1, f) ^ dist(g,f) и u G J(g ф h1). Поэтому h1 = 0, т. е. 1s С 1/v/u.

Пусть h2 = (g ф 1)(f  fu). Тогда u G J(h2) и u G J(g ф h2). Но dist(g ф h2, f) ^

^ dist(g,f). Поэтому h2 = 0, т. е. 1// С 1s.

Поскольку 1/•/u С 1s, то g представима в виде g = f  fu ф h, где h  f  fu = 0 и u G J(h). Поскольку 1s С 1/v/u, а f V fu = f  fu ф Duf, то для функции h выполнено h  Duf = h. Показанные соотношения доказывают утверждение.

Следствие 1. Для любой булевой функции f G Fn справедливо соотношение

^ • wt(Du f) on—2 1 Л ^

P(f) = min -ö-= 2 — 7 max А/(u).

«eVn 2 4 u^Vn

Доказательство. Из определения параметра р следует, что справедливо равенство p

которых существует ненулевой вектор u G J(g) и dist(f,g) = min dist(f,g'). Из

S':u€J

утверждения 3 следует, что g = f  fu ф h, где u G J(h) и h  Duf = h. Для функции h

выполняется равенство h = h1  h2, где h1 • h2 = 0, hU = h2 и справедливы соотношения

hi(f 0 f • fu) = h и h2(f 0 f • fu) = 0. Поэтому dist(f, g) = wt(f 0 f • fu 0 h1 0 h2) =

= wt(f) — wt(f • fu) — wt(h1)+ wh(h2) = wt(Df )/2. Это соотношение доказывает первое равенство. Второе равенство следует из первого и из того, что

Af (u) = WDuf (0n) = 2n — 2 dist(Duf, 0) = 2n — 2 wt(Df).

Следствие доказано.

Следствие 2. Пусть f Е Fn. Если g Е DG(n) и dist(f,g) = p(f), то для любого вектора и Е J*(g) справедливо равенство Af (u) = max{Af (v) : v Е V*}.

Доказательство. Пусть u — произвольный вектор из J * (g). Тогда, по утверждению 3, функция g представима в виде g = f • fu 0 hM. Отсюда и из следствия 1 получаем, что

dist(f,g) = wt^uf) = 2n-2 — ^Af(u) = P(f) = 2n-2 — 4 maxAf(v)-

2 4 4 veV^

Следовательно, Af(u) = maxAf(v).

veV*

Утверждение 4. Для любой булевой функции f от n ^ 2 переменных справедливо неравенство p(f) ^ 2n-2.

Доказательство. Предположим, что для некоторой функции f Е Fn и для любого ненулевого вектора u Е VI справедливо Af (u) < 0, а поскольку числа Af (u) четны, то Af (u) ^ —2.

Из равенства Е Af(u) = W2(0n) следует Е Af(u) ^ 0. Но Af(0n) = 2n, а по

uGVt. uGVn

предположению Af (u) ^ —2, поэтому

Y, Af (u) ^ 2n — 2(2n — 1) = 2 — 2n

u€Vn

Следовательно, У] Af (u) < 0 при n ^ 2. Полученное противоречие показывает, что существует такой ненулевой вектор u Е Vn, что Af (u) ^ 0, а значит, p(f) ^ 2n-2.  Заметим, что поскольку выполнены включения An С DG(n) С FI, то

nl(f) ^ P(f) ^ ¿(f).

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

Пример 1. Рассмотрим функцию ^0>2 Е F10, построенную в работе [7]:

fl0,2(x) = (xg 0 Х10 0 1)(Ж1Жа 0 Х1Х4 0 Х2Х3 0 Х2Х4 0 X1 0 Х3 0 Х5 0 Хб 0 Х7 0 Xg)0

0(x9 0 Х10)(Х1 0 Х2 0 Х3 0 Х4 0 Х5Х7 0 Х5Х8 0 Х6Х7 0 Х6Х8 0 Х5 0 Х7) 0 Xg.

Функция f140,2 является 6-устойчивой булевой функцией, нелинейность которой равна 2g — 27 = 384. Однако p(f40 2) = ^(f40 2) = 0, т. е. функция является алгебраически вырожденной, причем AD(f40 2) = 3, а dimLf4Q2 = 4.

Рассмотрим вопрос достижимости параметром p своего максимального значения 2n-2. Из критерия Ротхауза следует, что для любой бент-функции f справедливо соотношение p(f) = 2n-2. Для нечетного числа переменных справедлива

Теорема 4. Пусть n нечетно, функция f Е Fn является платовидной функцией порядка n — 1 и {u Е Vn : Wf (u) = 0} = {u Е Vi : <u,w> = 1} для некоторого ненулевого вектора w. Тогда p(f) = 2n-2.

Доказательство. Рассмотрим соотношение между автокорреляционными коэффициентами и коэффициентами Уолша — Адамара функции f для ненулевого вектора u. Поскольку функция f является платовидной функцией порядка n — 1 , то в том случае, когда W2(u) = 0, справедливо равенство Wf(u) = 22n-(n-1) = 2n+1. Следовательно,

1 2n+1

Af(u) = у E W2(v)(—1)<u'v> = E (—4

v€Vn v:<v,w>=1

Таким образом, max Af (u) = 0 и p(f) = 2n-2.

u^V*

В работе [8] было показано, что функции, удовлетворяющие условиям теоремы 4, представимы в виде f = gB, где B — некоторая невырожденная (n х ^-матрица над F2 и g(x) = хп 0 h(x1, ...,хп-1), где h — бент-функция от n — 1 переменной.

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

3. Порядок алгебраической вырожденности наилучших аппроксимаций

Будем обозначать множество алгебраически вырожденных функций, наилучшим образом приближающих некоторую булеву функцию f, через

DG(f) = {g Е DG(n) : dist(f,g) = p(f)}.

Множество функций, имеющих нетривиальную линейную структуру и наилучшим образом приближающих функцию f, обозначим через

F.(f) = {g Е F : dist(f,g) = 5(f)}.

Рассмотрим следующие функционалы:

np(f)= max dimJ(g) = max AD(g);

^ ' seDG(f) ^ seDG(f) ^

пл (f)= max dim L0.

Алгебраически вырожденные функции, наилучшим образом аппроксимирующие данную функцию f, находятся от нее на расстоянии p(f). Однако на этом расстоя-ниии могут находиться функции с разными значениями порядка алгебраической вы-рожденности. С точки зрения криптоанализа нужно аппроксимировать функцию f с помощью наиболее алгебраически вырожденной функции. Максимальное значение порядка алгебраической вырожденности тех функций, которые находятся от f на расстоянии p(f), отражает параметр np(f). Содержательный смысл параметра п(f) аналогичен.

Определение 9. Пусть f Е Fn; пр-функцией для f назовем функцию g^DGf), для которой AD(gp) = np(f).

Аналогично определяется понятие пл-функции для f.

Используя введенные понятия, можно следующим образом описать связь параметров пл, p, пр.

<«,v> _ ) 0, если u = w,

-2n, если u = w.

Утверждение 5. Еслиp(f) = ¿(f),топ(f) Е М/'),пр(f)+1}. Еслиp(f) > ¿(f), то пл (f) = 1.

Доказательство. Пусть функции gp и g5 являются соответственно пр-функцией и пл-функцией для f.

Пусть p(f) = £(f). Тогда пл (f) ^ ^(f), так как иначе dim > dim , что противоречит условию. Заметим также, что dim J(g£) ^ dim J(gp). Тот факт, что для любой функции h справедливо dim Е {dim J(h), dim J(h) + 1}, показывает справедливость первой импликации.

Если же p(f) > £(f), то dim J(g,s) = 0, а = {0n,u}, где D g,s = 1, т. е. пл(f) = 1.

Утверждение доказано.

Заметим, что для функции f140,2 из примера 1 справедливы соотношения

p(f140,2 ) = ^(f140,2) и пл (f140,2) = пР(Л40,2) + 1, а для функции f, удовлетворяющей условиям теоремы 4, справедливы равенства

¿(f ) = 0 и пл (f) = 1

Исходя из доказанного утверждения, можно сказать, что при равенстве значений p(f) и $(f), вычислив один из параметров пл и пр, можно достаточно точно оценить значение второго. Однако когда p(f) = $(f), значение п (f) равно 1, тогда как ^(f) необходимо вычислять. В связи с этим далее большее внимание будет уделяться именно параметру пр.

Утверждение 6. Пусть f Е Fn. Если |wt(f) — 2n-1| > p(f), то p(f) = £(f) и

^(f) = пл(f).

Доказательство. Непосредственно следует из того факта, что любая функция h, для которой существует вектор u Е V*, такой, что h = 1, является уравновешенной, и из определений соответствующих функционалов.

Теорема 5. Для любой булевой функции f Е Fn, для которой p(f) > 0, справед-

ливо соотношение

bg2 p(f) + ^(f) ^ n.

Доказательство. Пусть g — некоторая пр-функция для f. Тогда справедливо соотношение f = g 0 h, где wt(h) = p(f). Предположим, что для некоторого вектора u Е J(g) справедливо h • hu = 0. Тогда, переписав соотношение для функции f в виде

f = (g 0 h • hu) 0 (h 0 h • hu), можно заметить, что

dist(f, g 0 h • hu) = wt(h 0 h • hu) < wt(h) = p(f).

Но это противоречит условию, поскольку функция g 0 h • hu является алгебраически вырожденной.

Получаем, что wt(D h) = 2wt(h) для любого ненулевого вектора u Е J(g). Но максимальный вес такой функции h совпадает с мощностью фактор-пространства Vi/J(g). Следовательно, p(f) = wt(h) ^ 2n-AD(g) = 2n-np(f). Утверждение теоремы получается путем логарифмирования обоих частей неравенства.

Заметим, что если сравнивать полученное неравенство с неравенством Зигенталера с точки зрения оптимизации криптографических параметров, то можно заметить следующее различие. С точки зрения стойкости криптографических примитивов нужно

максимизировать и deg(f), и cor(f). Неравенство Зигенталера показывает, что эти два параметра вступают в противоречие друг с другом. Исходя из тех же соображений, необходимо максимизировать p(f), но минимизировать ^(f). Полученное в теореме 5 неравенство показывает, что эти два параметра в каком-то смысле согласованы.

Следствие 3. Пусть функция f Е Fn такова, что nl(f) = p(f). Тогда справедливо неравенство nl(f) = p(f) ^ 2.

Доказательство. Если nl(f) = p(f), то существует такая аффинная функция g, что dist(f,g) = p(f). Для этой функции справедливо соотношение AD(g) ^ n — 1. Отсюда ^(f) ^ n — 1. Из утверждения теоремы 5 заключаем, что log2 p(f) ^ 1, т. е. p(f) ^ 2.

Следующие две леммы описывают некоторые классы булевых функций, для которых в неравенстве теоремы 5 достигается равенство.

Лемма 2. Пусть функция f Е Fn такова, что ^(f) = k > n/2. Тогда для функции f выполнено равенство log2 p(f) + ^(f) = n тогда и только тогда, когда f представима в виде f = g 0 h, где AD(g) = k, wt(h) = 2n-k и для любых различных векторов u, v Е 1h справедливо u 0 v Е J(g).

Доказательство. Необходимость. Доказательство аналогично теореме 5.

Достаточность. Пусть J(g) = L. Заметим, что для любого вектора u Е L* справедливо wt Duf = wt (Dug 0 Duh) = wt Duh = 2  2n_k < 2  22.

Пусть u Е Vn \ L. Тогда wt Duf = wt (Dug 0 Duh) ^ wt Dug — wt Duh. Поскольку wt Dug ^ 2  2k, а wt Duh ^ 2  2n_k, то

wt Duf ^ 2(2k — 2n_k) > 2(2  22 — 22) > 2  22.

Учитывая неравенство, полученное для векторов из L*, получаем, что для любых векторов u Е L* и v Е Vn \ L справедливо wt Duf < wt Dvf. Таким образом,

p(f) = 2wt = 2n-k = dist(f,g).

Тот факт, что ^(f) = AD(g) = k, следует из неравенства log2 p(f) + пр(f) ^ n.

Лемма 3. Пусть натуральные числа n и k удовлетворяют условиям n ^ 3,

2 ^ k ^ n/2. Пусть A — (n х (n — k^-матрица над F2 ранга n — k и L — подпространство пространства Vn, ортогональное к подпространству, порожденному набором из n — k столбцов матрицы A. Пусть если число (n — k) четно, то g является бент-функцией от n — k переменных, иначе пусть функция g Е Fn_fc удовлетворяет условиям теоремы 4. Пусть функция h Е Fn такова, что wt(h) = 2n-k и носитель 1h является такой плоскостью пространства Vn, что для любых двух ненулевых векторов u,v Е 1h справедливо соотношение u 0 v Е L. Тогда для функции f = gA 0 h справедливы соотношения

p(f) = 2n-k, ^(f) = k.

Доказательство. Пусть (n — k) четно. Если u Е L*, то

wt Duf = wt (DugA 0 h) = wt Duh = 2  wt(h) = 2  2n-k.

Пусть теперь u Е Vn \ L. Если u Е J(h), то

wt Duf = wt (DugA 0 Duh) = wt DugA = 2n 1.

Последнее равенство справедливо, поскольку функция д является бент-функцией от п — к переменных и ДидА = д)А для некоторого V Е ^-к.

Если же и Е (Л-), то

wt Ди/ = -^(Дщд^  ДиЛ,) = wt ДаддА + wt — 2  wt(DugA  ДиЛ,).

Заметим, что для любого ^ 6 У„ \ Ь справедливо равенство wt(/LфZ  ДиЛ,) = 2. Поэтому wt(DugA  ДиЛ,) = 2п-1-к  2 и

wt Duf = 2n-1 + 2n_fc+1 — 2  2n_k = 2n-1

Получили, что

n f i 2n 1, если u Е L, w uf = ^ 2n-k+1, если u e L*.

Следовательно, p(f) = 2n_k. А поскольку p(f) = dist(f, g) и AD(g) = k, то из теоремы 5 следует, что ^(f) = k.

Пусть теперь число (n — k) нечетно. Поскольку функция g удовлетворяет условиям теоремы 4, то справедливо соотношение wt(Du gA) Е {0, 2n-1, 2n} для любого вектора u Е Vn*. Пусть вектор u Е V* таков, что wt(Du gA) = 2n. Тогда wt(Du f) ^ 2n — 2n_fc+1 ^ ^ 2n-k+1. Рассмотрение оставшихся случаев аналогично случаю, когда (n — k) четно. В результате получаем, что p(f) = 2n_k и ^(f) = k.

Пример 2. Примером использования конструкции леммы 3 может служить функция f8 от 8 переменных, которая задается в виде алгебраической нормальной формы следующим образом:

fg(x) = Ж5Ж6Ж7Xg 0 Ж7Ж8 0 Ж5Ж6Ж8 0 Ж5Ж6Ж7 0 Х5Х8 0 Х5Х7Х8 0 Ж6Ж7 0 Х6Х7Х8 0

0 Ж1Ж2 0 Х3Х4 0 Ж6Ж8 0 Х5Х7 0 Х5Х6 0 Жз 0 Х8 0 Ж7 0 Ж5 0 Жб 0 1.

Параметры функции f8 имеют значения

deg(f8) = 4, nl(f8) = 100, p(f8) = ^(f8) = 16, пр(/^8) = 4, wt(f8) = 100.

Функция f8 представима в виде f8 = gA 0 h. Функция g = x2 0 x1x2 0 ж3ж4 является бент-функцией от 4 переменных. Носитель функции h является подпространством пространства V8 размерности 4 с базисом u(1) = (00000001), u(2) = (00000010), u(3) = (00000100), u(4) = (00001000). Эти же векторы являются столбцами (8 х 4)-матрицы A.

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

Теорема 6. Для любой функции f Е Fn, такой, что ^(f) > n/2, существует такое целое число T, 0 ^ T ^ 2n_np(f), что справедливо неравенство

T (2np(f) — 1) ^ wt(f) ^ T (2np(f) — 1) + 2n_np(f).

Доказательство. Пусть g — некоторая пр-функция для f. Тогда для любого смежного класса J(g) 0 z справедливо 11 f П J(g) 0 z| Е {0,1, 2np(f) — 1, 2np(f)}. Вес функции f получается суммированием мощностей множеств 11 f П J(g) 0 z | по всем различным смежным классам J(g) 0 z. Утверждение теоремы следует из того, что количество различных смежных классов по подпространству J(g) равно 2n_np(f).

Теорема 7. Пусть f Е Fn. Если ^(f) > log2 p(f), то deg f ^ ^(f).

Доказательство. Пусть функция f Е Fn представима в виде f = g 0 h, где AD(g) = ^(f) > log2 wt(h) = log2p(f). Тогда справедливы неравенства

2n_degh ^ wt(h) ^ 2n — 2n_deg h и deg g ^ n — пр(f).

Отсюда получаем deg h ^ n — log2 p(f) и n — ^(f) ^ degg. Складывая эти два неравенства, получим, что deg h — deg g ^ ^(f) — log2 p(f) > 0, т. е. deg h > deg g.

Поскольку deg f = max(deg g, deg h) при deg g = deg h, то deg f = deg h ^ ^ n — log2p(f) ^ пр^).

Неравенство, полученное в теореме 6 и связывающее вес функции со значением параметра пр, схоже с двусторонним неравенством из леммы 1. Комбинирование этих двух неравенств позволяет получать соотношения между различными параметрами булевой функции.

4. Свойства пр-функций и вычисление параметра пр

Рассмотрим свойства пр-функций для некоторой функции f.

Теорема 8. Пусть f Е Fn и g Е DG(f). Если существуют два таких различных вектора u,v Е V*, что u,v Е J(g), то функция g представима в виде

g = f  fu 0 f  fv 0 fu  fv.

Доказательство. Поскольку fu  fv = (f  f uv)v, то из следствия 2 следует, что wt(f  fu) = wt(f  fv) = wt(fu  fv). Из утверждения 3 следует, что функция g представима в виде

g = f  fu 0 hu 0 hu, где hu  f = hu и hu  f = 0, g = f  fv 0 hv 0 hv, где hv  f = hv и hv  f = 0.

Умножим обе части первого равенства на функцию /  /*  /  /и  /*:

д (/  /* е /  /и  /*) = /  /* е /  /и  /* = (/  /* е /  /и  /*) Л

Отсюда получаем, что wt(hu) ^ wt(/  /* е /  /и  /*).

Воспользовавшись вторым представлением функции д, получим

С = hu = hv  hu 0 hu  hv = hv  f  hu 0 hu  hv  fv = hu  fv  hv.

Таким образом, справедливо равенство  /*. Теперь умножим обе части первого

представления функции д на функцию /и  /* е /  /и  /*:

g (fu  fv 0 f  fu  fv ) = hu  fu  fv 0 hu  f  fu  fv = hu  fv = hu.

Отсюда получаем wt(/u  /* е /  /и  /*) ^ wt(hU). Поскольку wt(hU) = wt(hu) и

^(/“  / е /  /и  /) = ^(/  / е /  /и  /), то ^(М = wt(/  / е /  /и  /), а

значит, верны равенства = /  /* е /  /и  /*, и  /* е /  /и  /*.

Переписав первое представление для функции д, учитывая полученные соотношения, получим д = /  /и е /  / е /и  /*.

Таким образом, вычисление значения пр(/) можно проводить по следующему принципу. Необходимо вычислить значение А/ = шах А/(и), одновременно сформировав

множество A = {u Е V* : Af (u) = А*}. Вычислить значение пр^) можно с помощью множества B = {g = f  fu 0 f  fv 0 fu  fv : u, v Е A, u = v, dist(f,g) = p(f)} по формуле

^(f) = max{1, max dim J(g)}.

5. Вырожденность бент-функций

Рассмотрим свойства параметров p и пр для случая, когда f является бент-функ-цией.

Лемма 4. Пусть f Е Fn является бент-функцией и g Е DG(f). Если существуют два различных ненулевых вектора u,v Е Vn, такие, что u,v Е J(g), то функция g представима в виде g = Du (f  fv).

Доказательство. По теореме 8 справедливо равенство g = f  fu 0 f  fv 0 fu  fv.

По условию g = gu. Используя представление функции g, получим равенство

f  f v 0 f u  f v = f u  f uv 0 f  f uv

Преобразовав его, получаем Duf (Duf )v = 0. Учитывая, что производная бент-функ-ции по любому направлению уравновешена, это соотношение можно переписать в виде Duf 0 I = (Duf )v. Умножая обе части на f, получаем f (I 0 f 0 fu) = (fv 0 fuv) f, f  fu 0 f  fv 0 f  fuv = 0. Используя представление функции g, запишем g = = f  f uv 0 (f  f uv )u = Du(f  f uv). После переобозначения векторов имеем требуемое соотношение.

Теорема 8 и лемма 4 показывают, что пр-функции для функции f легко выражаются через функции вида f  fu. Некоторые свойства функций вида f  fu для случая, когда функция f является бент-функцией, отражены в следующем утверждении.

Утверждение 7. Для любой бент-функции f Е Fn, где n ^ 4, и любого ненулевого вектора u Vn справедливо соотношение AD(f  fu) = 1.

Доказательство. По критерию Ротхауза, производная функции f по любому ненулевому направлению уравновешена. Из соотношения wt(f  fu) = wt(f) — —wt(Du f) = 2n_2 ± 2 2 _1 получаем, что для любых ненулевых векторов u,v Е Vn справедливо равенство wt(f  fu) = wt(f  fv).

Предположим, что утверждение не верно, т. е. AD(f  fu) > 1. Поскольку справедливо AD(f  fu) = dim J(f  fu), то это означает, что существует такой ненулевой вектор v Е , отличный от u, что (f  fu)v = f  fu. Учитывая равенство весов wt(f  fu) = wt(f  fv), получаем f  fu = f  fv = f  fuv = (f  fuv)u = fu  fv.

Используя полученные ранее равенства, имеем f (fu0fv) = 0, откуда f (Duv f )u = = (fu  Duv f )u = 0. Таким образом, выполнено соотношение fu  Duv f = 0. Заменяя в рассуждениях вектор u на v, получаем fv  Duv f = 0.

Рассмотрим два случая. Если wt(f) = 2n_1 + 22_1, то ни одно из полученных ранее соотношений не может быть выполнено, так как производная бент-функции по любому ненулевому направлению уравновешена.

Если же wt(f) = 2n_1 — 22_1, то для выполнения двух полученных равенств необходимо, чтобы выполнялось неравенство wt(fu) + wt(fv) — wt(fu  fv) + 2n_1 ^ 2n. Так как fu  fv = (f  fuv)u, то wt(fu  fv) = 2n_2 — 22_1. Подставляя значения весов функций в неравенство, получаем

2n + 2n_1 — 2n_2 — 2 2 _1 ^ 2n,

2n_2 - 22_1 < 0.

Но для n ^ 4 это неравенство не выполняется. Получили противоречие, которое доказывает утверждение.

Для бент-функций параметр p достигает своего максимального значения 2n_2. С помощью конструкции, описанной в лемме 3, можно строить бент-функции, для которых в неравенстве теоремы 5 достигается равенство, т. е. бент-функции с пр^) = 2. Для этого достаточно задать четное число переменных n и положить k = 2.

Пример 3. Функция b8 является бент-функцией от восьми переменных и задается следующим образом:

&8(х) = Ж4Ж5Ж6 0 Ж2Ж3Ж5 0 Ж1Ж3Ж4 0 Ж7Ж8 0 Ж1Ж5 0 Ж3Ж4 0 Ж2Ж4 0 Ж1Ж4 0 Ж2Ж3 0

0 Ж1Ж3 0 Х3Х6 0 Ж8 0 Х7 0 1.

Параметры функции b8 имеют следующие значения:

deg(b8) = 3, nl(b8) = 120, p(b8) = ¿(&8) = 64, пр(^8) = 2, wt^) = 120.

Функция b8 представима в виде b8 = gA 0 h. Функция

g(x) = Х2Х6 0 Х3Х6 0 Ж1Ж2Ж3 0 Х4Х6 0 Ж1Ж4 0 Х3Х4 0 Х3Х4Х6 0 Х3Х5 0 Х4Х5 0 Ж2Ж4Ж5

является бент-функцией от шести переменных. Векторы u(1) = (00000001), u(2) = = (00000010), u(3) = (00000100), u(4) = (00001000), u(5) = (00010000), u(6) = (00100000) являются столбцами (8 х 6)-матрицы A, а также образуют базис подпространства, которое является носителем функции h.

ЛИТЕРАТУРА

1. Siegenthaler T. Decrypting a class of stream chipher using ciphertext only // IEEE Trans. Computers. 1985. V. C-34. No. 1. P. 81-85.

2. Matsui M. Linear cryptanalysis method for DES cipher // LNCS. 1993. V. 765. P. 386-397.

3. Meier W. and StaffeJbach O. Nonlinearity criteria for cryptographic functions // LNCS. 1990. V. 434. P. 549-562.

4. Алексеев Е. К. О некоторых алгебраических и комбинаторных свойствах корреляционноиммунных булевых функций // Дискретная математика. 2010. Т. 22. №3. С. 110-126.

5. Dawson Е. and WuC.K. Construction of correlation immune boolean functions // LNCS. 1997. V. 1334. P. 170-180.

6. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.

7. Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 91-148.

8. Zhang X. M. and Zheng Y. Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors // Design Codes Cryptography. 1996. No. 7 (1/2). P. 111-134.