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

Полугодовой спецкурс по выбору кафедры математической логики и теории алгоритмов.

Весна 2020

Новости

C 17 марта 2020 года МГУ перешел на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут происходить в обычное время (по понедельникам с 18:30 до 20:05) на сайте zoom.us с помощью электронной доски jamboard.google.com

Во время лекции можно задавать вопросы, как обычно.

Задания выкладываются, как обычно.

Краткое описание курса

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

Программа курса.

Курс читается по понедельникам в 18:30-20:05 в ауд. 1604. Первая лекция 10 февраля.

Дневник лекций

Каждую неделю для решения даётся две задачи. Для получения оценки за спецкурс достаточно посещать лекции и решить эти задачи: Список задач с указанием срока сдачи. Оценки за курс (при условии посещения не менее 8 из 12 лекций): отлично - 70% от максимального количества баллов, хорошо - 55%, удовлетворительно - 40%. Зачет - 40%.

Оценки за сданные задачи.

Конспекты лекций.