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

• Автор: Омаров, Рустам Рамазанович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 75 с.

Оглавление
Введение
1 Оценки для расстояния между классами при произвольном к
2 Точные формулы для расстояния при к
3 Точные формулы для расстояния при к
Заключение
Список литературы

Введение
Данная работа относится к теории дискретных функций. В диссертации рассматриваются булевы функции и их важный с криптографической точки зрения параметр нелинейность. Исследуется класс максимально нелинейных функций.
Дискретные функции широко исследуются в математике, так как с их помощью удается описывать широкий класс природных явлений. Традиционными задачами для теории дискретных функций является изучение параметров и свойств этих функций, важных с практической или теоретической точки зрения. Множество функций, обладающих определенным свойством, можно выделить в отдельный класс. Поэтому естественным образом возникают задачи получения явных конструкций таких функций для использования в практике, подсчета мощностей этих классов, что представляет определенный теоретический интерес. Часто важно знать, как разные параметры соотносятся друг с другом, находятся ли они в противоречии или дополняют друг друга.
Наиболее известным примером дискретных функций являются булевы функции. Они находят широкое применение в электронных вычислительных и управляющих системах, играют важную роль при передаче информации. В криптографии они используются при конструировании различных криптографических объектов (шифры, хэш-функции и т.п.). Основной целью, преследуемой разработчиком таких объектов, например, шифров, является максимальное затруднение их анализа противником. Развитие методов криптографического анализа привело к выделению ряда свойств, важных с криптографической точки зрения. Наличие этих свойств у функций необходимо, чтобы криптографические схемы, построенные с их использованием, успешно противостояли различным методам анализа, например статистическом}', корреляционному, дифференциальному, линейному
Введение

[2, 3, 12, 16, 18]. К таким свойствам можно отнести нелинейность и устойчивость булевой функции, корреляционную и алгебраическую иммунности. Ежегодно публикуются десятки работ, посвсщенных изучению этих параметров, а также связей между ними (например, [4, 8, 17, 21]).
В ряде методов криптографического анализа существенно используется ,.близость“ криптографических функций к функциям, обладающим простой структурой с хорошо изученными свойствами. Примером таких плохих“ функций служат аффинные функции (в дискретной математике их обычно называют линейными). Мерой удаленности булевой функции от класса аффинных функций является ее нелинейность. Множество функций, для которых нелинейность принимает максимально возможное значение, называется множеством максимально-нелинейных функций. Известно, что при четных п нелинейность булевой функции от п переменных ограничена величиной А'/ < 2"-1 — 2П'2-1, причем для максимально-нелинейных функций это неравенство обращается в равенство.
Наличие у булевой функции свойств, близких к линейным, говорит об определенной „простоте“ этой функции, что облегчает исследование других ее параметров и свойств. Поэтому возникает практическая необходимость в построении функций, обладающих высокой или даже максимально возможной нелинейностью [10, 13, 20, 22]. Несмотря на то, что уже построено довольно много классов максимально-нелинейных функций, не удается описать класс всех максимально-нелинейных функций. Более того, не получено близких верхних и нижних оценок на мощность этого класса. Некоторые результаты в этом направлении можно найти в [11, 14, 23].
Вместе с нелинейностью можно рассматривать и нелинейность порядка г, которая определяется как минимальное расстояние между данной функцией и всеми функциями степени не более т. Если для подсчета нелинейности разработан эффективный аппарат коэффициентов Уолша, то подсчет нелинейности произвольного порядка представляет более сложную задачу. Рекурсивные оценки на нелинейность порядка г можно найти в [15], а оценки на нелинейность через другие параметры функции в [4, 5, 6].
Высокая нелинейность булевой функции означает, что она плохо приближается аффинными функциями. Однако в принципе может оказаться, что данную функцию удастся
Глава 3. Точные формулы при к

При таких предположениях для Т верно:
Т =2П~1 + 2,1“|л| у + 2пНС| у + 2п“1лис,|+1 и°°+
|2"-И1 _ 2"-ИиС1+1| . „1° -р |2П_1С'1 _ 2п-1ЛиС1+1|
(2п~а + 2П~1С1 - 2п_ІлисІ+1) . „и _ 26, где
(3.12)
6 = <

г)п-А — )
2’1~1С11
если ро Є Пі; если ро Є У); если ро Є У3;
2п-а + 2п~с _ 2п-ИиС|+і) если ро є у11
Далее доказательство будет состоять из рассмотрения отдельных случаев.
Лемма 3.3. Если мноэтества А, С непусты и А 5 С (А С С), то условие (3.1) для Т выполняется при п > 3, причем Т < Ттах.
Доказательство. Пусть для определенности АЭС, тогда ДиС = Л и ЛПС = С. Из того, что 10001 = 2|ЛиС| - 2|л| - 21С| + 21ЛпС1 = 2 - 2|л| - 2|С| + 2'с1 = 0 и ш01 = 21С| - 2Апс = 21 — 2 = 0, получим, что т40 = г1 = гЛ,1 = 0. С учетом этого запишем формулу (3.12)
Т < 5 2П_1 — 2— 2’1~ІЛІ+1 < 5 2п~1 — 2 — 2пА°( То есть Т < 5 2п~1 — 2ІСІ — 2п~сУ
в виде
(3.13)
Т <2п~1 + 2П“|Л| (і4° + О + 2П-|С| (і1 + + и“) - 26 <
<2П-1 + 2П-|Л| №10 + 2П-|С| (и2и + у131 + и4и)
=2П~1 + 2П_|Л| (2|л| - 2|С!) + 2пЧС1 (г;2п + і11 + п4п) - 26 <
< (т.к. А < п) < 3 2п~1 - 2|С1 + 2П“|С1 Ц1 + г1 + т}1) - 26.
Если Ро Є Уь то <5 = 0, ух + у1 + < Ши - 1 = 2|с1 - 1 и Т < 5 2'1'1 - 2|с' - 2«-'0>,
если ро € V) и V) и И;11, то у1 + г]1 + и)1 < Шц = 2'СД но 6 > 2пА) так как |И| > ]С|, и