Оценки нелинейности векторных булевых функций специального вида | ПДМ. Приложение. 2014. № 7.

Оценки нелинейности векторных булевых функций специального вида

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

Nonlinearity bounds for vectorial boolean functions of special form.pdf Векторные булевы функции, используемые в криптографических приложениях, должны обладать рядом специальных свойств для обеспечения стойкости к известным видам криптоанализа и иметь относительно простую структуру [1-3]. Задачи совмещения различных свойств функции, а также оценки числа функций с выделенными свойствами являются сложными. Данная работа посвящена изучению нелинейности векторных булевых функций при относительно простом способе их построения и совмещению свойств нелинейности и уравновешенности. Булевой функцией от n переменных называется функция, действующая из Zn в Z2. Каждая булева функция однозначно задается своей алгебраической нормальной форn мой (АНФ), т.е. представляется в виде f(x) = I ф ф а^,...,^xil ■ ... ■ xik I ф а0, где yfc=1 ii.....ik J {i1,...,ik} С {1,...,n} и а^,...,^, а0 Е Z2. Степенью degf булевой функции f называется число переменных в самом длинном слагаемом её АНФ. Булева функция называется аффинной, если её степень не превосходит 1. Множество всех аффинных функций от n переменных обозначим через An. Нелинейностью булевой функции / : Zn ^ Z2 называется число N/(/) = dist(/, An), где dist(•, •) -расстояние Хэммин-га между булевыми функциями. Векторной булевой функцией называется функция вида F : Zn ^ Zmm. Нелинейностью векторной булевой функции F : Zn ^ Zm, где n F = (fi, /2,..., fm), называется число N/(F) = min dist I ф bi/i, An 22 поскольку lim (2n-i - 2(n-i)/2 - 2n-2) = го и lim -n-2- = 2. То есть макси- OtZ2 yi=i Для нелинейности векторной булевой функции от n переменных имеется та же верхняя оценка, что и в случае обычной булевой функции: N/(F) ^ 2n-i - 2n/2-1. При m ^ n - 1 данная оценка была улучшена В. М. Сидельниковым [4]. Для класса векторных булевых функций, построенных из аффинных, найдена следующая оценка нелинейности. Теорема 1. Пусть Fi = (/и, ... , fim) и F2 = (/2i,... , /2m) - функции, действующие из Zn-i в Zm, и /ij - аффинные функции для всех i = 1, 2, j Е {1,..., m}. Тогда для функции F : Zn ^ Zm, определённой правилом F(x, 0) = Fi(x), F(x, 1) = F2(ж) для каждого x Е Zn-i, справедлива оценка N/(F) ^ 2n-2, причём при m ^ n/2 данная оценка достижима. Пусть (n - 1, т)-функция F = (/i,... ,/m) с аффинными координатными функциями задаётся двоичной (n х т)-матрицей A(F) = (aij), где aij получены из АНФ n- i соответствующих функций /j(xl, ... ,xn-i) = ф aijxi ф anj. Тогда при m ^ n/2 оценi=i / a ка из теоремы 1 достижима на (n - 1, m)-функциях с матрицами A(Fl) = ( 0 A(F2) = ^ BB ^ , где A и B - (m х m)-матрицы полного ранга. Полученная в теореме 1 оценка нелинейности векторных булевых функций, построенных из аффинных булевых функций, слаба по сравнению с известными оценками, 2n-i _ 2(n-i)/2 n-^^о n-^^о 2n мум нелинейности функций из описанного класса приблизительно в 2 раза меньше максимально возможного значения нелинейности. Это позволяет сделать вывод, что в данном классе нет функций с хорошими нелинейными свойствами. Булева функция / : Zn ^ Z2 называется уравновешенной, если она принимает значения 0 и 1 одинаково часто. Рассмотрим множество векторных булевых функций F : Zn ^ Zn, F = (/i,... , /n), для которых каждая /i уравновешенная. Обозначим это множество Sbn. Через N (t, n) обозначим число векторных булевых функций от n переменных из класса Sbn с нелинейностью равной t. Для N (t, n) имеет место следующая оценка. Теорема 2. Если n и k удовлетворяют неравенству k ^ 2n-2/(n + 2), то справедлива оценка n , n \ / sn W t \ sn! N(2k, n) ^ 42n - 1) V2n-V \2n-i - sn/ (s!)n' где s = |~k/2]; t = k - s. Приведём таблицу значений верхней границы оценки Сидельникова [4] для нелинейности (n, ^-функций при малых значениях n (табл. 1). Для тех же значений n приведём таблицу нижних оценок числа (n, ^-функций с нелинейностью € для подходящих параметров t из теоремы 2 (табл. 2). Таблица 1 n 5 6 7 Nl 12 26 56 Таблица 2 е \ n 5 6 7 2 236 2ЬЬ 278 4 - 283 2Ш 6 - - 21Ьи > 0 2145 2364 2868 Известно, что для нечётных n оценка Сидельникова точна на классе AB-функций, причём AB-функции существуют при всех нечётных n. Из табл. 2 видно, что оценка, полученная в теореме 2, применима только к значениям нелинейности, далёким от максимальных. Однако доказательство теоремы 2 конструктивно и может оказаться полезным, поскольку описывает метод построения функций с фиксированной нелинейностью.

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

векторная булева функция, нелинейность, аффинная функция, уравновешенность, vectorial Boolean function, nonlinearity, affine function, balancedness

Авторы

ФИООрганизацияДополнительноE-mail
Корсакова Екатерина ПавловнаНовосибирский государственный университетмагистрантка механико-математического факультетаkorsakova.katerina@gmail.com
Всего: 1

Ссылки

Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
Панкратова И. А. Булевы функции в криптографии: учеб. пособие. Томск: Издательский Дом Томского государственного университета, 2014. 88 с.
Carlet C. Boolean functions for cryptography and error-correcting codes // Boolean Models and Methods in Mathematics, Computer Science, and Engeneering / eds. P. Hammer, Y. Crama. Cambridge Univ. Press, 2010. Ch.8. P. 257-397. www.math.univ-paris13.fr/~carlet/
Сидельников В. М. О взаимной корреляции последовательностей // Проблемы кибернетики. 1971. Т. 24. С. 15-42.
 Оценки нелинейности векторных булевых функций специального вида | ПДМ. Приложение. 2014. № 7.

Оценки нелинейности векторных булевых функций специального вида | ПДМ. Приложение. 2014. № 7.