Программа экзамена по курсу «Введение в математическую криптографию / Математическая криптография» (2015/2016 уч. г.)

PDF-версия программы (1 стр.)

Введение. Предмет математической криптографии. Криптографические протоколы и криптографические примитивы. Параметр стойкости. Модель противника. Понятие об атаках на криптографические протоколы и об угрозах стойкости криптографических протоколов. Общее понятие стойкости криптографического протокола против данной угрозы на основе данной атаки. Три задачи криптографии — обеспечение конфиденциальности, целостности, неотслеживаемости. Вспомогательные понятия, используемые в курсе: полиномиальный параметр, пренебрежимо малая функция, статистическое расстояние, статистическая неотличимость, вычислительная неотличимость и т. д.

Сильно и слабо односторонние функции и перестановки. Построение сильно односторонней функции на основе произвольной слабо односторонней функции (теорема Яо). Сильно (слабо) односторонние семейства функций и их связь с сильно (слабо) односторонними функциями. Примеры гипотетически односторонних семейств функций.

Трудные и трудно аппроксимируемые функции и предикаты. Связь между трудными и трудно аппроксимируемыми функциями. Теорема Гольдрайха — Левина о трудном предикате.

Псевдослучайные генераторы (генераторы псевдослучайных последовательностей). Два определения псевдослучайного генератора: через вычислительную неотличимость и через непредсказуемость следующего бита. Теорема Яо об эквивалентности этих определений. Увеличение разности длин выхода и входа псевдослучайного генератора. Теорема Хостада и др. о необходимом и достаточном условии существования псевдослучайных генераторов (без доказательства). Построение псевдослучайного генератора исходя из произвольной односторонней перестановки.

Псевдослучайные семейства функций. Построение псевдослучайного семейства функций на основе произвольного псевдослучайного генератора, удваивающего длину входа (теорема Гольдрайха и др.).

Псевдослучайные и сильно псевдослучайные семейства перестановок. Преобразование Файстеля. Построение полиномиально инвертируемого псевдослучайного семейства перестановок на основе произвольного псевдослучайного семейства функций (теорема Луби — Ракоффа, без доказательства). Построение полиномиально инвертируемого сильно псевдослучайного семейства перестановок на основе произвольного псевдослучайного семейства функций (теорема Луби — Ракоффа, без доказательства).

Семейства хэш-функций с трудно обнаружимыми коллизиями. Теорема о композиции для семейств хэш-функций с трудно обнаружимыми коллизиями.

Универсальные односторонние семейства хэш-функций. Теорема о композиции для универсальных односторонних семейств хэш-функций. Теорема Ромпеля о необходимом и достаточном условии существования универсальных односторонних семейств хэш-функций (без доказательства). Построение универсального одностороннего семейства хэш-функций на основе произвольной односторонней перестановки (теорема Наора — Юнга).

Семейства функций и перестановок с секретом. Примеры гипотетических семейств функций и перестановок с секретом (семейства RSA и Рабина). Доказательство того, что семейство Рабина является семейством функций с секретом в предположении трудности задачи факторизации целых чисел Блюма. Доказательство того, что семейство Рабина, ограниченное на элементы нечетного порядка, является семейством перестановок с секретом в предположении трудности задачи факторизации целых чисел.

Элементы теории Шеннона систем секретной связи (secrecy systems). Понятия замкнутой, совершенной и чистой системы секретной связи. Нижняя оценка числа элементов носителя априорного распределения вероятностей на пространстве ключей совершенной системы секретной связи. Остаточные классы сообщений и криптограмм замкнутой чистой системы секретной связи. Разложение замкнутой чистой системы секретной связи в «дизъюнктное объединение» совершенных систем секретной связи. Пример: система секретной связи Вернама.

Системы шифрования (криптосистемы) с секретным и с открытым ключом. Блоковые системы шифрования. Атаки на системы шифрования и угрозы стойкости последних. IND-стойкость, IND-CPA-стойкость и IND-CCA-стойкость. Построение IND-CPA-стойкой блоковой системы шифрования с секретным ключом на основе произвольного полиномиально инвертируемого псевдослучайного семейства перестановок. Построение IND-стойкой (на основе атаки с открытым ключом) блоковой системы шифрования с открытым ключом, исходя из семейства функций, трудного для некоторого семейства перестановок с секретом. Конструкция системы шифрования сообщений произвольной длины на основе блоковой системы шифрования. Сохранение IND-стойкости на основе атаки с открытым ключом для этой конструкции, примененной к системе шифрования с открытым ключом.

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна