авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Исследование криптографических параметров, близких к нелинейности, для булевых функций

Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

На правах рукописи

Омаров Рустам Рамазанович Исследование криптографических параметров, близких к нелинейности, для булевых функций 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2013

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный консультант: доктор физико-математических наук, профессор Алексеев Валерий Борисович.

Официальные оппоненты: доктор физико-математических наук, профессор Леонтьев Владимир Константинович;

кандидат физико-математических наук Таранников Юрий Валерьевич.

Ведущая организация: Национальный исследовательский университет Mосковский энергетический институт.

Защита диссертации состоится 12 апреля 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государ ственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознако миться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан марта 2013 г.

Ученый секретарь диссертационного совета профессор Н.П. Трифонов

Общая характеристика работы

Актуальность темы. Работа относится к теории дискретных функций.

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

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

Наиболее известным примером дискретных функций являются булевы функции. Они находят широкое применение в электронных вычислитель ных и управляющих системах, играют важную роль при передаче инфор мации. В криптографии они используются при конструировании различ ных криптографических объектов (шифры, хэш-функции и т.п.). Основ ной целью, преследуемой разработчиком таких объектов, например, шиф ров, является максимальное затруднение их анализа противником. Раз витие методов криптографического анализа привело к выделению ряда свойств, важных с криптографической точки зрения. Наличие этих свойств у функций необходимо, чтобы криптографические схемы, построенные с их использованием, успешно противостояли различным методам анализа, на пример статистическому, корреляционному, дифференциальному, линейно му1,2,3,4,5. К таким свойствам можно отнести нелинейность и устойчивость Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В., Основы криптографии, М.:Гелиос, Ассоциация российских ВУЗов, 2001. 479 c.

Бабаш А. В., Шанкин Г. П., Криптография, М.: Солон-Р, 2007. 512 c.

Biham E., Shamir A., Dierential cryptanalysis of DES-like cryptosystems// J. Cryptology, 1991. V. 4, N 1. 3–72.

Courtois N., Meier. W., Algebraic attacks on stream ciphers with linear feedback // Advances in cryptology, EUROCRYPT 2003. - Berlin/Heidelberg: Springer Verl., 2003. 345–359. (Lecture Notes in Computer Science;

V. 2656).

Matsui M., Linear cryptanalysis method for DES cipher // Advancesin Cryptology - EUROCRYPT’93.

Workshop on the theory and application of cryptographic techniques (Lofthus, Norway. May 23-27, 1993), булевой функции, корреляционную и алгебраическую иммунности. Еже годно публикуются десятки работ, посвещенных изучению этих парамет ров, а также связей между ними6,7,8,9.

В ряде методов криптографического анализа существенно используется близость“ криптографических функций к функциям, обладающим про ” стой структурой с хорошо изученными свойствами. Примером таких пло ” хих“ функций служат аффинные функции (в дискретной математике их обычно называют линейными). Мерой удаленности булевой функции от класса аффинных функций является ее нелинейность. Множество функ ций, для которых нелинейность принимает максимально возможное значе ние, называется множеством максимально-нелинейных функций. Известно, что при четных n нелинейность булевой функции от n переменных ограни чена величиной Nf 2n1 2n/21, причем для максимально-нелинейных функций это неравенство обращается в равенство.

Наличие у булевой функции свойств, близких к линейным, говорит об определенной простоте“ этой функции, что облегчает исследование дру ” гих ее параметров и свойств. Поэтому возникает практическая необходи мость в построении функций, обладающих высокой или даже максимально возможной нелинейностью10,11,12,13. Несмотря на то, что уже построено до вольно много классов максимально-нелинейных функций, не удается опи сать класс всех максимально-нелинейных функций. Более того, не получе но близких верхних и нижних оценок на мощность этого класса. Однако, Proc. Berlin: Springer, 1994. 386–397 (Lecture Notes in Comput. Sci. V. 765).



Лобанов М. С., Точное соотношение между нелинейностью и алгебраической иммунностью// Дискретная математика, Изд-во Наука, Москва, 2006, Т. 18, вып. 3. 152–159.

Таранников Ю. В., О корреляционно-иммунных и устойчивых булевых функциях // Математиче ские вопросы кибернетики. Вып. 11, М.: Физматлит, 2002. 91–148.

Dalai D. K., Gupta K. C., Maitra S., Results on algebraic immunity for cryptographically signicant Boolean functions// Progress in Cryptology: INDOCRYPT’04, LNCS V. 1880, Springer-Verlag, 2004. 92– 106.





