WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

Апробация работы. Результаты докладывались на российских и международных конференциях: Шестой молодежной научной школе по дискретной математике и ее приложениям в 2007 году в Москве, ISIT’2007 IEEE Международном Симпозиуме по Теории Информации в Ницце (Франция), Шестой школе-семинаре SIBECRYPT’ Компьютерная безопасность и криптография в Горно-Алтайске, международной конференции Математика в современном мире в Новосибирске в 2007 году, Четвертой международной конференции BFCA’2008 Булевы функции: криптография и приложения в Копенгагене (Дания), 15-ой международной конференции Проблемы теоретической кибернетики в Казани в 2008 году, SIBIRCON2008 IEEE Международной Конференции Вычислительные Технологии в Электрической и Электронной Инженерии в Новосибирске, Седьмой школе-семинаре SIBECRYPT’08 Компьютерная безопасность и криптография в Красноярске.

Результаты докладывались на семинарах Дискретный анализ, Теория кодирования, Геометрия, топология и их приложения и общеинститутском семинаре Института Математики СО РАН; научных семинарах Института проблем передачи информации имени А. А. Харкевича в Москве; лаборатории информатики, сигналов и систем национального центра научных исследований (I3S CNRS) в Софии Антиполисе (Франция); кафедры защиты информации и криптографии Томского государственного университета. Результаты кандидатской диссертации отмечены премией школы Компьютерная безопасность и криптография SIBECRYPT’07 в году. Работа выполнена при поддержке интеграционного проекта СО РАН N 35 Древовидный каталог математических Интернетресурсов mathtree.ru, Российского фонда фундаментальных исследований (проекты 07-01-00248, 08-01-00671), гранта Лучшие аспиранты РАН за 2008 год Фонда содействия отечественной науке, гранта NUGET (Agence Nationale de la Recherche, France), совета научной молодежи ИМ СО РАН и Новосибирского государственного университета.

Основные результаты диссертации.

1. На множестве двоичных векторов длины m введены новые бинарные операции u, v, являющиеся аналогами скалярного произk ведения. Исследованы их свойства. Определены новые понятия kнелинейности и k-преобразования Уолша Адамара булевой функции.

2. Введено новое обобщение понятия бент-функции k-бент-функция, отражающее возможность поэтапного усиления нелинейности булевой функции с ростом целого параметра k. Бент-функции и 1-бент-функции совпадают. Доказано, что класс k-бент-функций строго вложен в класс -бент-функций при k >.

3. Предложены способы построения k-бент-функций и исследованы их свойства. Доказано существование k-бент-функций от m переменных любой степени нелинейности d, где 2 d max{2, (m/2) k + 1}.

4. Классифицированы k-бент-функции от малого числа переменных.

5. Исследованы квадратичные аппроксимации вида u, (v), где k v вектор переменных; перестановка, целое k и вектор u параметры. Показано, что использование k-бент-функций в качестве функций шифрования максимально повышает стойкость блочного шифра к таким аппроксимациям.

6. Рассмотрены четырехразрядные подстановки, рекомендованные для S-блоков алгоритмов ГОСТ 28147-89, DES, s3DES; с помощью компьютера показано, что для всех этих подстановок (кроме одной) существуют более вероятные (по сравнению с линейными) квадратичные приближения функциями вида u, (v).

k 7. Отмечена аналогия между проблемами нижних верхних оценок числа бент-функций и двоичных кодов, таких как совершенные и равномерно упакованные. Для числа равномерно упакованных двоичных кодов установлена новая (лучшая на данный момент) верхняя оценка.

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

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

Публикации. По теме диссертации опубликовано 13 работ, [26–38].

Из них 4 статьи в журналах, 9 работ в трудах и тезисах международных конференций. На web-странице www.math.nsc.ru/tokareva работы и текст диссертации доступны в электронном виде.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, предметного указателя и списка литературы из 153-х наименований. Общий объем работы 120 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Во введении обсуждается актуальность исследования бент-функций и их обобщений; дается обзор полученных результатов.

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

Для числа равномерно упакованных двоичных кодов в Теореме устанавливается новая (лучшая на данный момент) верхняя оценка (доказательство теоремы приведено в главе 5).

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

k определяются k-преобразование Уолша Адамара, k-нелинейность булевой функции, и вводится понятие k-бент-функции.

С 90-х годов в теории кодирования активно стали исследоваться нелинейные коды, образы которых под действием подходящих (как правило, взаимно-однозначных и изометричных) отображений в другие метрические пространства линейны. Так, ярким примером служат Z4-линейные коды двоичные коды, прообразы которых относительно отображения Грея : 0 00, 1 01, 2 11, 3 10, являются линейными кодами над кольцом Z4. Интересно, что многие нелинейные в обычном смысле двоичные коды (среди них коды Кердока, Препараты, Геталса и др.) оказались Z4-линейными, см.

