WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

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

Теоретическая и практическая ценность работы.

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

Апробация работы.

Результаты диссертации докладывались на следующих научноисследовательских семинарах и конференциях:

• Семинар "Булевы функции в криптологии"под руководством к.ф.-м.н.

О.А.Логачева и к.ф.-м.н., доцента Ю.В.Таранникова (2005-2009).

• Семинар "Математические вопросы кибернетики"под руководством д.ф.-м.н., профессора О.М.Касим-Заде (21 марта 2008).

• Вторая международная конференция по проблемам безопасности и противодействия терроризму (МГУ, 25-26 октября 2006).

• VI молодежная научная школа по дискретной математике и ее приложениям (Москва, 16-21 апреля, 2007).

• IX международный семинар "Дискретная математика и ее приложения" (Москва, 18-23 июня, 2007).

• Ежегодная научная конференция "Ломоносовские чтения"(МГУ, апрель 2007) • Международная конференция "NATO Advanced Study Institute on Boolean Functions in Cryptology and Information Security"(Звенигород, сентябрь 2007).

• XVII международная школа-семинар "Синтез и сложность управляющих систем"(Новосибирск, 27 октября - 1 ноября, 2008).

• Международная конференция "Современные проблемы математики, механики и их приложений"(Москва, 30 марта - 02 апреля, 2009).

Публикации.

Основное содержание диссертации было опубликовано в 8 работах, список которых приведен в конце автореферата [1] [8].

Структура и объем диссертации.

Диссертация состоит из введения, 6 глав и списка литературы. Объем диссертации 64 страницы, библиография включает 47 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе мы обсуждаем предварительные сведения и формулируем основные определения.

Определение 1. Алгебраической иммунностью AI(f) булевой функции n n f над F2 называется степень булевой функции g над F2, где g не равная тождественно нулю функция с минимальной степенью, такая что fg = 0 или (f + 1)g = 0.

Определение 2. Нелинейностью r-го порядка nlr(f) булевой функции f n над F2 называется min d(f, l). Нелинейностью nl(f) функции f называется deg(l)r расстояние между f и множеством аффинных функций, т. е. нелинейность первого порядка.

Вводится определение коэффициентов Уолша и раскрывается их связь с нелинейностью функции. Формулируется теорема об аффинной классификации квадратичных булевых функций.

Во второй главе проблема получения как можно более сильных нижних оценок нелинейности r-го порядка через значение алгебраической иммунности функции полностью сводится к задаче определения размерности некоторых подпространств Bk(h) = {g(x1,..., xn)| deg(g) k, deg(gh) k}.

Теорема 1 Пусть f(x1,..., xn) имеет AI(f) = k, тогда nlr(f) min dim(Bk-1(g)).

deg(g)r Кроме того, при k n существует функция f0, AI(f0) = k, для которой nlr(f0) = min dim(Bk-1(g)).

deg(g)r Теорема 1 позволяет получить в качестве простых следствий некоторые оценки других авторов. Например, оценку AI(f)-r- n nlr(f) i i=из работы группы индийских исследователей30, а также оценку AI(f)-r- n - r nlr(f) i i=из работы К.Карле31 и оценку, полученную независимо автором [3] и С.Менаже32:

AI(f)-r-1 AI(f)-r- n n - r nlr(g) +. (1) i i i=i=AI(f)-2r Но вместе с тем главное значение теоремы 1 в том, что она дает довольно хороший общий подход к проблеме, изучению которой посвящена диссертация. Этот подход будет неоднократно успешно использован в следующих главах.

Третья глава посвящена случаю обычной нелинейности nl(f). В главе доказана оценка AI(f)- n nl(f) = nl1(f) = min d(f, l) 2, (2) deg(l)1 i i=и построено семейство функций 0, если wt(x1,..., xn) < k, fn,k(x1,..., xn) = 1, если wt(x1,..., xn) > n - k, x1, если k wt(x1,..., xn) n - k, на которых оценка достигается при всех допустимых значениях параметров n и AI(f). А именно, доказано, что AI(fn,k) = k и k- n - nl(fn,k) = 2.

i i=Также в третьей главе мы доказываем следующее утверждение:

D.K.Dalai, K.C.Gupta and S.Maitra. Results on Algebraic Immunity for Cryptographically Significant Boolean Functions // Indocrypt 2004 (Chennai, India, December 20-22, 2004) Berlin/Heidelberg: Springer Verl., 2004. P. 92-106.

C.Carlet. On the higher order nonlinearities of algebraic immune functions // CRYPTO 2006.

Berlin/Heidelberg: Springer, 2006. P. 584-601. (Lecture Notes in Computer Science; Vol.4117).

