Город: Санкт-Петербург Казань Язык: Русский English

Теоретико-сложностные основы криптографии
Санкт-Петербург / весна 2016, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Криптография как учение о шифрах появилась несколько тысячелетий назад, однако наукой она стала лишь во второй половине 20-го века, когда появились строгое определения криптографических протоколов, понятий о их надежности и сформировалась культура строгих доказательств надежности. В курсе пойдет речь о теоретических основаниях криптографии на языке теории сложности. Детали практических реализаций либо не будут упоминаться совсем, либо будут упоминаться лишь вскользь.

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

Во второй части курса на основе криптографических примитивов мы построим конкретные криптографические протоколы: протокол с секретным ключом, протокол с открытым ключом, привязка к биту, протокол подкидывания монетки, секретное вычисление функций, протокол цифровой подписи, доказательства с нулевым разглашением и пр.

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

Курс требует от слушателей знаний основ теории сложности (классы P, NP, сведения, NP-полные задачи, булевы схемы, вероятностные алгоритмы, желательно слышать про интерактивные доказательства), дискретной теории вероятности и начальных сведений из линейной алгебры, теории чисел и математического анализа. От слушателей ожидается готовность воспринимать сложные определения и сложные доказательства теорем (лектор постарается сделать все возможное, чтобы облегчить восприятие). Курс состоит из лекций и практических занятий, на которых будут обсуждаться задачи на темы лекций.

Курс входит в магистерскую программу теоретическая информатика Академического университета.

Рекомендуемая литература:

  1. O. Goldreich, Foundations of cryptography, vol. 1, vol. 2
  2. J. Katz, Y. Lindell, Introduction to Modern Cryptography
  3. Н.К. Верещагин, курс лекций Теоретико-сложностные проблемы криптографии, http://lpcs.math.msu.su/~ver/teaching/cryptography/index.html

Вопросы к экзамену.

Дата и время Название Место Материалы
11 февраля
18:30–20:05
Односторонние функции, лекция ПОМИ РАН видео
11 февраля
20:15–21:50
Односторонние функции, семинар ПОМИ РАН Нет
18 февраля
18:30–20:05
Генераторы псевдослучайных чисел, лекция ПОМИ РАН Нет
18 февраля
20:15–21:50
Обсуждение первого домашнего задания, семинар ПОМИ РАН Нет
25 февраля
18:30–20:05
Генератор псевдослучайных чисел из односторонней перестановки, лекция ПОМИ РАН видео
25 февраля
20:15–21:50
Обсуждение второго домашнего задания , семинар ПОМИ РАН Нет
03 марта
18:30–20:05
Теорема Голдрейха-Левина о трудном бите, лекция ПОМИ РАН видео
03 марта
20:15–21:50
Обсуждение третьего домашнего задания, семинар ПОМИ РАН Нет
10 марта
18:30–20:05
Семейство псевдослучайных функций, лекция ПОМИ РАН видео
10 марта
20:15–21:50
Обсуждение четвертого домашнего задания , семинар ПОМИ РАН Нет
17 марта
18:30–20:05
Протоколы с открытым ключом, лекция ПОМИ РАН видео
17 марта
20:15–21:50
Обсуждение пятого домашнего задания , семинар ПОМИ РАН Нет
24 марта
18:30–20:05
Интерактивные протоколы привязки к биту, лекция ПОМИ РАН видео
24 марта
20:15–21:50
Обсуждение шестого домашнего задания, семинар ПОМИ РАН Нет
31 марта
18:30–20:05
Доказательства с нулевым разглашением, лекция ПОМИ РАН видео
31 марта
20:15–21:50
Обсуждение седьмого домашнего задания , семинар ПОМИ РАН Нет
07 апреля
18:30–20:05
Нулевое разглашение для языков из NP, лекция ПОМИ РАН видео
07 апреля
20:15–21:50
Обсуждение восьмого домашнего задания, семинар ПОМИ РАН Нет
14 апреля
18:30–20:05
Протоколы цифровой подписи, лекция ПОМИ РАН видео
14 апреля
20:15–21:50
Обсуждение девятого домашнего задания, семинар ПОМИ РАН Нет
21 апреля
18:30–20:05
Протоколы цифровой подписи (продолжение), лекция ПОМИ РАН видео
21 апреля
20:15–21:50
Обсуждение десятого домашнего задания, семинар ПОМИ РАН Нет
28 апреля
18:30–20:05
Основные понятия теории сложности в среднем, лекция ПОМИ РАН видео
28 апреля
20:15–21:50
Обсуждение одиннадцатого домашнего задания, семинар ПОМИ РАН Нет
05 мая
18:30–20:05
Трудные в среднем задачи, лекция ПОМИ РАН видео
05 мая
20:15–21:50
Обсуждение двенадцатого домашнего задания , семинар ПОМИ РАН Нет
12 мая
18:30–20:05
Сведение к равномерному распределению, лекция ПОМИ РАН видео
12 мая
20:15–21:50
Обсуждение тринадцатого домашнего задания , семинар ПОМИ РАН Нет
26 сентября 2016

Видео

Доступны видеозаписи всех лекций курса.

08 апреля 2016

Новые видео

Выложены видео лекций 1, 3, 4, 5, 6 и 7