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

Понятие булевой функции сформировалось во второй половине XIX века в работах одного из основоположников математической логики английского математика Джорджа Буля (G. Boole, 1815−1864). В первой половине XX века булевы функции приобрели фундаментальное значение для оснований математики. Вместе с тем длительное время булевы функции оставались невостребованными в прикладных областях.

Существенные изменения произошли в середине XX века, когда бурное развитие техники связи, приборостроения и вычислительной техники потребовало создания адекватного математического аппарата. В этот период происходит становление таких прикладных отраслей математики, как теория конечных функциональных систем, теория информации, теория кодирования и, наконец, теоретическая криптография.

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

Как известно из практики математических исследований, линейность (в математическом смысле) изучаемого объекта упрощает его исследование. Линейность с успехом используется в алгебре, теории систем, математической кибернетике и других разделах математики. С другой стороны, для построения надёжных криптографических систем валена как раз нелинейность, а существование свойств, близких к свойствам линейных функций, считается слабостью. Наличие таких свойств противоречит фундаментальным принципам построения криптографических систем.

Одной из мер нелинейности булевой функции f является величина ТУ/, численно равная расстоянию (в метрике Хэмминга) от данной функции до множества аффинных функций ап.

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

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

В настоящей работе получены двусторонние оценки и асимптотические формулы для количеств булевых функций от п переменных, которые с заданной точностью аппроксимируются линейными, аффинными или квадратичными булевыми функциями. Используя термины теории вероятностей, можно сказать, что эти результаты описывают распределение расстояния от случайной равновероятной булевой функции до линейных, аффинных и квадратичных функций в области вероятностей больших уклонений. Доказана предельная теорема для расстояния Хемминга между случайной равновероятной булевой функцией от п переменных и множеством аффинных булевых функций от тех же переменных, дополняющая аналогичную теорему Б. В. Рязанова для расстояния до множества линейных булевых функций.

Перейдём к более подробному изложению результатов диссертации.

Пусть F2 — поле из двух элементов. Для произвольного натурального числа п будем обозначать через Уп = Е2 пространство п-мерных векторов с компонентами из ?2. Между множеством = {/: Уп —> ?2} всех булевых функций от п переменных и пространством У2п можно установить взаимно однозначное соответствие, отождествляя функцию / Е ¥-п с вектором {/(ж)| х Е Уп}.

Расстояние Хэмминга р (/, д) между булевыми функциями f1gE определяется как число значений переменной х Е Уп, при которых /(гг) Ф 9(х) — Для произвольного множества булевых функций, А С и функции / Е обозначим через р (/, А) = ттр^, д) дел расстояние Хэмминга от / до ближайшей к ней функции из множества А.

В множестве ¥-п всех булевых функций естественно выделяются: класс линейных функций ахх ф. 0 апХп, аь ., ап Е F2}, класс аффинных функций а0 0 ах 1 0. 0 апхп, а0,., G F2} и класс квадратичных функций п ф bijXiXj 0 (J) 0 а0, bij, ai <Е F2 }, 1 где 0 — сложение в F2- очевидно, Ln С Ап С Qn. Мощности этих классов имеют следующий вид: L"| =2″, | An| = 2n+1 и | Q"| = 2(«)+n+1.

Основными результатами диссертации являются точные формулы и двусторонние оценки для чисел элементов множеств.

F2(L", r) = {/eF[": p (/, LJ ^ г},.

F2(An, r) = {/ е p (J, К) < г}, F2(Qn, г) = {/ € F^": Q") s? г} всех булевых функций от п переменных, расстояния от которых до множеств Ln, АП} Qn соответственно меньше или равны г. Известно [9], что F2(An, r) = F^n, если г ^ 2^-12^/2—1.

При четном п функции, расстояние от которых до множества аффинных функций равно 2п~1 — 2П/2−1, называются бейт-функциями или максимально-нелинейными функциями. Они, в частности, представляют интерес для построения криптографических алгоритмов, стойких по отношению к методам, основанным на аппроксимации булевых функций линейными (см., например, [2], [8]). Однако даже асимптотика числа бент-функций до сих пор неизвестна.

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

Предельные теоремы для распределения расстояния между случайной булевой функцией и множеством линейных булевых функций доказаны в [5]. В частности, было показано, что если / 6 — случайная булева функция, имеющая равномерное распределение на то lim Р < Л = 1 — ух е К, (1).

