О некоторых мерах нелинейности булевых функций | ПДМ. 2011. № 2(12).

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

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

On some measures of nonlinearity for boolean functions.pdf ВведениеОдним из приемов современного криптоанализа является использование близости(относительно некоторой метрики) криптографических отображений к отображени-ям, позволяющим свести исходную криптографическую задачу к менее трудоемкой.Яркими примерами этого являются корреляционный [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.В дальнейшем будем придерживаться следующих обозначений: x(i) - i-й вектор изнекоторой совокупности векторов; Xj - j-я компонента вектора x. Если n - натураль-ное число, а c Е {0,1}, то через cn будем обозначать вектор длины n, все компонентыкоторого равны с. Константные булевы функции будем обозначать через 0 и 1.Пусть L - подмножество пространства Vn. Тот факт, что L является подпрост-ранством пространства Vn, будем обозначать так: L < Vn. Для произвольного линей-ного подпространства L 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, имеющих нетривиальную линейную струк-туру, обозначается через ?n [6]. Легко показать, что если для f Е Fn существует такойвектор u Е Vn*, что Du f = I, то Lf = J ( f ) U ( J ( f ) ф u).Определение 3. Преобразованием Уолша - Адамара булевой функции f называет-ся целочисленная функция на Vn, определяемая следующим равенством:Wf (u) = Е (-1)f(x)®.uevnОпределение 5. Булева функция f Е Fn называется корреляционно-иммуннойпорядка m, 0 < m ^ n, если для любого вектора u Е Vn, такого, что 1 ^ wt(u) ^ m,выполнено равенство Wf (u) = 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 является бент-функци-ей тогда и только тогда, когда ее производная Duf по каждому ненулевому направле-нию u Е 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 = I C e z ( i ) ф ... ф I C ® z ( t ) , где t ^ 2k. Пусть функция g Е Fk такова, что g(x) = 1тогда и только тогда, когда существует номер i = 1 , ...,t, что x = z( i )D.Покажем, что f (x) = g(xD) для любого вектора x Е V„. Поскольку множество 1fпредставимо в виде объединения смежных классов Cфz( 1 ) ,..., Cфz( t ) , то для векторовx Е 1f и только для них справедливо представление x = z(i) фc, где i Е {1,..., t}, c Е 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 - линейноеподпространство пространства Vn с базисом u(1), ...,u(k). Тогда для любого u Е Cx илюбого x Е V^ выполнено 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 |Wf(u)|; 2 uevn*(f) = dist(f, Fn) = 2n - 2 -1 max i A f 4 uevn* (u)i.Будем называть невырожденностью функции f Е Fn значениеp(f ) = dist(f, DG(n)).Заметим, что параметры AD(f), nl(f), $(f) и p(f) являются аффинными инвари-антами.Утверждение 3. Пусть f Е Fn и u - произвольный вектор из V*. Если функцияg Е DG(n) такова, что u Е J(g) и dist(f, g) = min dist(f, g'), то g представима в видеg':u€J (g')g = f fu ф h, где для функции h Е Fn выполняется условие Du f h = h и u Е J(h).Доказательство. Покажем, что 1g С 1 f V f u и 1ffu С 1g.Пусть h1 = g ((f V f u ) ф 1). Тогда u Е J(h1). Но dist(g ф h1 , f ) ^ dist(g,f) иu Е J(g ф h1). Поэтому h1 = 0, т. е. 1g С 1 f V f « .Пусть h2 = (g ф 1)(f f u ) . Тогда u Е J(h2) и u Е J(g ф h2). Но dist(g ф h2, f) ^^ dist(g,f). Поэтому h2 = 0, т. е. 1ffu С 1g.Поскольку 1ffu С 1g, то g представима в виде g = f f u ф h, где h f f u = 0 иu Е J(h). Поскольку 1g С 1 f V f u , а f V f u = f f u ф Du f , то для функции h выполненоh Du f = h. Показанные соотношения доказывают утверждение. Следствие 1. Для любой булевой функции f Е Fn справедливо соотношение/ л w t ( D u f ) 0n - 2 1 л ( \ P ( f ) = mueivnn ^2 = 2 - 4т umevan*x A f ( u ) .Доказательство. Из определения параметра р следует, что справедливо ра-венство p(f) = min min dist(f,g'). Вычислим dist(f,g) для тех функций g, дляuevn* g':ueJ (g')которых существует ненулевой вектор u Е J(g) и dist(f,g) = min dist(f,g'). Изg':u€J (g')утверждения 3 следует, что g = f fu ф h, где u Е J(h) и h Du f = h. Для функции hвыполняется равенство h = h1 ф h2, где h1 h2 = 0, hU = h2 и справедливы соотношенияhi(f Ф f f u ) = h1 и h2(f Ф f f u ) = 0. Поэтому dist(f,g) = wt(f ф f fu ф h ф h2) == wt(f) - wt(f f u ) - wt(h1)+ wh(h2) = wt(DUf )/2. Это соотношение доказывает первоеравенство. Второе равенство следует из первого и из того, чтоAf (u) = WDuf (0n) = 2n - 2 dist(Duf, 0) = 2n - 2 w t ( D f ) .Следствие доказано. Следствие 2. Пусть f Е Fn. Если g Е DG(n) и dist(f,g) = p(f), то для любоговектора u Е J * (g) справедливо равенство Af (u) = max{Af (v) : v Е Vi*}.Доказательство. Пусть u - произвольный вектор из J * (g). Тогда, по утвер-ждению 3, функция g представима в виде g = f fu ф hu. Отсюда и из следствия 1получаем, чтоdist(f, g) = = 2n - 2 - 1Af (u) = p(f) = 2n - 2 - 4 max Af (v).2 4 4 vevnСледовательно, Af (u) = max Af (v). v e VnУтверждение 4. Для любой булевой функции f от n ^ 2 переменных справед-ливо неравенство p(f) ^ 2n-2.Доказательство. Предположим, что для некоторой функции f Е Fn и длялюбого ненулевого вектора u Е V^ справедливо Af (u) < 0, а поскольку числа Af (u)четны, то Af (u) ^ -2.Из равенства Е Af(u) = Wf2(0n) следует Е Af(u) ^ 0. Но Af(0n) = 2n, а поueVr u&Vrпредположению Af (u) ^ -2, поэтомуE Af (u) ^ 2n - 2(2n - 1) = 2 - 2nueVrСледовательно, E Af (u) < 0 при n ^ 2. Полученное противоречие показывает, чтоueVrсуществует такой ненулевой вектор u Е Vn, что Af (u) ^ 0, а значит, p(f) ^ 2n-2. Заметим, что поскольку выполнены включения An С DG(n) С Fn, тоnl(f) ^ P(f) ^ *(f).Следующий пример показывает, что высокая нелинейность не гарантирует высокойневырожденности булевой функции.Пример 1. Рассмотрим функцию Е F10, построенную в работе [7]:fl0,2(x) = (xg ф Х10 ф 1)(Х1Х3 ф Х1Х4 ф Х2Х3 ф Х2Х4 ф Х1 ф Хз ф Х5 ф Хб ф Х7 ф Хз)фф(х9 ф Х1о)(Х1 ф Х2 ф Хз ф Х4 ф Х5Х7 ф Х5Х8 ф Х6Х7 ф ХбХз ф Х5 ф Х7) ф Хд.Функция f140,2 является 6-устойчивой булевой функцией, нелинейность которой рав-на 2д - 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 Е К, : Wf (u) = 0} = {u Е К, : = 1} для некоторогоненулевого вектора w. Тогда p(f) = 2n-2.Доказательство. Рассмотрим соотношение между автокорреляционнымикоэффициентами и коэффициентами Уолша - Адамара функции f для ненулевоговектора u. Поскольку функция f является платовидной функцией порядка n - 1 , тов том случае, когда W2(u) = 0, справедливо равенство Wf(u) = 22 n - ( n - 1 ) = 2n+1.Следовательно,Af (u) = - V W2(v)(-1) = ^ у (-1) f о, е с л и u = w,2n ^ fV A ' 2n ^ K ' \ -2n, если u = w.Таким образом, max Af (u) = 0 и p(f) = 2n 2. u e vnВ работе [8] было показано, что функции, удовлетворяющие условиям теоремы 4,представимы в виде f = gB, где B - некоторая невырожденная (n x n)-матрица над F2и g(x) = xn ф h(x1; ...,xn-1), где h - бент-функция от n - 1 переменной.Заметим, что проблема исчерпывающего описания множества функций, для кото-рых параметр p достигает своего максимума, пока не решена.3. Порядок алгебраической вырожденности наилучших аппроксимацийБудем обозначать множество алгебраически вырожденных функций, наилучшимобразом приближающих некоторую булеву функцию f, черезDG(f) = {g Е DG(n) : dist(f,g) = p(f)}.Множество функций, имеющих нетривиальную линейную структуру и наилучшимобразом приближающих функцию f, обозначим через?n(f) = {g Е Fn : dist(f,g) = 5(f)}.Рассмотрим следующие функционалы:np(f) = max dim J(g) = max AD(g); M ; geDG(f) geDG(f)пл ( f ) = max dim L0.geF0 ( f ) gАлгебраически вырожденные функции, наилучшим образом аппроксимирующиеданную функцию f, находятся от нее на расстоянии p(f). Однако на этом расстоя-ниии могут находиться функции с разными значениями порядка алгебраической вы-рожденности. С точки зрения криптоанализа нужно аппроксимировать функцию fс помощью наиболее алгебраически вырожденной функции. Максимальное значениепорядка алгебраической вырожденности тех функций, которые находятся от f на рас-стоянии p(f), отражает параметр np(f). Содержательный смысл параметра пл(f) ана-логичен.Определение 9. Пусть f Е Fn; пр-функцией для f назовем функцию gрЕDG(f),для которой AD(gp) = np(f).Аналогично определяется понятие пл-функции для f.Используя введенные понятия, можно следующим образом описать связь парамет-ров пл, p, пр.Утверждение 5. Еслиp(f) = . ( f ) , т о п , ( f ) Е {np(f),Пр(f) + 1}. Еслиp(f) > .(f),то п, ( f ) = 1.Доказательство. Пусть функции gp и gs являются соответственно пр-функциейи п,-функцией для f.Пусть p(f) = $(f). Тогда п, ( f ) ^ np(f), так как иначе dim Lgp > dim Lgs, что проти-воречит условию. Заметим также, что dim J (gs) ^ dim J (gp). Тот факт, что для любойфункции h справедливо dimLh Е {dim J(h), dim J(h) + 1}, показывает справедливостьпервой импликации.Если же p(f) > $(f), то dim J (gs) = 0, а Lgs = {0n,u}, где Du gs = 1, т.е. п, ( f ) = 1.Утверждение доказано. Заметим, что для функции f40 2 из примера 1 справедливы соотношенияp( f140 ,2) = f 0 , 2 ) и п& (f140 ,2) = nP( f140 ,2) + 1,а для функции f, удовлетворяющей условиям теоремы 4, справедливы равенства5(f) = 0 и п, (f ) = 1.Исходя из доказанного утверждения, можно сказать, что при равенстве значе-ний p(f) и $(f), вычислив один из параметров пs и пр, можно достаточно точно оце-нить значение второго. Однако когда p(f) = $(f), значение п, ( f ) равно 1, тогда какnp(f) необходимо вычислять. В связи с этим далее большее внимание будет уделятьсяименно параметру пр.Утверждение 6. Пусть f Е Fn. Если |wt(f) - 2n-1| > p(f), то p(f) = 5(f) ипp(f ) = п (f).Доказательство. Непосредственно следует из того факта, что любая функ-ция h, для которой существует вектор u Е Vn*, такой, что Du h = 1, является уравно-вешенной, и из определений соответствующих функционалов. Теорема 5. Для любой булевой функции f Е Fn, для которой p(f) > 0, справед-ливо соотношениеbg2 p ( f ) + ^ ( f ) ^ n.Доказательство. Пусть g - некоторая пр-функция для f. Тогда справедливосоотношение f = g ф h, где wt(h) = p(f). Предположим, что для некоторого вектораu Е J(g) справедливо h hu = 0. Тогда, переписав соотношение для функции f в видеf = (g ф h hu) ф (h ф h hu), можно заметить, чтоdist(f, g ф h hu) = wt(h ф h hu) < wt(h) = p(f).Но это противоречит условию, поскольку функция g ф h hu является алгебраическивырожденной.Получаем, что wt(DU h) = 2wt(h) для любого ненулевого вектора u Е J(g). Но мак-симальный вес такой функции h совпадает с мощностью фактор-пространства Vn/J(g).Следовательно, p(f) = wt(h) ^ 2n-AD(g) = 2n - n p ( 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.Отсюда пp(f) ^ n - 1. Из утверждения теоремы 5 заключаем, что log2p(f) ^ 1, т.е.p(f) ^ 2. Следующие две леммы описывают некоторые классы булевых функций, для кото-рых в неравенстве теоремы 5 достигается равенство.Лемма 2. Пусть функция f Е Fn такова, что ^ ( f ) = k > n/2. Тогда для функ-ции f выполнено равенство log2 p(f) + ^ ( f ) = n тогда и только тогда, когда f пред-ставима в виде f = g ф h, где AD(g) = k, wt(h) = 2n - k и для любых различныхвекторов u, v Е 1h справедливо u ф v Е J(g).Доказательство. Необходимость. Доказательство аналогично теореме 5.Достаточность. Пусть J(g) = L. Заметим, что для любого вектора u Е L* справед-ливо wt Du f = wt (Dug ф Duh) = wt Duh = 2 2n - k < 2 22.Пусть u Е Vn \ L. Тогда wt Du f = wt (Dug ф Duh) ^ wt Dug - wt Duh. Посколькуwt Dug ^ 2 2k, а wt Duh ^ 2 2n - k , тоwt Du f ^ 2(2k - 2n - k ) > 2(2 22 - 22) > 2 22.Учитывая неравенство, полученное для векторов из L*, получаем, что для любыхвекторов u Е L* и v Е Vn \ L справедливо wt Du f < wt Dvf. Таким образом,p(f ) = 2 wt Duf = 2n - k = dist(f,g).Тот факт, что пp(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-k удовлетворяет условиям теоремы 4.Пусть функция h Е Fn такова, что wt(h) = 2n - k и носитель 1h является такой плоско-стью пространства Vn, что для любых двух ненулевых векторов u,v Е 1h справедливосоотношение u ф v Е L. Тогда для функции f = gA ф h справедливы соотношенияp(f) = 2n - k , ^ ( f ) = k.Доказательство. Пусть (n - k) четно. Если u Е L*, тоwt Duf = wt (DugA ф Duh) = wt Duh = 2 wt(h) = 2 2n - k.Пусть теперь u Е Vn \ L. Если u Е J(h), тоwt Duf = wt (DugA ф Duh) = wt DugA = 2n - 1.Последнее равенство справедливо, поскольку функция g является бент-функцией отn - k переменных и DugA = (Dvg)A для некоторого v Е Vn-k.Если же u Е J(h), тоwt Duf = wt(DugA ф Duh) = wt DugA + wt Duh - 2 wt(DugA Duh).Заметим, что для любого z Е Vn \ L справедливо равенство wt(/L e z Duh) = 2.Поэтому wt(DugA Duh) = 2 n - 1 - k 2 иwt D u f = 2n - 1 + 2n - f c + 1 - 2 2 n - k = 2n -1Получили, чтоn /> i 2n 1, если u Е L,wt D u f = < 2n-k+1, если u G 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 Е Vn* таков, что wt(Du gA) = 2n. Тогда wt(Du f) ^ 2n - 2n - f c + 1 ^^ 2n-k+1. Рассмотрение оставшихся случаев аналогично случаю, когда (n - k) четно.В результате получаем, что p ( f ) = 2n - k и ^ ( f ) = k. Пример 2. Примером использования конструкции леммы 3 может служитьфункция fs от 8 переменных, которая задается в виде алгебраической нормальнойформы следующим образом:fs(x) = x5x6x7xs ф x/xs ф x5x6xs ф x5x6x/ ф x5xg ф x5x/xs ф x6x/ ф xex/xg фф x1x2 ф x3x4 ф x6xs ф x5x7 ф x5x6 ф x3 ф xs ф x/ ф x5 ф x6 ф 1.Параметры функции fs имеют значенияdeg(fs) = 4, nl(fs) = 100, p(fs) = ЗД) = 16, Пр(fs) = 4, wt(fs) = 100.Функция fs представима в виде fs = gA ф h. Функция g = x2 ф x1x2 ф x3x4 яв-ляется бент-функцией от 4 переменных. Носитель функции h является подпростран-ством пространства VS размерности 4 с базисом u(1) = (00000001), u(2) = (00000010),u(3) = (00000100), u(4) = (00001000). Эти же векторы являются столбцами (8 x 4)-матрицы A.Рассмотрим теперь некоторые соотношения, которые связывают параметры p и прбулевой функции с другими ее важными характеристиками.Теорема 6. Для любой функции f Е Fn, такой, что ^ ( f ) > n/2, существуеттакое целое число T, 0 ^ T ^ 2n - n p ( f ) , что справедливо неравенствоT ( 2 n p ( f ) - 1) ^ w t ( f ) ^ T ( 2 n p ( f ) - 1) + 2 n - n p ( f ) .Доказательство. Пусть g - некоторая пр-функция для f. Тогда для любогосмежного класса J(g) ф z справедливо 11 f П J(g) ф z| Е {0,1, 2np(f) - 1, 2n p ( f ) }. Весфункции f получается суммированием мощностей множеств 11 f П J(g) ф z | по всемразличным смежным классам J(g) ф z. Утверждение теоремы следует из того, чтоколичество различных смежных классов по подпространству J(g) равно 2n - n p ( f ) . Теорема 7. Пусть f Е Fn. Если ^ ( f ) > log2 p(f), то deg f ^ пp(f).Доказательство. Пусть функция f Е Fn представима в виде f = g ф h, гдеAD(g) = ^ ( f ) > log2 wt(h) = log2p(f). Тогда справедливы неравенства2n - d e g h ^ 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 - l o g 2 p ( f ) ^ Пp( f ) . Неравенство, полученное в теореме 6 и связывающее вес функции со значениемпараметра пр, схоже с двусторонним неравенством из леммы 1. Комбинирование этихдвух неравенств позволяет получать соотношения между различными параметрамибулевой функции.4. Свойства пр-функций и вычисление параметра прРассмотрим свойства пр-функций для некоторой функции f.Теорема 8. Пусть f Е Fn и g Е DG(f). Если существуют два таких различныхвектора u,v Е V**, что u,v Е J(g), то функция g представима в видеg = f f u ф f f v ф f u f v .Доказательство. Поскольку f u f v = (f f u®v ) v , то из следствия 2 следует,что wt(f f u ) = wt(f f v ) = wt(fu f v ) . Из утверждения 3 следует, что функция gпредставима в видеg = f f u ф hu ф hu, где hu f = hu и hu f = 0,g = f f v ф hv ф hv, где hv f = hv и hv f = 0.Умножим обе части первого равенства на функцию f fv ф f fu f v:g (f f v ф f f u f v ) = f f v ф f f u f v = (f f v ф f f u f v ) huОтсюда получаем, что wt(hu) ^ wt(f fv ф f fu f v ).Воспользовавшись вторым представлением функции g, получим^ = h u = h v h u ф h u h v = h v f h u ф h u h v f v = h u f v h v Таким образом, справедливо равенство hu = hu f v . Теперь умножим обе части первогопредставления функции g на функцию fu fv ф f fu f v :g ( f u f v ф f f u f v ) = hu f u f v ф hu f f u f v = hu f v = hu.Отсюда получаем wt(fu fv ф f fu f v ) ^ wt(hu). Поскольку wt(hu) = wt(hu) иwt(fu fv ф f fu f v ) = wt(f fv ф f fu f v ) , то wt (hu) = wt(f fv ф f fu f v ) , азначит, верны равенства hu = f fv ф f fu f v , hu = fu fv ф f fu f v .Переписав первое представление для функции g, учитывая полученные соотноше-ния, получим g = f fu ф f fv ф fu f v . Таким образом, вычисление значения ^ ( f ) можно проводить по следующему прин-ципу. Необходимо вычислить значение А*- = maxAf (u), одновременно сформировавf uev*множество A = {u Е V* : Af (u) = Д*}. Вычислить значение np(f) можно с помощьюмножества B = {g = f fu ф f fv ф fu fv : u,v Е A, u = v, dist(f,g) = p ( f ) } поформулеnp ( 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 f v ).Доказательство. По теореме 8 справедливо равенство g = f fu ф f fv ф fu f v .По условию g = gu. Используя представление функции g, получим равенствоf f v ф f u . f v f u f u®V ф f f u®vПреобразовав его, получаем Du f (Duf )v = 0. Учитывая, что производная бент-функ-ции по любому направлению уравновешена, это соотношение можно переписать в видеDuf ф 1 = (Duf )v. Умножая обе части на f, получаем f (1 ф f ф f u ) = (fv ф fu®v) f,f fu ф f fv ф f fu®v = 0. Используя представление функции g, запишем g == f f u®v ф (f f u®v )u = Du( f f u®v). После переобозначения векторов имеем требуе-мое соотношение. Теорема 8 и лемма 4 показывают, что пр-функции для функции f легко выража-ются через функции вида f f u . Некоторые свойства функций вида f fu для случая,когда функция f является бент-функцией, отражены в следующем утверждении.Утверждение 7. Для любой бент-функции f Е Fn, где n ^ 4, и любого ненуле-вого вектора u Е Vn справедливо соотношение AD(f f u ) = 1.Доказательство. По критерию Ротхауза, производная функции f по любо-му ненулевому направлению уравновешена. Из соотношения wt(f f u ) = wt(f) --wt(Du f) = 2n - 2 ± 2"2-1 получаем, что для любых ненулевых векторов u,v Е Vnсправедливо равенство wt(f f u ) = wt(f f v ).Предположим, что утверждение не верно, т.е. AD(f f u ) > 1. Поскольку спра-ведливо AD(f f u ) = dim J(f f u ) , то это означает, что существует такой ненуле-вой вектор v Е Vn, отличный от u, что (f f u ) v = f f u . Учитывая равенство весовwt(f f u ) = wt(f f v ) , получаем f fu = f fv = f fu®v = (f fu®v)u = fu f v .Используя полученные ранее равенства, имеем f ( f uфf v ) = 0, откуда f (Du®v f )u == ( f u Du®v f )u = 0. Таким образом, выполнено соотношение fu Du®v f = 0. Заменяяв рассуждениях вектор u на v, получаем fv Du®v f = 0.Рассмотрим два случая. Если wt(f) = 2n - 1 + 22- 1 , то ни одно из полученных ранеесоотношений не может быть выполнено, так как производная бент-функции по любомуненулевому направлению уравновешена.Если же wt(f) = 2n - 1 - 22- 1 , то для выполнения двух полученных равенств необхо-димо, чтобы выполнялось неравенство wt(fu) + wt(fv) - wt(fu f v ) + 2n - 1 ^ 2n. Так какfu fv = (f fu®v)u, то wt(fu f v ) = 2n - 2 - 22- 1 . Подставляя значения весов функцийв неравенство, получаем2n + 2n - 1 - 2n - 2 - 2 2 - 1 ^ 2n,2n - 2 - 2 2 - 1 < 0.Но для n ^ 4 это неравенство не выполняется. Получили противоречие, которое дока-зывает утверждение. Для бент-функций параметр p достигает своего максимального значения 2n - 2 . С по-мощью конструкции, описанной в лемме 3, можно строить бент-функции, для которыхв неравенстве теоремы 5 достигается равенство, т. е. бент-функции c ^ ( f ) = 2. Дляэтого достаточно задать четное число переменных n и положить k = 2.Пример 3. Функция bs является бент-функцией от восьми переменных и задает-ся следующим образом:bs(x) = Ж4Ж5Ж6 ф Ж2Ж3Ж5 ф Ж1Ж3Ж4 ф Ж7Ж8 ф Ж1Ж5 ф Ж3Ж4 ф Ж2Ж4 ф Ж1Ж4 ф Ж2Ж3 фф Ж1Ж3 ф Ж3Ж6 ф Xs ф Х7 ф 1.Параметры функции bs имеют следующие значения:deg(bs) = 3, nl(bs) = 120, p(bs) = .(bs) = 64, ^(bs) = 2, wt(bs) = 120.Функция bs представима в виде bs = gA ф h. Функцияg(x) = Ж2Ж6 ф Ж3Ж6 ф Ж1Ж2Ж3 ф Ж4Ж6 ф Ж1Ж4 ф Ж3Ж4 ф Ж3Ж4Ж6 ф Ж3Ж5 ф Ж4Ж5 ф Ж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.

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

cryptography, linear structures space, algebraic degenerated functions, nonlinearity of Boolean functions, криптография, пространство линейных структур, алгебраически вырожденные функции, нелинейность булевых функций

Авторы

ФИООрганизацияДополнительноE-mail
Алексеев Евгений КонстантиновичМосковский государственный университет им. М. В. Ломоносовааспирантgeni-cmc@mail.ru
Всего: 1

Ссылки

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.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях // Математические вопросы кибернетики. Вып. 11. М.: Физматлит, 2002. С. 91-148.
Dawson Е. and Wu C. K. Construction of correlation immune boolean functions // LNCS. 1997. V. 1334. P. 170-180.
Алексеев Е. К. О некоторых алгебраических и комбинаторных свойствах корреляционно- иммунных булевых функций // Дискретная математика. 2010. Т. 22. №3. С. 110-126.
Matsui M. Linear cryptanalysis method for DES cipher // LNCS. 1993. V. 765. P. 386-397.
Meier W. and Staffelbach O. Nonlinearity criteria for cryptographic functions // LNCS. 1990. V. 434. P. 549-562.
Siegenthaler T. Decrypting a class of stream chipher using ciphertext only // IEEE Trans. Computers. 1985. V. C-34. No. 1. P. 81-85.
 О некоторых мерах нелинейности булевых функций | ПДМ. 2011. № 2(12).

О некоторых мерах нелинейности булевых функций | ПДМ. 2011. № 2(12).

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