Sarkar P., Maitra S., Nonlinearity bounds and constructions of resilient Boolean functions// CRYPTO’2000, LNCS V. 1880, Springer-Verlag, 2000. 515–532.

Халявин А. В., Построение 4-корреляционно-иммунных булевых функций от 9 переменных с нели нейностью 240 // Материалы X Международного семинара Дискретная математика и ее приложе ния, Изд-во мех.-мат. факультета МГУ, Москва, 2010. 534–537.

Carlet C., Two new classes of bent functions// Workshop on the theory and application of cryptographic techniques on Advances in cryptology, January 1994, Lofthus, Norway. 77–101.

Rodier F., Asymptotic nonlinearity of Boolean functions // Designs, Codes and Cryptography, V. 40, N. 1, 2006. 59–70.

Tarannikov Y., New Constructions of Resilient Boolean Functions with Maximal Nonlinearity// Revised Papers from the 8th International Workshop on Fast Software Encryption, April 02-04, 2001., 66–77.

имеется большое число результатов в этом направлении14,15,16.

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

Эту проблему удается частично разрешить. Например, имеются результа ты по рекурсивным оценкам на нелинейность порядка r17, а также оценки на нелинейность через другие параметры функции18,19.

Высокая нелинейность булевой функции означает, что она плохо прибли жается аффинными функциями. Однако в принципе может оказаться, что данную функцию удастся хорошо приблизить почти аффинной“ булевой ” функцией. Например, наряду с нелинейностью, исследуется расстояние до множества функций, обладающих нетривиальными линейными структура ми20 ( булева функция обладает нетривиальной линейной структурой, если существует ненулевой вектор a, такой что f (x) f (x a) = const). Так же исследовалось расстояние до множества k-аффинных функций21 (при k = 0 это множество состоит из некоторого числа аффинных и квадра тичных функций). В качестве плохих“ функций можно рассматривать и ” другие классы функций, например алгебраически вырожденные функции (функция f называется алгебраически вырожденной, если ее можно пред ставить в виде f (x) = g(Ax), где A некоторая матрица, а g функция от меньшего числа переменных).

Анализ конкретных криптографических объектов часто приводит к ре Agievich S. V., On the representation of bent functions by bent rectangles // Fifth Int. Petrozavodsk conf.

on probabilistic methods in discrete mathematics. Proc. Boston: VSP, 2000. 121–135.

Carlet C., Klapper A., Upper bounds on the numbers of resilient functions and of bent functions // 23rd Symposium on Information Theory (Benelux, Belgium. May, 2002). Proc. 2002. 307–314.

Tokareva N. N., On the number of bent functions from iterative constructions: lower bounds and hypotheses // Advances in Mathematics of Communications (AMC), 2011, V. 5, N 4. 609–621.

Carlet C., Recursive lower bounds on the nonlinearity prole of Boolean functions and their applications// IEEE Transactions on Information Theory, V. 54, N. 3, 2008. 1262–1272.

Лобанов М. С., Точные соотношения между нелинейностью и алгебраической иммунностью// Дискретная математика и исследование операций, Изд-во Наука, Москва, 2008, Т. 15, вып. 6. 34–47.

Лобанов М. С., Получение нижних оценок на нелинейность булевой функции через размерность некоторых подпространств, Материалы X Международного семинара Дискретная математика и ее приложения, Изд-во мех.-мат. факультета МГУ, Москва, 2010. 416–419.

Meier W., Staelbach O. Nonlinearity criteria for cryptographic functions // LNCS. 1990. V. 434. 549– 562.

Токарева Н. Н. Сильно нелинейные булевы функции: бент-функции и их обобщения. Диссертация на соискание ученой степени кандидата физико-математических наук, Новосибирск, 2008.

Алексеев Е. К., Аппроксимация дискретных функций алгебраически вырожденными функциями в анализе систем защиты информации. Диссертация на соискание ученой степени кандидата физико математических наук, Москва, 2011.

шению систем булевых уравнений вида a f (1, x) = c1,...

f (m, x) = cm ;

a для некоторого неизвестного вектора x. Для произвольной булевой функ ции f такие системы плохо решаются. Предположим, что для некоторой булевой функции g(, x) с достаточно большой вероятностью выполняет a ся равенство f (, x) = g(, x), тогда с определенной вероятностью будет a a выполняться система равенств g(1, x) = c1, a...

g(m, x) = cm.

a Если функция g – аффинная относительно x, то получим линейную систе му, которая быстро решается, и мы с определенной вероятностью находим решение исходной системы. Однако решение можно быстро найти и в тех случаях, когда функция g в своем полиноме Жегалкина содержит не бо лее k нелинейных слагаемых. Заменяя каждый моном вида xi1... xis на соответствующую переменную ui1,...,is, мы придем к некоторой линейной системе. Если исходная нелинейная система содержала n неизвестных, то полученная линейная система будет содержать не более n + k неизвестных.

При фиксированном k сложность решения такой линейной системы будет O(n3 ). Находя решения этой линейной системы и проверяя их на необхо димую связь между переменными, мы с некоторой вероятностью можем быстро получить решение исходной системы.

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

Целью диссертационной работы является исследование расстояния от класса максимально-нелинейных функций до класса функций, у кото рых в полиноме Жегалкина присутствует не более фиксированного числа k нелинейных слагаемых.

Методы исследования. При выполнении диссертационного исследо вания использовались методы дискретной математики и алгебры.

Научная новизна. Все результаты диссертации являются новыми. А именно, изучен новый параметр – расстояние от максимально-нелинейных булевых функций до класса всех функций, у которых в полиноме Жегал кина присутствует не более фиксированного числа k нелинейных слага емых. Для минимума этого расстояния по множеству всех максимально нелинейных булевых функций от 2n переменных при произвольном k по лучены близкие нижние и верхние оценки. При k = 1 получена точная формула. Для функций из класса Мэйорана–Мак-Фарланда при k = 1 по лучены точные границы, в которых изменяется это расстояние. При k = получена точная формула для минимума этого расстояния по множеству всех максимально-нелинейных булевых функций от 2n переменных из клас са Мэйорана–Мак-Фарланда.

Достоверность полученных в диссертации результатов обусловлена строгостью математических доказательств, использованием апробирован ных научных методов и средств.

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

Соответствие диссертации паспорту научной специальности.

Диссертация соответствует паспорту специальности 01.01.09, поскольку ис следования в ней относятся к научному направлению Дискретная мате матика.

Апробация результатов. Результаты, полученные в диссертации, до кладывались и обсуждались на международных конференциях: Х между народном семинаре Дискретная математика и её приложения (Москва, 2010), VIII международной конференции Колмогоровские чтения (Яро славль, 2010), XVI международной конференции Проблемы теоретиче ской кибернетики (Нижний Новгород, 2011), ХI международном семинаре Дискретная математика и её приложения (Москва, 2012).

Кроме того, результаты обсуждались на научном семинаре Дискрет ная математика и математическая кибернетика кафедры математической кибернетики факультета ВМК МГУ.

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

2 из них опубликованы в журналах из списка ВАК.

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

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии, включающей 29 наименований.

Общий объем диссертации составляет 75 страниц.

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

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

Пусть n - произвольное натуральное число. Через Vn будем обозначать векторное пространство наборов длины n с компонентами из {0, 1} с опе рацией покоординатного сложения векторов по модулю 2. Под булевой функцией от n переменных будем понимать отображение f : Vn {0, 1}.

Ее весом wt(f ) будем называть количество наборов, на которых она рав на 1. Расстоянием от булевой функции f до булевой функции g на зывается величина dist(f, g) = wt(f g), т.е. число наборов, на кото рых значения функций f и g различаются. Расстоянием от f до мно жества M булевых функций от n переменных называется величина dist(f, M ) = min dist(f, g). Под расстоянием между двумя множествами gM булевых функций M и N будем понимать dist(M, N ) = min dist(g, h).

gM hN Пусть x и y – два произвольных вектора из Vn. Через x, y будем обо значать их скалярное произведение над полем GF (2) с двумя элементами 0 и 1: x, y = x1 y1... xn yn (здесь – это сложение по модулю 2). Бу лева функция f от n переменных называется аффинной, если существуют a = (a1,..., an ) Vn и c {0, 1} такие, что f (x) = a, x c. Множество всех аффинных булевых функций от n переменных будем обозначать An.

Расстояние dist(f, An ) от булевой функции f (x) от n переменных до множе ства An аффинных булевых функций называется нелинейностью функции f (x) и обозначается через Nf.

Булевы функции f (x), для которых Nf равно максимально возможному значению среди всех функций от n переменных, называют максимально нелинейными функциями (в случае четного n это расстояние равно Nf = 2n1 2n/21 ). Множество таких функций будем обозначать через Bn.

Далее рассматривается множество приближающих функций, у которых в полиноме Жегалкина присутствует не более k нелинейных слагаемых.

