Односторонние функции и их применения

Бакалавриат 2022/2023

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Верещагин Николай Константинович, Милованов Алексей Сергеевич

Язык: русский

Кредиты: 5

Контактные часы: 60

Дополнительные материалы в LMS Задать вопрос

Аннотация

Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,  по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,  схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации. Необходимы предварительные знания: знакомство с основными вычислительными  моделями: машинами Тьюринга, вероятностными машинами Тьюринга  и схемами из функциональных элементов.

Цель освоения дисциплины

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

Планируемые результаты обучения

Умение решать задачи на тему "односторонние функции"
Умение решать задачи на тему "Трудный бит"
Знание основных криптографических протоколов (ауентификация, цифровая подпись, шифрование).

Содержание учебной дисциплины

Слабо и сильно необратимые функции для равномерного и неравномерного противника. Односторонние функции.  Если P=NP, то односторонних функций нет.  Функция Mult.  Функция SubsetSum
Преобразование слабо необратимой функции в сильно необратимую. Полиномиально моделируемые и доступные распределения.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом.
Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ
Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.

Элементы контроля

Колллоквиум
Проходит устно.
Экзамен
Домашние задания

Промежуточная аттестация

2022/2023 учебный год 2 модуль
0.4 * Домашние задания + 0.4 * Колллоквиум + 0.2 * Экзамен

Список литературы

Авторы

Милованов Алексей Сергеевич
Верещагин Николай Константинович

Программа дисциплины