Получена верхняя оценка нелинейности векторных булевых функций, построенных из аффинных булевых функций. Построен пример функций, на которых оценка достижима. Получена нижняя оценка числа векторных функций с фиксированной нелинейностью, построенных из уравновешенных булевых функций.
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 конструктивно и может оказаться полезным, поскольку описывает метод построения функций с фиксированной нелинейностью.
Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 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.