работы 1989 года А. А. Нечаева [4] и П. Сол [25], работу 1994 года е А. Р. Хэммонса и др. [13]. Можно сказать, что это явление альтернативной линейности, которое удалось обнаружить, послужило ключом к структуре таких кодов и впервые позволило перенести богатый аппарат линейных методов теории кодирования в нелинейную область. В данной диссертации альтернативный подход к линейности используется для изучения булевых функций.

Рассмотрим Z2- и Z4-линейные коды с параметрами кодов Адамара (далее кратко коды типа Адамара). Известно, что Z2-линейный (т. е. линейный в обычном смысле) двоичный код Адамара длины 2m единствен с точностью до эквивалентности. Д. С. Кротовым [18] было показано, что существуют в точности m/2 попарно неэквивалентных Z4-линейных кодов типа Адамара длины 2m+1 при m > 2.

Опираясь на классификацию [18] всех таких кодов, рассмотрим специальную серию двоичных кодов типа Адамара Ak, 1 k m/2, m длины 2m (m четно). В этой серии каждый код Ak получается из m линейного над Z4 кода Ak заменой элементов 0, 1 на 0 и элементов m 2, 3 на 1 в каждой координате, где Ak подкод соответствующего m линейного четверичного кода Адамара типа 4k2m-2k (см. [18]), состоящий из всех кодовых векторов, имеющих в первой координате только 0 или 2. Каждый код Ak образует абелеву группу относиm тельно операции •, индуцированной операцией + покоординатного сложения над Z4, определенной на векторах кода Ak.

m Теорема 2. При четном m, целом k, 1 k m/2, выполняются (i) код Ak является кодом с параметрами кода Адамара;

m (ii) код A1 линеен, коды A1,..., Am/2 попарно неэквивалентны;

m m m (iii)операция •, заданная на Ak, согласована с метрикой Хэмминга.

m Множество Ak булевых функций, векторами значений которых явm ляются кодовые векторы кода Ak, представляет собой аналог мноm жества аффинных функций это функции вида u, v a, где k a Z2 и операция ·, · играет роль скалярного произведения. Таk кие функции далее названы k-аффинными4. Коды Ak выбраны таm ким образом, чтобы операции ·, · обладали многими свойствами k обычного скалярного произведения и на их основе оказались возможными конструктивные построения. Отметим, что каждая операция ·, · при k 2 не является билинейной формой. Явный вид k операции u, v следующий.

k Теорема 3. Пусть m, k целые, 1 k m/2. Для любого целого i, 1 i m/2, любых u, v Zm пусть Yi = (u2i-1 u2i)(v2i-1 v2i).

Тогда k k u, v = YiYj u, v.

k i=1 j=i Необходимо отметить, что термин k-аффинная функция в другом значении уже использовался ранее М. Л. Буряковым и О. А. Логачевым [1]. Параметр k в их работе играет роль уровня аффинности булевой функции и не имеет ничего общего с параметром, определяемым здесь. К сожалению, такое совпадение терминов было замечено уже достаточно поздно.

Каждый класс функций Ak состоит из 2m-k+1(k + 1) аффинных m функций и 2m-k+1(2k - k - 1) квадратичных функций.

С помощью операции ·, · определяются k-преобразование Уолша k (k) (k) Адамара Wf и k-нелинейность Nf булевой функции f. Верна (k) Теорема 4 (равенство Парсеваля для Wf ). Для любой булевой функции f от m переменных выполняется (k) Wf (v) = 22m.

vZm Булеву функцию от четного числа переменных m назовем максимально k-нелинейной (k-бент-) функцией, 1 k m/2, если вектор значений этой функции удален на максимально возможное расстояние 2m-1 - 2(m/2)-1 от каждого кода типа Адамара Aj, j = m (j) 1,..., k (или, что эквивалентно, Wf (v) = ±2m/2 для любого v Zm и каждого j = 1,..., k). Другими словами, каждая k-бент-функция одинаково плохо аппроксимируется булевыми функциями из каждого класса Aj, j = 1,..., k. Обычные бент-функции представляют m собой класс 1-бент-функций. Через Bk обозначим класс всех k-бентm функций от m переменных.

Результаты второй главы опубликованы в работах [26, 30, 31, 32].