П-+СО | Ъп где.

П1 —(1п 1×12п + 1п47г а" = 2 — ^ —ШЫ2-) '.

Ъп = (2).

В [10] доказаны предельные теоремы для распределения расстояния от случайной булевой функции до множества квадратичных булевых форм со свободным членом. В частности, в [10] показано, что для любого фиксированного х оо вп где п2 — Г 1 41п (тгп21п2)-1п2.

Л. = 2 — |1 + —пу1п2.

В главе 1 диссертации содержится доказательство теоремы, дополняющей результаты работ [5] и [10].

Теорема 1. Если / 6 — случайная булева функция, имеющая равномерное распределение на, то для любого фиксированного х Е К.

Цтр М, К)~ап<�хыЛ= (5).

П-* оо I Оп) где ап и Ъп определены в (2).

В частности, из результатов работы [5] следует, что если Е2(Ьп, г) — множество всех булевых функций, расстояние Хемминга от которых до множества линейных функций (аффинных с нулевым свободным членом) не превосходит г, то при п —> оо эир

0^г<2п—1 —2П/2−1 где х (п, г) определяется равенством г = 2п~1 — ^2п~1 (п Ь 2 — | 1п (4тггг 1п 2) + х (п, г)).

Это означает, что для основной массы булевых функций от п переменных расстояние до множества линейных функций при п —> оо имеет вид.

2п~1 — yj2п~1 (rcln2-§ Inn) +0 (v7^?^).

Сравнение (1) и (5) показывает степень увеличения окрестности множества Ап аффинных функций по сравнению с окрестностью множества Ln линейных функций.

Основным результатом главы 3 (объединение части формулировок теорем 8, 9, 10 и утверждений 3, 4) является следующие утверждение.

Теорема 2. Если п ^ 2, то г г.

1 — Q (n, r))2n+1 F2(An, r)| < 2™+1C?n,.

771=0 771=0.

Г Г.

1 — Q (n, r)) 2″ s? | F2(Ln, r) K 2″ .

772=0 m= 0 где Q (n, r) = О при 0 ^ r < 2n2- 4 1 o-icMV p^n)3/2).

Q (n, r)<-2 ^ ^exp|-^-| npun⁸, r = 2й-1 — cr/2n-1nln2 ^ 0, cv > 1.

Замечание 1. Неравенства теоремы 2 позволяют получать оценки для левого хвоста распределения расстояния от случайной булевой функции до множеств аффинных и линейных булевых функций.

Отношения верхних и нижних оценок в теореме 2 стремятся к 1, если га —> оо и г < 2п~1 — су/2п~1пп2, с > л/ЦЪ = 1,2247. г.

Для сумм при г ^ 27г~1 в главе 2 получены т=О явные верхние и нижние оценки. С их помощью, например, показано, что в области «больших уклонений» (где 1 —.

7*) е~е ' —> 0) относительная погрешность приближения м 77* к г у* 1 величины 2-" 1 |Р2(Ьп, г)| величиной 1 — е~е ' быстро растет с уменьшением г.

Следствие 1. Если с > 1 и п, г —> оо так, что выполняется условие г < 2п~1 — сл/2п~1п1п2, то при достаточно больших га.

22П — С.

Из результатов работы [10] (см. формулу (3)) следует, что если F2(QTг, r) — множество всех булевых функций, расстояние Хемминга от которых до множества квадратичных функций не превосходит г, то при га —> оо вир

0<�Г<2п-1−2″ /2−1/Ь2.

2″ 2>2(Отг)| - (1.

0,.

7) где ж (га, г) определяется равенством г- 2п~1−2?-1х х ^/га21п 2 + га 1п 2 — 21п га — 1п (тг1п2) + Ь <У2 + 2х (п, г). ю.

Это означает, что для основной массы булевых функций от п переменных расстояние до множества квадратичных функций при п —> оо имеет вид.

2п~1 — л/2″ -2 (п21п 2 + п 1п 2 — 21п п) + О ?2п/2/п) .

Основным результатом главы 4 (объединение части формулировок теорем 13, 14 и утверждения 5) является следующее утверждение.

Теорема 3. Если п ^ 3- то г г.

