Односторонние функции и их применения (мехмат, осень 2021)
Полугодовой спецкурс по выбору кафедры (осень 2021)
Лектор: Н.К. Верещагин
Курс читается по вторникам 18:30–20:05 он-лайн (Zoom).
Первая лекция – 14 сентября.
Страница спецкурса в базе данных мехмата.
Ссылка на записи на доске во время лекциий. | Записи лекция на YouTube | Группа в Телеграм https://t.me/joinchat/STGxTbyvLNQ3NjVi
Краткое описание курса:
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Будет рассказано, как односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел, схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
Необходимы предварительные знания: начала сложности вычислений (машины Тьюринга, схемы из функциональных элементов, взаимоотношения между ними, вероятностные алгоритмы, классы P, BPP, NP).
Программа курса
Домашние задания
После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF лектору) не позже начала следующей лекции. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).
Итоговая оценка
Итоговая оценка выставляется только при условии посещения не менее 8 лекций, исходя из общей оценки за домашние задания по следующему правилу: отлично, если общая оценка 0.8 или больше, хорошо, если общая оценка 0.65 или больше, удовлетворительно (= зачет), если общая оценка 0.5 или больше.