Сложность вычислений и основы криптографии

Общая информация
ЛекторД. М. Ицыксон
Семестрвесна 2013
Дата начала21.02.2013
Количество пар12
Язык курсарусский
Lecture notes
Вопросы к экзамену
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/13165-slozhnost-vychisleniy-i-osnovy-kriptog...
Аннотация Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с секретным и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.

Формально курс является продолжением курса Основы вычислимости и теории сложности, но на лекции приглашаются все желающие. Рекомендуется иметь представление о следующих понятиях: машины Тьюринга (детерминированные и недетерминированные), классы P, NP, PSPACE, NP-полнота, полиномиальная иерархия, булевы схемы. Все определения будут напоминаться по просьбе слушателей.

Литература:

  • S. Arora, B. Barak, Computational Complexity: A modern approach. Draft [pdf]
  • Ch. Papadimitriou, Computational Complexity.
  • O. Goldreich, Foundations of cryptography.
  • Н.К. Верещагин, Конспект лекций по теоретико-сложностным проблемам криптографии. [pdf]

Примерное описание каждой лекции представлено ниже.

Задачи по практике.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Вероятностные классы сложности
(21.02.2013 - 18:30 - 19:50)

Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в $ \Sigma_2^P \cap \Pi_2^P $. http://www.lektorium.tv/lecture/?id=14224
2. Интерактивные протоколы
(28.02.2013 - 18:30 - 19:50)

BPP содержится в $ \Sigma_2^P \cap \Pi_2^P $. Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов. Теорема Шамира (IP = PSPACE) и ее следствия. http://www.lektorium.tv/lecture/?id=14239
3. Игры Артура и Мерлина
(07.03.2013 - 18:30 - 19:50)

Универсальное семейство попарно независимых хеш-функций. Конструкция. Протокол для нижней оценки на размер множества. Публичные и скрытые случайные биты, игры Мерлина и Артура. Классы AM и MA. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства). Из NP-полноты изоморфизма графов следует, что полиномиальная иерархия схлопывается на 2 уровне. http://www.lektorium.tv/lecture/?id=14261
4. Подсчет числа подсказок. Лемма Вэлианта-Вазирани
(14.03.2013 - 18:30 - 19:50)

Лемма Вэлианта-Вазирани. И ее $ \bigoplus $-версия. Операции с числом выполняющих наборов и следствия из них. $ \bigoplus $-версия леммы Вэлианта-Вазирани для полиномиальной иерархии. http://www.lektorium.tv/lecture/?id=14281
5. Теорема Тода. Схемная сложность класс PP
(21.03.2013 - 18:30 - 19:50)

Классы $ \sharp P $ и $ PP $. Теорема Тода. $ P^{PP} = P^{\sharp P} $. Теорема Вэлианта о $ \sharp P $ -полноте 0/1 перманента (без доказательства). Интерактивное доказательство для перманента. Следствие об интерактивном доказательстве для $ P^{PP} $. Включение $ MA $ в $ PP $. Схемная сложность $ PP $. http://www.lektorium.tv/lecture/?id=14305
6. Вероятностно проверяемые доказательства
(28.03.2013 - 18:30 - 19:50)

Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. NP-трудность приближения MAX-3-SAT. Код Уолша-Адамара и его локальное декодирование. http://www.lektorium.tv/lecture/?id=14344
7. Экспоненциальная PCP-теорема
(04.04.2013 - 18:30 - 19:50)

NP$ \subseteq $PCP(poly(n),1). Базис Фурье для булевых функций. Тестирование функции на линейность. http://www.lektorium.tv/lecture/?id=14361
8. Односторонние функции
(11.04.2013 - 18:30 - 19:50)

Односторонние в наихудшем случае функции. Слабые и сильные односторонние функции. Полиномиально моделируемые ансамбли распределений. Примеры предположительно односторонних функций (произведение чисел, дискретный логарифм, SUBSET_SUM). Односторонние функции с полиномиально моделируемым распределением на входах. Доступные распределения. Частичные односторонние функции. http://www.lektorium.tv/lecture/?id=14383
9. Генератор псевдослучайных чисел
(18.04.2013 - 18:30 - 19:50)

Односторонние перестановки, примеры. Вычислительная неразличимость. Генератор псевдослучайных чисел. Односторонняя функция из генератора псевдослучайных чисел. Трудная случайная величина и вычислительная неразличимость. Конструкция (n + 1)-генератора на основе перестановки с трудным битом. Конструкция p(n)-генератора на основе перестановки с трудным битом. http://www.lektorium.tv/lecture/?id=14385
10. Трудный бит. Псевдослучайные функции.
(25.04.2013 - 18:30 - 19:50)

Построение трудного бита для односторонних перестановок. Декодирование списком кодов Уолша-Адамара. Конструкция семейства псевдо-случайных функций из генератора псевдослучайных чисел.
11. Протоколы с секретным и открытым ключом
(16.05.2013 - 18:30 - 19:50)

Одноразовые и многоразовые протоколы с секретным ключом. Пример одноразового протокола, который не является многоразовым. Конструкция многоразового протокол с секретным ключом. Протокол с открытым ключом. Эквивалентность одноразовой и многоразовой надежности. Конструкция, основанная на семействе односторонних перестановок с секретом.
12. Привязка к биту. Доказательства с нулевым разглашением.
(16.05.2013 - 20:00 - 21:45)

Интерактивный протокол привязки к биту. Стратегии, разглашающие только f(x). Разглашение при многократном применении стратегии. Интерактивные доказательства с нулевым разглашением. Протокол для изоморфизма графов. Протокол с нулевым разглашением для языка из NP (идея доказательства).
Ваша оценка: Пусто Средняя: 5 (1 голос)
Share |