Кафедра математической логики и теории алгоритмов

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

Полугодовой спецкурс по выбору кафедры (осень 2021)

Лектор: Н.К. Верещагин

Курс читается по вторникам 18:30–20:05 он-лайн (Zoom).
Первая лекция – 14 сентября.
Страница спецкурса в базе данных мехмата.


Кликните здесь, чтобы увидеть ссылку Zoom
https://us02web.zoom.us/j/84574806181?pwd=Wm0vNCtkUmpZRVhyQTQ4NDhrMUZNdz09
Идентификатор: 845 7480 6181
Код доступа: 540889

Ссылка на записи на доске во время лекциий.

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

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

Необходимы предварительные знания: начала сложности вычислений (машины Тьюринга, схемы из функциональных элементов, взаимоотношения между ними, вероятностные алгоритмы, классы P, BPP, NP).

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

Домашние задания

После каждой лекции дается домашнее задание, состоящее из двух задач. Это домашнее задание надо сдать (послав PDF лектору) не позже начала следующей лекции. Решения, присланные после дедлайна, не проверяются. Повторно решать задачи нельзя. При проверке за каждое задание выставляется оценка, не превосходящая 1. Общая оценка за домашние задания равна среднему арифметическому оценок, полученных за все домашние задания (по существу, это – доля правильно решенных задач).

Итоговая оценка

Итоговая оценка выставляется только при условии посещения не менее 8 лекций, исходя из общей оценки за домашние задания по следующему правилу: отлично, если общая оценка 0.8 или больше, хорошо, если общая оценка 0.65 или больше, удовлетворительно, если общая оценка 0.5 или больше.

Таблица оценок (домашние задания, итоговая оценка)

Прочитанные лекции

Литература

  1.  Конспекты лекций.
  2. O. Goldreich. «Foundations of Cryptography — a two-volume book»