О продолжении до бент-функций и оценке сверху их числа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/4

О продолжении до бент-функций и оценке сверху их числа

Булева бент-функция f от n переменных является продолжением булевой функции g от k < n переменных, если g является сужением f на фиксированную аффинную плоскость размерности k. Доказывается, что продолжение всегда существует, если k ^ n/2. Получена оценка сверху для числа продолжений. Оценка усиливается для случая k = n - 1, когда g является почти-бент-функцией. В результате мы улучшаем известные оценки сверху для числа бент-функций.

On the continuation to bent functions and upper bounds on their number.pdf Булева функция f: F^ ^ F2 от чётного числа переменных n называется бент-функцией, если |/(u)| = 2n/2 для всех u G F^. Здесь f - спектр Уолша - Адамара функции f: /(u)= Е x(f (x)+ x ■ u). Символ x под знаком суммы - это нетривиальный аддитивный характер F2: x(a) = = (-1)a, точка обозначает скалярное произведение векторов. Пусть Bn - множество всех бент-функций от n переменных. Точное значение |Bn| неизвестно уже для n = 10, более того, адекватное оценивание |Bn| как сверху, так и снизу остаётся трудной задачей (см. обсуждение в [1]). В настоящей работе нас интересуют оценки сверху. Обозначим B (d, n) = и напомним, что булева функция f однозначно представляется многочленом фактор-кольца F2[x i,... , xn]/(x2 - x1,... ,х"П - xn). Пусть deg f - степень многочлена. Наивная оценка сверху (так она названа в работе [2]) для |Bn| основана на том, что если f G Bn и n ^ 4, то deg f ^ n/2. Оценка имеет следующий вид: |Bn| ^ B(n/2,n) = 22n-1+(nn/2)/2 « 22n-1+2n^ Оценка может быть немного усилена: следует учесть условие 2 ^ deg f и вычесть из правой части 2n+ 1 -число аффинных функций. В [2] К. Карле и А. Клаппер нашли более серьёзное усиление: |Bn| ^ Bn/2/2-)i(1 + £n) + B(n/2 - 1,n), en = )-2 , справедливое для n ^ 6. Эта оценка считается лучшей на сегодняшний день. В [2], кроме ограничения на deg f, учитывается также спектральное строение бент-функций. Мы улучшаем оценку Карле - Клаппера. Теорема 1. При чётном n ^ 6 справедлива оценка |B,,| « c„ 2 ( B(n/2,n - - hn - 1} + B (n/2 - 1, n - 1)) , в которой cn = exp(-1/2 + 23/(18 ■ 2n-2))/^n, причём cn ^ c6 ~ 0,3706. Различные оценки сверху для |Bn| при малых n сведены в табл. 1. Точные значения |Вб| = 5425430528 и |BS| = 99270589265934370305785861242880 найдены в работах [3] и [4] соответственно. Таблица 1 n |Bn| Оценки сверху для |Bn| Наивная [2] Настоящая работа 2 8 4 896 2032 6 к, 232'3 242 238 236 8 к, 2106'3 2163 2152 2149 10 ? 2638 2612 2608 12 ? 22510 22453 22448 Метод оценивания основан на подсчёте числа продолжений булевой функции g от k < n переменных до бент-функций от n переменных. Функция f Е Bn является продолжением д, если g(yi,...,yk) = f (01_^10,уъ... ^k). n-k Другими словами, f - продолжение д, если д является сужением f на аффинную плоскость E = {(0,... ,0,у1,... ,yk)}. Выбор E здесь не имеет принципиального значения, можно зафиксировать любую другую плоскость размерности k. Пусть Bn(g) -множество всех функций f Е Bn, которые являются продолжениями д. При доказательстве теоремы 1 мы рассматривали функции д от n- 1 переменных, для которых Bn(g) = 0. Если g является подходящей, то значения g принадлежат множеству {0, ±2n/2} (и тогда g называется почти-бент-функцией) и, кроме этого, выполняется условие deg g ^ n/2. Для оценки числа подходящих функций g мы применили результаты работы [2]. Для оценки |Bn(g)| использована следующая лемма, доказанная с помощью техники работы [5]. Лемма 1. Пусть N - чётное, Sn - сумма N независимых случайных величин с равномерным распределением на {-1,1}. Для s = 0, ±2,..., ±N справедлива следующая оценка: P'SN = s]= ((N +Ns)/2)2-N « \\HNexp (-2N + 1N)• Лемма 1 имеет и самостоятельное значение. С её помощью можно оценивать (сверху) биномиальные коэффициенты, контролировать точность аппроксимации в локальной теореме Муавра - Лапласа. В нашем контексте лемма позволяет оценить вероятность того, что спектральный коэффициент случайной булевой функции принимает заданное значение. Оценку леммы 1 можно несколько улучшить, это улучшение потребуется в теореме 2. Речь идёт об оценке вида P[SN = s] ^ 2-aNs2-i3n, где aN и Pn настраиваются так, чтобы величина Yn = ^n + Pn/N была максимальной. При малых N оптимальные тройки (aN,@n, Yn) можно определить, решая задачи линейного программирования. Решения представлены в табл. 2. Таблица 2 N aN PN Yn 2 4 8 / 2 6 2 1 4/3 14/3 - log2 7 3/4 1/2 2/3 - 1 log2 7 « 0,3157 8 В общем случае из леммы 1 следует, что > log2 e + log2 п + log2 N - 1 23 log2 e Yn > 2N 18N2 ' С точки зрения теории бент-прямоугольников [6] величина |Bn(g)| -это число прямоугольников размерности (n - k) х k, у которых первая строка фиксирована - она заполнена значениями g. Учитывая ограничения на строки и столбцы бент-прямо-угольника (точнее, тождества Парсеваля для них), получаем следующий результат. Теорема 2. Для булевой функции g от k < n переменных справедлива оценка log2 |Bn(g)| ^ 2n (1 - Y2n-k)' Отметим, что оценка теоремы 2 с k = n - 1 несколько усиливается при доказательстве теоремы 1. Начиная c k = n/2 + 1, появляются функции g, которые нельзя продолжить до бент-функций. В этом можно убедиться, анализируя ограничения на столбцы бент-прямоугольника. Впрочем, оказывается, что Теорема 3. При чётном n любая булева функция от k ^ n/2 переменных может быть продолжена до бент-функции от n переменных. Теорему достаточно доказать для k = n/2. В этом случае с помощью биаффинной конструкции, предложенной в [7], можно построить бент-квадрат размерности k х k, все строки и столбцы которого являются аффинными перестановками значений g. Легко добиться, чтобы первая строка квадрата в точности совпадала с g.

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

бент-функция, число бент-функций, почти-бент-функция, аффинная плоскость, bent function, number of bent functions, near-bent function, affine plane

Авторы

ФИООрганизацияДополнительноE-mail
Агиевич Сергей ВалерьевичБелорусский государственный университеткандидат физико-математических наук, заведующий НИЛ проблем безопасности информационных технологий НИИ прикладных проблем математики и информатикиagievich@bsu.by
Всего: 1

Ссылки

Tokareva N. Bent Functions: Results and Applications to Cryptography. London, UK; San Diego, CA, USA: Academic Press, 2015.
Carlet C. and Klapper A. Upper bounds on the numbers of resilient functions and of bent functions // Proc. 23rd Symp. Inform. Theory. Louvain-La-Neuve, Belgium. 2002. P. 307-314.
Preneel B., Van Leekwijck W., Van Linden L., et al. Propagation characteristics of Boolean functions // EUR0CRYPT'90. LNCS. 1991. V.473. P. 161-173.
Langevin P. and Leander G. Counting all bent functions in dimension eight 99270589265934370305785861242880 // Des. Codes Cryptogr. 2011. V. 59. P. 193-205.
Szabados T. A Simple Wide Range Approximation of Symmetric Binomial Distributions. Preprint arXiv:1612.01112 [math.PR]. 2016.
Agievich S. On the representation of bent functions by bent rectangles // Probabilistic Methods in Discrete Mathematics: Fifth Intern. Conf. (Petrozavodsk, Russia, June 1-6, 2000). Utrecht, Boston: VSP, 2002. P. 121-135.
Agievich S. Bent rectangles // Proc. NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security (Moscow, September 8-18, 2007). Amsterdam: IOS Press, 2008. P. 3-22.
 О продолжении до бент-функций и оценке сверху их числа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/4

О продолжении до бент-функций и оценке сверху их числа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/4