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

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

Весна 2020

Новости

C 17 марта 2020 года МГУ перешел на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут транслироваться и записываться в обычное время (по понедельникам с 18:30 до 20:05) на моем Ютуб канале https://www.youtube.com/channel/UCQpMy-jk_5qdi91U9NsBVdQ?view_as=subscriber

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

Задания выкладываются, как обычно. Задание к 23 марта уже выложено.

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

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

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

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

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

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

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

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