Криптографические, алгоритмические и теоретико-сложностные свойства дискретных функцийНИР

Cryptological, algorithmic, and complexity theoretic properties of discrete functions

Источник финансирования НИР

грант РФФИ

Этапы НИР

# Сроки Название
1 1 января 2016 г.-31 декабря 2016 г. Этап 2016 г.
Результаты этапа: Разработана ориентированная на практическое применение модель оценки стойкости некоторых режимов работы блоковых шифров. Эта модель применена к некоторым важным частным случаям. Предложен набор промежуточных моделей, позволяющих строить сведения и получать оценки стойкости широкого класса алгоритмов преобразования ключа. Сделан обзор уязвимостей протоколов аутентификации с выработкой общего ключа на основе пароля (семейства PAKE). С точки зрения обозначенных уязвимостей, выстроенных в определенную иерархию, объяснены основные принципы построения отечественного протокола SESPAKE. Найдены необходимые и достаточные условия псевдосвободности (в многообразии всех элементарных абелевых p-групп, где p - произвольное простое число) для семейств конечных вычислительных элементарных абелевых p-групп, элементы которых однозначно представлены бинарными строками длины, полиномиальной от длины индекса группы в семействе. Получены критерии существования псевдосвободных семейств конечных вычислительных элементарных абелевых p-групп, удовлетворяющих указанному условию для представителей элементов, в терминах существования криптографических примитивов некоторых видов. Построена новая рекурсивная конструкция упаковок (n,k)-продуктов (включая совершенные упаковки); получены соответствующие рекуррентные оценки их длины. Найдены бесконечные семейства носителей спектра, для которых удается вычислить число платовидных булевых функций с такими носителями спектра; получены соответствующие формулы. Введено понятие полиномиально устойчивого источника случайности и доказан ряд теорем о существовании криптографически стойких псевдослучайных генераторов в модели с такими источниками случайности. Рассчитаны и обоснованы параметры эффективности методов, использующих аффинные нормальные формы булевых функций для решения систем квадратичных булевых уравнений. Получена новая универсальная достижимая оценка экспонентов n-вершинных примитивных орграфов. Исследовались также криптографические генераторы, ключевые расписания блоковых шифров и признаки в полугруппах.
2 1 января 2017 г.-31 декабря 2017 г. Этап 2017 г.
Результаты этапа: Для шифра "Магма" с преобразованием ключа методом CryptoPro Key Meshing (CPKM) получены оценки стойкости в рамках стандартной модели и модели с информацией из побочных каналов. Предложена модификация алгоритма преобразования ключа, улучшенная по сравнению с CPKM. При весьма общих дополнительных предположениях об аддитивной группе описаны все ассоциативные коммутативные кольца, для всех функций над которыми совпадают следующие параметры: (а) наименьшая степень многочлена, представляющего функцию и (б) наименьшее число n\ge-1 такое, что все (n+1)-кратные производные функции равны 0. Доказан критерий совершенной уравновешенности сдвиг-композиции p-значных функций. Найдены новые классы совершенно уравновешенных функций над конечными полями, не являющихся перестановочными по крайним переменным. Построены совершенные упаковки двойной кратности (n,2)-продуктов для нескольких бесконечных последовательностей значений n. Произведено обобщение упаковок (n,k)-продуктов на случай не двух, а большего числа слагаемых в сумме; для таких обобщений получены оценки на мощность и найдены конструкции. Усовершенствован метод оценивания числа "плохих" продуктов в предложенных ранее рекурсивных конструкциях, т.е. таких продуктов, которые по своим характеристикам не могут быть использованы на последующих шагах рекурсии. Исследованы вопросы минимизации заданного примитивного множества неотрицательных матриц порядка n (n-вершинных орграфов), где минимизация понимается как определение минимальных примитивных подмножеств. Получены критерий локальной примитивности орграфа и оценки локальных экспонентов (как универсальная оценка, так и ее уточнения для различных частных случаев). Исследованы перемешивающие свойства модифицированных аддитивных генераторов. Выведен закон нестационарной рекурсии, позволяющий для любого примитивного множества A={a_1,...,a_k} (k\ge3), построить алгоритм вычисления множества чисел C(a_1,...,a_k), не содержащихся в аддитивной полугруппе, порожденной множеством A. Исследованы некоторые вопросы примитивности перемешивающих орграфов композиций регистровых подстановок и связь экспонентов прямой и обратной подстановок.
3 1 января 2018 г.-31 декабря 2018 г. Этап 2018 г.
Результаты этапа: Проанализирована стойкость некоторых режимов практических шифров. Получена формула для числа однородных невырожденных функций φ:Z_p^n→Z_p, имеющих степень d, где p — простое число. В случае, когда d≥3, найдена более простая асимптотическая формула для числа таких функций при n→∞. Введено полезное представление булевых функций с помощью векторов на евклидовой сфере. Определено и изучено понятие Δ-эквивалентности булевых функций. Предложен метод построения бент-функций путем конкатенации (платовидных) функций адреса с непересекающимися носителями спектра. Введены и исследованы новые метрические характеристики локально примитивных орграфов. Получена улучшенная оценка экспонента примитивного орграфа с n вершинами.

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".