УТВЕРЖДАЮ | |
Проректор — начальник Управления научной политики и организации научных исследований МГУ имени д. ф.-м. н., профессор | |
_________________________ | |
«______»_______________ 2016 г. |
ОТЗЫВ
ведущей организации на диссертацию Городиловой Анастасии Александровны «Почти совершенно нелинейные функции: характеризация через подфункции и дифференциальная эквивалентность», представленную на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 - «Дискретная математика и математическая кибернетика»
Диссертационное исследование Городиловой Анастасии Александровны «Почти совершенно нелинейные функции: характеризация через подфункции и дифференциальная эквивалентность», представленная на соискание ученой степени кандидата физико-математических наук, состоит из введения, пяти глав (28 параграфов), заключения и списка литературы (105 наименований).
Результаты диссертации относятся к области исследований сложностных, алгебраических, комбинаторных и метрических свойств дискретных функций, активно развиваемой в настоящее время. Актуальность этой тематики обусловлена широким использованием дискретных функций в качестве математических моделей для средств обеспечения информационной безопасности и, в частности, в анализе и синтезе современных криптосистем.
Рассматриваемые автором булевы APN – отображения и бент — функции относятся к так называемым «криптографическим» классам булевых отображений. Изучению различных свойств этих классов отображений посвящено значительное число публикаций, конференций и семинаров. Однако, еще остаются неразрешенными такие проблемы, как нахождение мощностей классов или их нетривиальных оценок, полное описание классов, построение классификаций, вычисление для их представителей некоторых комбинаторных и метрических параметров, а также другие важные вопросы.
Целью данной работы является изучение комбинаторных свойств и характеризаций почти совершенно нелинейных отображений (APN — отображений) и бент — функций.
Во введении обосновывается актуальность исследований, проведенных в рамках данной диссертационной работы, приводится обзор результатов по изучаемой проблеме, формулируется цель работы.
Каждое рассматриваемые в диссертации отображение принадлежит множеству всех отображений пространства Хэмминга размерности n в пространство Хэмминга размерности k — Fun (n, k), при подходящих значениях натуральных n и k.
Первая глава содержит аналитический обзор основных криптографических свойств булевых функций и отображений. Кратко рассматриваются базовые теоретические результаты, полученные для каждого из свойств, и формулируются открытые проблемы в данной области. Необходимо отметить также рассмотренные в этой главе вопросы формирования данных свойств в ходе криптоаналитических исследований.
Во второй главе исследуется комбинаторное строение отображений из класса APN. Для произвольного отображения S из Fun(n, n) определяется четверка отображений F, G из Fun(n-1,n-1) и f, g из Fun(n-1,1), являющиеся сужениями исходного отображения S и одной из его координатных функций. Для таких наборов отображений автор вводит новое понятие «допустимого набора». На основе этого понятия получена (теорема 1) полная характеризация APN - отображения из F(n, n) через его сужения из F(n-1,n-1) и F(n-1,1).
В третьей главе для отображения из Fun(n, n) вводится понятие ассоциированной с ним булевой функции, являющейся индикатором разрешимости некоторого разностного уравнения. Дифференциальная эквивалентность двух отображений из Fun(n, n) определяется как равенство ассоциированных с ними функций. Приводятся результаты, описывающие некоторые свойства дифференциальной эквивалентности общего характера. Основными же здесь являются результаты исследований свойств классов дифференциальной зквивалентности для APN – отображений Голда. Автором найдено (теорема 2) исчерпывающее описание аффинных отображений из Fun(n, n), сложение которых с APN — отображениями Голда не выводит их за пределы их классов дифференциальной эквивалентности. Кроме того, из утверждения теоремы 2 следует, что класс APN — отображений Голда содержит квадратичные отображения, классы дифференциальной эквивалентности которых шире чем тривиальные.
В четвертой главе исследуются свойства еще одного нового понятия — линейного спектра квадратичных APN — отображений. В начале данной главы развивается вспомогательный аппарат и устанавливаются некоторые свойства ассоциированных булевых функций квадратичных APN — отображений (предложения 13 -15, теорема 3).
Линейный спектр квадратичного APN — отображения задается набором из
неотрицательных целых чисел. Элемент с номером k этого набора равен количеству линейных отображений из Fun(n, n), для которых число пар производных исходной функции и ее суммы с соответствующим линейным отображением, обладающих одинаковыми областями значений, равно k. Это понятие естественно возникает при изучении квадратичных APN — отображений и вытекает из их свойств. Определенные элементы линейного спектра могут быть постоянными для конкретных классов отображений. Автором описаны (теорема 4) множества элементов линейного спектра, которые имеют нулевое значение для произвольного квадратичного APN — отображения от четного числа переменных. Для APN — отображения Голда получены (следствие теоремы 4) явные выражения для крайних значений их линейных спектров.
В пятой главе устанавливаются некоторые новые комбинаторные свойства булевых функций Касами. Предварительно автором доказан ряд вспомогательных результатов (леммы 3—8, теорема 5), имеющих самостоятельное значение и развивающих математический аппарат исследования булевых функций, представляемых полиномами с коэффициентами из расширений поля Галуа из двух элементов и линейного оператора «след». Далее для произвольной булевой функции Касами от четного числа переменных не менее восьми получены (теорема 6) верхние и нижние границы для ее алгебраической степени t, гарантирующие отличие от тождественного нуля для кратных производных этой функции порядков (t-2) и (t-3). Данные результаты находят дальнейшую интерпретацию с использованием понятия k - существенной зависимости функции, заключающегося в том, что алгебраическая нормальная форма функции содержит мономы, включающие произведения любых k переменных. Для произвольной булевой функции Касами в условиях теоремы 6 получены верхние и нижние границы для ее алгебраической степени t, гарантирующие для этой функции (t-2) и (t-3) — существенную зависимость.
К наиболее интересным в теоретическом плане результатам можно отнести:
- полную характеризацию APN – отображений из Fun(n, n) через сужения из Fun(n-1,n-1) и Fun(n-1,1), являющаяся перспективной в синтезном плане (то есть содержащая в себе идеи построения APN – отображений от произвольного числа переменных);
- введение понятия дифференциальной эквивалентности булевых отображений и полное описание для APN — отображений Голда из Fun(n, n) дифференциально эквивалентных функций, получаемых сложением с аффинными отображениями;
- введение понятия линейного спектра для квадратичных APN – отображений и доказательство теоремы о нулевых значениях квадратичных APN – отображений от четного числа переменных, а также нахождение крайних значений линейного APN – отображений Голда;
- в ходе работы над диссертацией автором доказан ряд результатов, развивающих математический аппарат (новые понятия и математические утверждения), используемый в исследованиях, связанных с криптографическими приложениями булевых функций. Автор хорошо ориентируется в обширной зарубежной и отечественной научной литературе по тематике диссертации. Необходимо отметить, что основные результаты по исследованию свойств APN – отображений появились в иностранных публикациях. Это также положительно характеризует диссертационную работу.
Представленные в диссертации результаты являются новыми, развивают теорию дискретных функций и вносят определенный вклад в развитие математических методов криптографии.
Диссертационная работа выполнена на высоком научном уровне, все математические результаты строго доказаны. Для получения результатов автор использовал методы алгебры, комбинаторики, теории булевых функций, теории множеств.
Диссертация имеет теоретический характер. Вместе с тем, представленные в ней результаты могут быть использованы в анализе конкретных криптосистем, описываемых булевыми математическими моделями. Результаты диссертации могут быть полезны специалистам по теории кодирования, теории систем и математической криптографии. Они могут быть также использованы в учебном процессе при разработке лекционных курсов для студентов, специализирующихся в различных областях дискретной математики.
Достоверность основных научных положений и выводов, полученных в диссертационной работе, подтверждены апробацией материалов диссертации в печати, на научных конференциях и семинарах.
Автореферат диссертации соответствует содержанию диссертационной работы.
В диссертационной работе можно отметить следующие недостатки.
Объем первой главы мог бы быть несколько уменьшен за счет сокращения ее частей не связанных непосредственно с тематикой диссертации. Кроме того, в тексте диссертации имеются отдельные стилистические неточности. Например, название раздела 5.1. Указанные недостатки не снижают ценности выполненной работы.
Диссертация представляет собой завершенную научно - исследовательскую работу, выполненную на актуальную тему.
Таким образом, диссертация Городиловой Анастасии Александровны «Почти совершенно нелинейные функции: характеризация через подфункции и дифференциальная эквивалентность» отвечает требованиям, предъявляемым к диссертационным работам на соискание ученой степени кандидата физико-математических наук, соответствует Положению о присуждении ученых степеней, утвержденному постановлением Правительства Российской Федерации от 24 сентября 2013 г. № 000, а ее автор заслуживает присуждения ему ученой степени кандидата физико-математических наук по специальности 01.01.09 — дискретная математика и математическая кибернетика.
Отзыв подготовлен заведующим Отделом математических проблем информационной безопасности Института проблем информационной безопасности МГУ имени , кандидатом физико-математических наук, старшим научным сотрудником
Заведующий Отделом математических проблем информационной безопасности Института проблем информационной безопасности МГУ имени , кандидат физико- математических наук, старший научный сотрудник | |
Подпись заверяю: Заместитель директора Института проблем информационной безопасности МГУ имени , кандидат физико- математических наук, старший научный сотрудник |
1. .
2. Кандидат физико-математических наук, старший научный сотрудник.
3. Институт проблем информационной безопасности Федерального государственного бюджетного учреждения высшего образования «Московский государственный университет имени », заведующий Отделом математических проблем информационной безопасности.
4. Москва 119192, Мичуринский проспект, 1, офис 10.
5. Эл. почта: *****@***msu. ru