В третьей главе изучаются способы построения k-бент-функций и их свойства. Известно, что задача описания бент-функций для произвольного числа переменных m, или хотя бы нахождения хороших нижних и верхних оценок числа таких функций является очень сложной. Об этом свидетельствует, например, тот факт, что число 6 является максимальным значением для m, при котором еще известно точное значение числа бент-функций (равное 5 425 430 232,3, см. описание в [5]), несмотря на длительный срок их исследования и большой интерес к этим объектам. В первой части третьей главы дается простое описание класса 2-бент-функций от четырех переменных.

Теорема 5. Пусть параметры i1, i2, i3 и i4 принимают различные целые значения от 1 до 4. Тогда множество функций B2 состоит из всех функций степени 2 с квадратичными частями вида:

vi vi vi vi (3 типа);

1 2 3 vi vi vi vi vi vi при {i1, i2} = {1, 2} или {3, 4} (4 типа);

1 2 1 3 2 vi vi vi vi vi vi vi vi при {i1, i2} = {1, 2} или {3, 4} (4 типа);

1 2 2 3 3 4 1 v1v2 v1v3 v1v4 v2v3 v2v4 v3v4 (1 тип).

Тем самым, параметр m = 6 становится наименьшим, при котором k-бент-функции пока не описаны.

Во второй части главы приводится итеративная конструкция k-бентфункций. Пусть Fm множество булевых функций от m переменных, F1 множество симметрических функций от двух переменных.

Теорема 6. Пусть числа m, r 0 четны, j 0 любое, k такое, что 1 k m/2, и пусть функция f F2j+m+r представима в виде j f(a1, a 1,..., aj, a j, u, u ) = si(ai, a i) p(u ) q(u ), i=где s1,..., sj F1, p Fm и q Fr функции с непересекающимися множествами переменных. Тогда f принадлежит классу Bj+k, 2j+m+r если и только если s1,..., sj B1, p Bk и q B1.

2 m r В качестве следствия устанавливается, что для k > 1 класс kбент-функций Bk является собственным подклассом класса -бентm функций B m. Показывается, что существуют k-бент-функции с любой степенью нелинейности d, где 2 d max{2, (m/2)-k+1}. Напомним, что степенью нелинейности булевой функции называется число переменных в самом длинном слагаемом ее алгебраической нормальной формы (или многочлена Жегалкина).

Пусть Sm,k подгруппа группы Sm подстановок на m элементах, порожденная k транспозициями: (1, 2), (3, 4),..., (2k - 1, 2k). Пусть Fk обозначает множество всех функций f Fm, постоянных на m каждой орбите множества Zm под действием группы Sm,k; справедm-k log2 ливо |Fk | = 22. Доказана следующая теорема о связи k-бентm функций и бент-функций.

Теорема 7. При любом четном m 2, целом k, 1 k m/2, справедливо равенство Fk Bk = Fk B1.

m m m m Результаты третьей главы опубликованы в работах [32, 33, 37].

В четвертой главе исследуется возможность квадратичного криптоанализа блочных шифров, в основу которого положены квадратичные аппроксимации специального вида, и роль k-бент-функций при конструировании таких шифров. Квадратичный криптоанализ является нелинейной модификацией известного метода линейного криптоанализа блочных шифров, предложенного М. Мацуи [19] в 1993 году для шифров FEAL и DES и являющегося в настоящее время одним из наиболее эффективных.

Идея метода линейного криптоанализа заключается в следующем.

Сначала для известного алгоритма шифрования определяется линейное соотношение L на биты открытого текста, шифротекста и ключа, выполняющееся с вероятностью p = 1/2+, достаточно сильно отличающейся от 1/2. Число называется преобладанием соотношения L. Затем при фиксированном неизвестном ключе K криптоаналитиком собирается статистика из N пар {открытый текст соответствующий шифротекст}, и на ее основе с учетом знака производится различение двух простых статистических гипотез: выполняется ли соотношение L для данного неизвестного ключа K или нет. В результате для битов ключа K устанавливается новое вероятностное соотношение. Для надежной работы этого метода мощность статистики N должна быть пропорциональна величине ||-2.

Общий подход к использованию в линейном криптоанализе нелинейных аппроксимаций предложили в 1996 году Л. Кнудсен и М. Робшау [17]. Основная его идея: обогатить класс аппроксимирующих функций нелинейными функциями и за счет этого повысить качество аппроксимации. Но при этом криптоаналитику придется столкнуться со следующими трудностями. Как эффективно выбрать хорошую нелинейную аппроксимацию В линейном случае возможно решение такой задачи перебором всех 2m линейных функций (от m m переменных). В общем случае полный перебор 22 булевых функций неосуществим даже при малых значениях m. Как объединить нелинейные аппроксимации отдельных раундов В целом метод нелинейного криптоанализа не получил пока должного развития.

Pages:     | 1 || 3 |






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