1 — <�Э (п, г))2®+п+1 < I г) I < 2(?)+" +1 Е т=О ш=О где (Э (гг, г) = 0 при О ^ г < 2п~г,.

2-^(с2З)/6+п+1 Г (сгП)3 1.

ХП>Г)<�—^—ехр7^/ прип^1Ъиг = 2п~1 — СгПл/ 2п~21п 2 > 0, о- > 1.

Замечание 2. Теорема 3 позволяет получать оценки левого хвоста распределения расстояния от случайной булевой функции до множества квадратичных булевых функций.

Отношения верхних и нижних оценок в теореме 3 стремятся к 1, если п -> оо и г < 2п~1 — сп/2п~21п2, с > л/3 = 1,7321.

С помощью верхних и нижних оценок для сумм г при г < 2п~1 показано, что в области «больших т=О уклонений» (где 1 — е~е ' —> 0) относительная погрешность приближения величины 22Гг|Е2(Оп, г)| г) величиной 1 — е~е ' быстро растет с уменьшением г.

Следствие 2. Если с > 1 и п, г —> оо так, что выполняется условие г < 2П1 — с д/2П~2 (п2 + га) 1п 2, то при достаточно больших п.

2(0″, г) I 1⁵.

22п.

В качестве упрощенных следствий результаты глав 1, 2, 3 и 4 можно записать в следующей форме.

Утверждение 1. Если га достаточно большое и г >

1п (4тгп 1п 2).

2п > 7710 р .РЫК)-** п.

С1 е—*Л л х I («1п (4тгп1п2)) '.

1 +.

21п2 ^ 2 п) о, рЦЛп) -ап Р < -Т1- < — 1п 2 > < а.

Л е-е-«Л.

1 .1 / 1п (47Г711п 2) у /'.

1 21п2 2п) 1п (тгп2 1п 2) если г > к 2п2—¿— то р. р{1,о") — к гп2 п.

1,5 / гп2' ~.

1. 1 (у 1п (7ГП2 1п 2) Л.

1 ^ 1п2 2п2 у где ап, Ьп, Нп, 5П определены в (2) и (4).

1 — е~е у ,.

1. Alfers D., Dinges H. A normal approximation for Beta and Gamma tail probabilities. — Z. Wahrscheinlichkeitstheorie verw. Gebiete, 1984, no. 65, pp. 399−420.

2. Carlet C. Boolean functions for cryptography and error correcting codes, 2006. http://www-rocq.inria.fr/codes/Claude.Carlet/chap-fcts-Bool.pdf.

3. Cusick T.W., Stanica P. Cryptographic Boolean Functions and Applications. — Elsevier, 2009.

4. McDiarmid Colin. Concentration. — Probabilistic Methods for Algorithmic Discrete Mathematics, 1998.

5. Ryasanov В. V. Probabilistic methods in the theory of approximation of discrete functions. — Probab. Meth. Dis-cr. Math., Proc. 3rd Int. Petrozavodsk Conf., TVP/VSP, Moscow, 1993, pp. 403−412.

6. Блейхут P. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

7. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. — М.: Наука, 1976.

8. Логачев О.А.- Сальников A.A., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004.

9. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов исправляющих ошибки. — М.: Связь, 1979.

10. Рязанов Б. В., Чечёта С. И. О приближении случайной булевой функции множеством квадратичных форм. — Дискретная математика., 1995, т. 7, № 3, с. 129−145.

11. Феллер В.

Введение

в теорию вероятностей и ее приложения, т.1. — М.: Мир, 1984.

12. Феллер В.

Введение

в теорию вероятностей и ее приложения, т.2. — М.: Мир, 1984.

13. Чечета С. И. О предельном распределении расстояния между случайным вектором и некоторыми двоичными кодами. — Проблемы передачи информации, 1995, т. 31, № 1, с. 90−98.Работы автора по теме диссертации.

14. Зубков A.M., Серов A.A. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Дискретн. матем., 2010, т. 22, К24, с. 3−19.

15. Серов A.A. Предельное распределение расстояния между случайной булевой функцией и множеством аффинных функций. — Теор. вер. и её прим., 2010, т. 55, № 4, с. 791−795.

16. Зубков A.M., Серов A.A. Оценки числа булевых функций, имеющих аффинные приближения заданной точности. — Обозрение прикладной и промышленной математики, 2009, т. 16, вып. 2, с. 337−339.