City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Theoretical foundations of cryptography
Saint Petersburg / spring 2016, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Криптография как учение о шифрах появилась несколько тысячелетий назад, однако наукой она стала лишь во второй половине 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

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

Date and time Class|Name Venue|short Materials
11 February
18:30–20:05
Односторонние функции, Lecture ПОМИ РАН video
11 February
20:15–21:50
Односторонние функции, Seminar ПОМИ РАН No
18 February
18:30–20:05
Генераторы псевдослучайных чисел, Lecture ПОМИ РАН No
18 February
20:15–21:50
Обсуждение первого домашнего задания, Seminar ПОМИ РАН No
25 February
18:30–20:05
Генератор псевдослучайных чисел из односторонней перестановки, Lecture ПОМИ РАН video
25 February
20:15–21:50
Обсуждение второго домашнего задания , Seminar ПОМИ РАН No
03 March
18:30–20:05
Теорема Голдрейха-Левина о трудном бите, Lecture ПОМИ РАН video
03 March
20:15–21:50
Обсуждение третьего домашнего задания, Seminar ПОМИ РАН No
10 March
18:30–20:05
Семейство псевдослучайных функций, Lecture ПОМИ РАН video
10 March
20:15–21:50
Обсуждение четвертого домашнего задания , Seminar ПОМИ РАН No
17 March
18:30–20:05
Протоколы с открытым ключом, Lecture ПОМИ РАН video
17 March
20:15–21:50
Обсуждение пятого домашнего задания , Seminar ПОМИ РАН No
24 March
18:30–20:05
Интерактивные протоколы привязки к биту, Lecture ПОМИ РАН video
24 March
20:15–21:50
Обсуждение шестого домашнего задания, Seminar ПОМИ РАН No
31 March
18:30–20:05
Доказательства с нулевым разглашением, Lecture ПОМИ РАН video
31 March
20:15–21:50
Обсуждение седьмого домашнего задания , Seminar ПОМИ РАН No
07 April
18:30–20:05
Нулевое разглашение для языков из NP, Lecture ПОМИ РАН video
07 April
20:15–21:50
Обсуждение восьмого домашнего задания, Seminar ПОМИ РАН No
14 April
18:30–20:05
Протоколы цифровой подписи, Lecture ПОМИ РАН video
14 April
20:15–21:50
Обсуждение девятого домашнего задания, Seminar ПОМИ РАН No
21 April
18:30–20:05
Протоколы цифровой подписи (продолжение), Lecture ПОМИ РАН video
21 April
20:15–21:50
Обсуждение десятого домашнего задания, Seminar ПОМИ РАН No
28 April
18:30–20:05
Основные понятия теории сложности в среднем, Lecture ПОМИ РАН video
28 April
20:15–21:50
Обсуждение одиннадцатого домашнего задания, Seminar ПОМИ РАН No
05 May
18:30–20:05
Трудные в среднем задачи, Lecture ПОМИ РАН video
05 May
20:15–21:50
Обсуждение двенадцатого домашнего задания , Seminar ПОМИ РАН No
12 May
18:30–20:05
Сведение к равномерному распределению, Lecture ПОМИ РАН video
12 May
20:15–21:50
Обсуждение тринадцатого домашнего задания , Seminar ПОМИ РАН No