k Определение. Через AEn будем обозначать класс всех почти аффинных функций от n переменных, а именно, функций вида XI1...XIk l(x), где XIt = xj, It – произвольные подмножества (возможно, пустые: X = 0) jIt множества {1,..., n}, t = 1, k и l(x) An. При k = 1 будем писать AEn.

k Введем следующую функцию k (U ) = dist(U, AE2n ), где U некоторое множество функций от 2n переменных. В следующей теореме получена нижняя оценка для расстояния между классом максимально-нелинейных k функций от 2n переменных и множеством приближающих функций AE2n.

Теорема 1. Пусть B2n множество всех максимально-нелинейных функций от 2n переменных, тогда k (B2n ) 22n1 3k · 2n1.

Возникает вопрос, насколько оценка из теоремы 1 точна. Оказывается для некоторого известного класса максимально-нелинейных функций уда ется ответить на этот вопрос.

Определение. Пусть x = (x1,..., xn ), y = (y1,..., yn ). Класс Мэйорана– Мак-Фарланда определяется как класс всех булевых функций f (x, y) от 2n переменных вида f (x, y) = (y), x (y), где – произвольная под становка на множестве Vn, а (y) – произвольная булева функция от n переменных. Будем обозначать его через M2n.

Для класса Мэйорана–Мак-Фарланда удается доказать следующие два утверждения.

Теорема 2. При любом k 0 и n = pk + t, 0 t k выполняется:

k 2n1 k · 2n1.

k (M2n ) 2 3 · 3 · 2p Следствие 1. При любом фиксированном k и n выполняется:

k (M2n ) 22n1 3k · 2n1 + o(2n1 ).

С учетом того, что k (B2n ) k (M2n ), из теоремы 1 и следствия 1 по лучаем.

Теорема 3. При любом фиксированном k и n выполняется:

k (B2n ) = 22n1 3k · 2n1 + o(2n1 ).

Теорема 4. При любом фиксированном k и n выполняется:

k (M2n ) = 22n1 3k · 2n1 + o(2n1 ).

k Легко заметить, что, в отличие от класса An, класс AEn не является замкнутым относительно невырожденных афинных преобразований. По этому интерес также представляет исследование расстояния до класса, со k держащего все функции из AEn, а также все функции, аффинно эквива k лентные им. В частности, интересно, сохранятся ли полученные для AEn оценки?

k Определение. Через AE n будем обозначать класс всех функций, аффин k но эквивалентных функциям из класса AEn, а именно, функций вида k g(Ax d), где g AEn, A произвольная невырожденная над полем GF (2) матрица размера n n, а d Vn произвольный вектор и вы числение Ax d производится в поле GF (2). При k = 1 будем писать AE n = AE n.

k Определим функцию k (U ) как k (U ) = dist(U, AE 2n ), где U некото рое множество функций от 2n переменных.

Следующая теорема говорит о том, что добавление к функциям класса AE k всех функций, аффинно эквивалентных им, не сокращает расстояние 2n k от класса B2n до приближающего класса AE 2n по сравнению с k (B2n ).

Теорема 5. Для множества максимально-нелинейных функций Bn верно k (Bn ) = k (Bn ) и, следовательно, при любом фиксированном k и n k (B2n ) = 22n1 3k · 2n1 + o(2n1 ).

В первой главе мы попытались ответить на вопрос: Как изменится рас k стояние между классами B2n и A2n, если перейти от последнего к AE2n или k AE 2n. К сожалению, класс B2n полностью не описан, что затрудняет по лучение точного значения. Но для малого значения параметра k и класса максимально-нелинейных функций M2n удается получить точный ответ.

Во второй главе получена точная формула для расстояния от классов B2n и M2n до классов AE2n и AE 2n при всех n.

Теорема 6. Для класса всех максимально-нелинейных функций B2n при всех n 2 выполняется равенство:

1 (B2n ) = 22n1 3 · 2n1 + 2.

(При n = 1 1 (B2n ) = 0.) Примером максимально-нелинейной функции, для которой 2n1 n 3·2 + 2 служит f (x, y) = x, y y dist(f, AE2n ) =... yn sg(y1,..., yn ), где sg(0,..., 0) = 0 и sg(y1,..., yn ) = 1, если (y1,..., yn ) = (0,..., 0).

Следствие 2. Для класса максимально-нелинейных функций M2n при всех n 2 выполняется равенство:

1 (M2n ) = 22n1 3 · 2n1 + 2.

