Оглавление
Введение....................................... 3
1 Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций 13
2 Оценки окрестностей линейных кодов и вспомогательные оценки для сумм с биномиальными коэффициентами 21
2.1 Оценки окрестностей линейных кодов .... 22
2.2 Оценки для сумм с биномиальными
коэффициентами............................ 26
3 Оценки числа булевых функций, имеющих аффинные приближения заданной точности 34
3.1 Неравенства включения-исключения......... 37
3.2 Упрощенные оценки числа булевых функций 46
3.3 Верхняя оценка Атоп\г)................... 51
4 Оценки числа булевых функций, имеющих квадратичные приближения заданной точности 62
4.1 Неравенства включения-исключения......... 63
4.2 Упрощенные оценки числа булевых функций 69
2
Введение
Понятие булевой функции сформировалось во второй половине XIX века в работах одного из основоположников математической логики английского математика Джорджа Буля (G. Boole, 1815-1864). В первой половине XX века булевы функции приобрели фундаментальное значение для оснований математики. Вместе с тем длительное время булевы функции оставались невостребованными в прикладных областях.
Существенные изменения произошли в середине XX века, когда бурное развитие техники связи, приборостроения и вычислительной техники потребовало создания адекватного математического аппарата. В этот период происходит становление таких прикладных отраслей математики, как теория конечных функциональных систем, теория информации, теория кодирования и, наконец, теоретическая криптография.
Практика показала плодотворность применения аппарата теории булевых функций к проблемам анализа и синтеза дискретных устройств, осуществляющих обработку и преобразование информации.
Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование. Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем важна как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств
з
противоречит фундаментальным принципам построения криптографических систем.
Одной из мер нелинейности булевой функции / является величина ЛГ/, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций Ап.
С точки зрения теории кодирования множество аффинных функций представляет собой код Рида-Маллера первого порядка ЯМ(1, п), а значение N/ является верхней границей для радиуса покрытия кода йМ(1,п) (см. [9]). В случае четного п значение ./V/ в точности совпадает с радиусом покрытия кода ДМ(1,п). При нечётном п точное значение радиуса покрытия кода ЯМ( 1,п) известно лишь для некоторых значений п, а в остальных случаях имеются только его нижние и верхние оценки.
По аналогии с нелинейностью булевой функции / как расстояния до множества аффинных функций можно рассматривать также расстояние от / до множества булевых функций, представимых в виде многочленов второй степени (квадратичных функций).
В настоящей работе получены двусторонние оценки и асимптотические формулы для количеств булевых функций от п переменных, которые с заданной точностью аппроксимируются линейными, аффинными или квадратичными булевыми функциями. Используя термины теории вероятностей, можно сказать, что эти результаты описывают распределение расстояния от случайной равновероятной булевой функции до линейных, аффинных и квадратичных функций в области вероятностей больших уклонений. Доказана предельная
4
теорема для расстояния Хемминга между случайной равновероятной булевой функцией от п переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б.В. Рязанова для расстояния до множества линейных булевых функций.
Перейдём к более подробному изложению результатов диссертации.
Пусть F2 - поле из двух элементов. Для произвольного натурального числа п будем обозначать через Vn = Fg пространство //-мерных векторов с компонентами из F2. Между множеством F^n = {/ : Vn —> F2} всех булевых функций от п переменных и пространством V2n можно установить взаимно однозначное соответствие, отождествляя функцию / Є F^n с вектором {f{x)\ X Є Vn}.
Расстояние Хэмминга p(f,g) между булевыми
функциями /, дє¥12П определяется как число значений
переменной х Є Vn, при которых f(x) д{х). Для
произвольного множества булевых функций А С F^n и
функции / Є F^71 обозначим через p(f,A) = тіир(/, q)
дел
расстояние Хэмминга от / до ближайшей к ней функции из множества А.
В множестве F^n всех булевых функций естественно выделяются: класс линейных функций
L„ = {/ є ¥\п: f(xu ...,хп) =
== а>\Х\ ф ... ф о*пХfiy а\,..., сіл Є F2} 5
5
класс аффинных функций
А„ = {/ Є ¥^п: Дхь ...,хп) =
<20 ® &\СС\ Ф . . . ф &ПХП) (2-0? • ■ ■ ) &тг ^ ^2}
и класс квадратичных функций 0>П = {/ є ¥2": /(хь ...,хп) =
П
— bijXiXj ф ОіХі Ф ао, 6^, а* Є Р2 } ,
і=1
где ф — сложение в ¥2] очевидно. С Ап С <0>п. Мощности этих классов имеют следующий вид:
11*| = 2™, | Ап| = 2"+1 и | <®п\ = 2®+п+1.
Основным и результатами диссертации являются точные формулы и двусторонние оценки для чисел элементов множеств
Рг(!Ь„,г) = {/ Є ¥%п: />(/, Ьп) < г},
^(Ап.г) = {/ Є р(/, А„) ^ г},
ВД„,г) = {/е^":р(/^^г}
всех булевых функций от п переменных, расстояния от которых до множеств ЪП: Ап, (фп соответственно меньше или равны г. Известно [9], что Р2(Ап,г) = если г ^ 2^—1 2 п/2—і
При четном п функции, расстояние от которых до множества аффинных функций равно 2п~1 — 27г/2~1, назы ваются бейт-функциями или максимально-нелинейными функциями. Они, в частности, представляют
б
- Київ+380960830922