S.Mesnager. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity. Cryptology ePrint archive(http://eprint.iacr.org/), Report 2007/117.

n Следствие 8. Пусть f(x1,..., xn) булева функция над F2 и AI(f) = k, n k, тогда равенство в неравенстве (2) может достигаться не более чем на одной линейной функции l.

Там же показываем, что для функции f2k+1, k+1 равенство в неравенстве (2) достигается сразу на нескольких линейных функциях l.

Четвертая глава посвящена получению оценки на нелинейность второго порядка.

В начале вводятся определения множества Sa,..., aq(k) и (a1,..., aq)бесповторного полинома:

Определение 6.

qПусть есть набор целых чисел a1 a2...

aq > 0, таких что ai n, тогда двоичному набору x = (x1,..., xn) i=длины n можно сопоставить набор из целых чисел: (s1(x),..., sq(x)) = a a +a2 a +...+aq 1 ( xi, xi,..., xi). Обозначим через Sa,..., aq(k) i=1 i=a1+1 i=a1+...+aq-1+1 множество двоичных наборов x длины n, таких что st(x) = 0 при некотором tx q, 0 < si(x) < ai при i < tx и также k - at < wt(x) k.

x Определение 7. Полином, в котором каждая переменная входит не более чем в один моном, будем называть бесповторным. Если полином имеет вид x1x2 · · · xa + xa +1 · · · xa +a2 + · · · + xa +...+aq-1+1 · · · xa +...+aq, 1 1 1 1 где a1 a2... aq, то будем его называть (a1,..., aq)-бесповторным.

Для бесповторного полинома доказана теорема, которая для довольно широкого класса функций сводит проблему вычисления размерности пространства Bk(f) к несложному комбинаторному подсчету:

Теорема 2 Пусть f(x1,..., xn) это (a1,..., aq)-бесповторный полином.

Тогда k n dim(Bk(f)) = - |Sa,..., aq(k)|.

i i=Известно33, 34, что любую квадратичную булеву функцию можно аффинным преобразованием перевести в функцию с бесповторным полиномом. Благодаря этому факту и теоремам 1 и 2, доказывается точная нижняя оценка на нелинейность второго порядка:

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

F.J.McWilliams, N.J.A.Sloane. The Theory of Error Correcring Codes. New York: North-Holland, 1977.

760 p.

Теорема 3 Пусть f(x1,..., xn) имеет AI(f) = k, тогда k-1 k- n n - 2i - nl2(f) - 2i. (3) i k - 1 - i i=0 i=Кроме того, при k n существует функция f0, AI(f0) = k, для которой k-1 k- n n - 2i - nl2(f0) = - 2i.

i k - 1 - i i=0 i=В пятой главе доказана оценка, которая является на настоящий момент рекордной для нелинейностей третьего и выше порядков:

Теорема 4 Пусть AI(g) = k, тогда k-r-1 k-r-1 k-r- n n - r n - r - nlr(g) + + 2. (4) i i i i=0 i=k-2r i=k-2r-Доказательство этой теоремы опирается на доказанное нами утверждение:

Утверждение 17. Пусть f(x1,..., xn) булева функция, deg(f) = k > 1. Тогда аффинными преобразованиями ее можно привести к многочлену, который будет содержать моном x1x2... xk и любой другой моном которого будет содержать не более чем k - 2 из переменных x1, x2,..., xk.

В шестой главе для конкретных значений n, AI(f) и r = 2 сравниваются оценки (1), (4) и (3). Из преведенных сравнений видно, что в случае нелинейности второго порядка оценка (3) заметно сильнее.

Также для конкретных значений n, AI(f) и r 3 сравниваются оценки (1) и (4). Оказывается, что вторая оценка существенно лучше.

Благодарности.

Автор выражает искреннюю благодарность своему научному руководителю кандидату физико-математических наук, доценту Юрию Валерьевичу Таранникову за постановку задач, постоянное внимание, многочисленные плодотворные обсуждения и помощь в работе.

Список публикаций по теме диссертации.

[1] М.С.Лобанов. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006.

Т. 18, вып. 3. С. 152-159.

[2] М.С.Лобанов. Точные соотношения между нелинейностью и алгебраической иммунностью // Дискретный анализ и исследование операций. 2008. Т. 15, вып. 5. С. 47-60.

[3] М.С.Лобанов. Оценка нелинейности высоких порядков булевой функции через значение ее алгебраической иммунности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 апреля, 2007). Часть 2. M.: Институт прикладной математики РАН, 2007. С. 11–16.

[4] М.С.Лобанов. Новый подход к оценке нелинейности высоких порядков булевой функции через значение ее алгебраической иммунности // Материалы IX международного семинара "Дискретная математика и ее приложения"(Москва, 18-23 июня, 2007). M.: Издательство механикоматематического факультета МГУ, 2007. С. 434-437.

[5] М.С.Лобанов. Новая нижняя оценка нелинейности высокого порядка через алгебраическую иммунность // Материалы XVII международной школы-семинара "Синтез и сложность управляющих систем"(Новосибирск, 27 октября - 1 ноября, 2008).

Новосибирск: Издательство института математики, 2008. С. 95-98.

[6] М.С.Лобанов. Об оценках нелинейности высоких порядков через алгебраическую иммунность // Материалы международной конференции "Современные проблемы математики, механики и их приложений"(Москва, 30 марта - 02 апреля, 2009). М: Издательство "Университетская книга", 2009. С. 395.

[7] М.С.Лобанов. Неулучшаемая оценка нелинейности функции через значение алгебраической иммунности // Материалы II международной конференции по проблемам безопасности и противодействия терроризму (МГУ, 25-26 октября 2006). М.: МЦНМО, 2007. С. 210-217.

[8] M.Lobanov. Tight bounds between nonlinearity and algebraic immunity of high orders // Boolean functions in cryptology and information security.

2008. IOS Press. P. 296-305. (NATO Science for Peace and Security Series D: Information and Communication Security - Vol. 18)

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»