(При n = 1 1 (M2n ) = 0.) Доказательство следует из того факта, что указанная выше f (x, y) M2n.

Класс M2n не является инвариантным относительно невырожденных аффинных преобразований.

k Определение. Обозначим через H2n множество функций от n перемен ных вида:

h(x) = f (l1 (x),..., l2n (x)), где li A2n, i = 1, 2n, f (x) AE k.

2n k k k Заметим, что AE 2n H2n и dist(M2n, H2n ) k (M2n ).

Следствие 3. Для класса максимально-нелинейных функций M2n при всех n 2 выполняется равенство:

dist(M2n, H2n ) = 22n1 3 · 2n1 + 2.

При n = 1 dist(M2n, H2n ) = 0.

Также удается показать, что не все максимально-нелинейные функции одинаково хорошо приближаются функциями из AE 2n.

Теорема 7. Для любой максимально-нелинейной функции f (x) B2n вер но неравенство:

dist(f, AE2n ) 22n1 2 · 2n1, причем при всех n 2 существуют максимально-нелинейные функции от 2n переменных, для которых это неравенство обращается в равен ство.

Более того, теорема 7 останется верной, если от AE2n перейти к AE 2n.

Теорема 8. При всех n 2 существуют максимально-нелинейные функ ции от 2n переменных, для которых dist(f, AE 2n ) = 22n1 2 · 2n1.

В третьей главе исследуется расстояние между классом максимально нелинейных функций M2n и классом почти“ линейных функций AE2n.

” Получена точная формула для этого расстояния при всех n. Показано, что существуют функции, расстояние от которых до класса AE2n заведомо не достигает этой величины.

Теорема 9. Верно равенство:

n n 2 (M2n ) = 22n1 9 · 2n1 + 6 2 + 2 при n 6. При n = 1, 2, 3, 4, 5 величина 2 (M2n ) равна 0, 0, 16, 88, 416 со ответственно.

Теорема 10. При всех n 2 существуют максимально-нелинейные функции от 2n переменных, для которых dist(f, AE2n ) = 22n1 4 · 2n1.

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

Установлено, что это расстояние уменьшается по сравнению с нели нейностью рассматриваемых функций на величину, асимптотически равную (3k 1) · 2n1 при n, стремящемся к бесконечности.

2. Получена точная формула для расстояния от класса всех максимально-нелинейных функций от 2n переменных до класса функций, у которых в полиноме Жегалкина присутствует не бо лее одного нелинейного слагаемого. Показано, что для различных максимально-нелинейных функций расстояние до класса функций, у которых в полиноме Жегалкина присутствует не более одного нели нейного слагаемого, может быть различным. Для функций из класса Мэйорана–Мак-Фарланда получены точные границы, в которых изменяется это расстояние.

3. Получена точная формула для расстояния от класса максимально нелинейных функций Мэйорана–Мак-Фарланда от 2n переменных до класса функций, у которых в полиноме Жегалкина присутствует не более двух нелинейных слагаемых.

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

Публикации автора по теме диссертации [1] Алексеев В. Б., Омаров Р. Р., “О приближении максимально нелинейных булевых функций почти линейными функциями”, Дискретная математика, Изд-во Наука, Москва, 2012, Т. 24, вып. 3, 73– [2] Алексеев В. Б., Омаров Р. Р., “Исследование одного параметра булевых функций, близкого к нелинейности”, Научные ведомости Белгородско го государственного университета, 2009, Т. 15(70), № 12/1, 81– [3] Омаров Р. Р., “О расстояниях от максимально-нелинейных функций до некоторого класса булевых функций”, Материалы XI Международ ного семинара Дискретная математика и ее приложения, Изд-во мех.-мат. факультета МГУ, Москва, 2012, 425– [4] Алексеев В. Б., Омаров Р. Р., “О приближении булевых функций по чти линейными функциями”, Материалы X Международного семина ра Дискретная математика и ее приложения, Изд-во мех.-мат. фа культета МГУ, Москва, 2010, 514– [5] Алексеев В. Б., Омаров Р. Р., “О приближении одного класса максимально-нелинейных булевых функций почти аффинными функциями”, Труды VIII Международных Колмогоровских чтений, Изд-во ЯГПУ, Ярославль, 2010, 98– [6] Алексеев В. Б., Омаров Р. Р., “О расстояниях от максимально нелинейных булевых функций до почти аффинных функций”, Мате риалы XVI Международной конференции Проблемы теоретической кибернетики, Нижегородский университет, Нижний Новгород, 2011, 24–

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.