Курс лекций читался при поддержке компании Интел. Основные темы, изучаемые в течение курса: криптографические протоколы, доказательства с нулевым разглашением, псевдослучайные генераторы, электронные выборы, электронные платежи, многосторонние секретные вычисления.
| № |
Название лекции |
Слайды |
Конспект |
Аннотация |
| 1 |
Базовые протоколы |
 |
|
В первой лекции рассматриваются два криптографических протокола, которые как кирпичики используются в более сложных протоколах решения самых разных задач. "Разделение секрета" позволяет раздать нескольким участникам информацию таким образом, чтобы восстановить значение секретного ключа могли только определенные группы. "Привязка к биту" позволяет делать электронные ставки и посылать их букмекеру, при этом соблюдается одновременно секретность и неизменяемость ставки. |
| 2 |
Византийское соглашение и покер по телефону |
|
|
Рассматриваются два протокола. Византийское соглашение позволяет выбрать согласованное решение компании, в которой некоторые из участников («предатели») нарушают протокол. Покер по телефону — как раздать карты между несколькими участниками так, чтобы карты не пересекались, были случайными, и никто не знал чужих карт. |
| 3 |
Электронные выборы |
|
|
Обсуждается формализацию требований к проведению электронных выборов и рассмотрим ряд протоколов. Неформально, нужно так вычислить победившего кандидата, чтобы нельзя было узнать, кто конкретно за кого проголосовал. |
| 4 |
Электронные платежи |
|
|
На лекции будут рассмотрены разные подходы для проведения электронных платежей с использованием «цифровых наличных». Мы обсудим формализацию требований к электронным деньгам и рассмотрим ряд протоколов. |
| 5 |
Введение в нулевое разглашение |
|
|
Центральная лекция всего курса! Понятие нулевого разглашения признано одним из главных достижений всей теоретической информатики за последние 20 лет. Нулевое разглашение — это способ одного участника доказать теорему второму так, что второй сможет проверить верность доказательства, но сам при этом доказательства не узнает. Мы рассмотрим протоколы нулевого разглашения и применения этого понятия в разных областях. |
| 6 |
Нулевое разглашение для языков класса NP |
|
|
В рамках данной лекции доказывается очень важная теорема: принадлежность любому языку из класса NP можно доказать с нулевым разглашением! |
| 7 |
Проверяемое разделение секрета и передача данных вслепую |
|
|
Мы заканчиваем подготовку к самой главной теореме про многосторонние секретные вычисления (она будет рассмотрена на следующей лекции). Для этого нам нужно решить еще две криптографические задачи:
- передача данных вслепую (oblivious transfer): есть два участника. У Алисы есть два файла, Боб хочет скачать один из них. Необходимо осуществить скачивание таким образом, чтобы Боб мог скачать только один файл, а Алиса не узнает, какой файл был скачан;
- проверяемое разделение секрета: разделение секрета, в котором участники могут проконтролировать, действительно ли им выдали кусочки от одного секрета.
|
| 8 |
Многосторонние секретные вычисления |
|
|
Задачу можно сформулировать так: есть несколько участников, у каждого из них свое число. Они хотят сосчитать функцию от этих чисел так, что все узнают ответ, но никто не узнает ничего другого про чужие числа. Пример: два миллионера хотят определить, кто богаче, не называя своего состояния. В эту формулировку вкладывается огромное количество практических задач. |
| 9 |
Псевдослучайные генераторы |
|
|
В этот раз мы будем изучать следующий вопрос: как из маленькой строки битов (скажем, около 1000) породить бесконечную последовательность «случайных» битов. Мы построим несколько таких генераторов. |
| 10 |
Псевдослучайные функции |
|
|
Неформально, псевдослучайные функции — это семейства генераторов. На лекции рассказывается, как их построить, и для чего они нужны. |