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

• Автор: Серов, Александр Александрович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 87 с.

Оглавление
Введение
1 Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций
2 Оценки окрестностей линейных кодов и вспомогательные оценки для сумм с биномиальными коэффициентами

2.1 Оценки окрестностей линейных кодов

2.2 Оценки для сумм с биномиальными

коэффициентами

3 Оценки числа булевых функций, имеющих аффинные приближения заданной точности

3.1 Неравенства включения-исключения

3.2 Упрощенные оценки числа булевых функций

3.3 Верхняя оценка (г)

4 Оценки числа булевых функций, имеющих квадратичные приближения заданной точности
4.1 Неравенства включения-исключения
4.2 Упрощенные оценки числа булевых функций

Введение
Понятие булевой функции сформировалось во второй половине XIX века в работах одного из основоположников математической логики английского математика Джорджа Буля (G. Boole, 1815-1864). В первой половине XX века булевы функции приобрели фундаментальное значение для оснований математики. Вместе с тем длительное время булевы функции оставались невостребованными в прикладных областях.
Существенные изменения произошли в середине XX века, когда бурное развитие техники связи, приборостроения и вычислительной техники потребовало создания адекватного математического аппарата. В этот период происходит становление таких прикладных отраслей математики, как теория конечных функциональных систем, теория информации, теория кодирования и, наконец, теоретическая криптография.
Практика показала плодотворность применения аппарата теории булевых функций к проблемам анализа и синтеза дискретных устройств, осуществляющих обработку и преобразование информации.
Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование. Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем важна как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств

противоречит фундаментальным принципам построения криптографических систем.
Одной из мер нелинейности булевой функции / является величина Nf, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций Ап.
С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка НМ{ 1, п), а значение АД является верхней границей для радиуса покрытия кода ЯМ(1,п) (см. [9]). В случае четного п значение АД в точности совпадает с радиусом покрытия кода ЙМ(1,гг). При нечётном п точное значение радиуса покрытия кода ЯМ{1,п) известно лишь для некоторых значений гг, а в остальных случаях имеются только его нижние и верхние оценки.
По аналогии с нелинейностью булевой функции / как расстояния до множества аффинных функций можно рассматривать также расстояние от f до множества булевых функций, представимых в виде многочленов второй степени (квадратичных функций).
В настоящей работе получены двусторонние оценки и асимптотические формулы для количеств булевых функций от п переменных, которые с заданной точностью аппроксимируются линейными, аффинными или квадратичными булевыми функциями. Используя термины теории вероятностей, можно сказать, что эти результаты описывают распределение расстояния от случайной равновероятной булевой функции до линейных, аффинных и квадратичных функций в области вероятностей больших уклонений. Доказана предельная

поэтому

p(li, lj) = 2ra_1, если г ф j, {г, j} ф (J {2к, 2к + 1}. к=
(3.1)
Считая равными 0 суммы, в которых верхний предел суммирования меньше нижнего, введем обозначения
S(a,b)= <%-2C*U g,h> 0:
g+h^a, д—h^b
IV® (г) =
г-2"-2 г
= Е Е С%п-2 С^п-2 S(r — и,г + и — 2v — 211-1).
11=0 И=2П—Х—r+2w
(3.2)
Теорема 8. а) Если 0 ^ г < 2П-1 — 2п^2~1, то |F2(Amr)| ^2n+1N$(r),
2n+1N$(r) - 4 C2nN$(2n-r) < | F2(An, r)| < (3.3)
< 2п+1Л$}(г) - 4 CfniV^"-1, r) + 8 ClnN$(r).
b) Если 0 ^ r < 2n~2; mo | F2(An, r)| = 2n+1A^«^(r')-
c) Если 2n~2 ^ r < 2n_2 + 2n_4, 7720 |F2(An,r)| равно правой части последнего неравенства в (3.3).
Теорема 9. а) Если 0 < г < 2”“1 - 2п/2~1, то |F2(L„,r)| 2"JV(r),
2"ЛГ(г) - ClNg>(2n-r) -С |F2(JL„,r)| Ä (3.4)
« 2п Ny) (г) - C},N$(T~l,r) + C)„Ny)(r).