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

Санкт-Петербург, весна 2013

Описание

Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с открытым и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.

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

Литература:

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

Преподаватели

Список лекций

Вероятностные классы сложности

Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в \( \Sigma_2^P \cap \Pi_2^P \)

Интерактивные протоколы

BPP содержится в \( \Sigma_2^P \cap \Pi_2^P \). Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов. Теорема Шамира (IP = PSPACE) и ее следствия.

Игры Артура и Мерлина

Универсальное семейство попарно независимых хеш-функций. Конструкция. Протокол для нижней оценки на размер множества. Публичные и скрытые случайные биты, игры Мерлина и Артура. Классы AM и MA. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства). Из NP-полноты изоморфизма графов следует, что полиномиальная иерархия схлопывается на 2 уровне.

Подсчет числа подсказок. Лемма Вэлианта-Вазирани

Лемма Вэлианта-Вазирани. И ее \( \bigoplus \)-версия. Операции с числом выполняющих наборов и следствия из них. \( \bigoplus \)-версия леммы Вэлианта-Вазирани для полиномиальной иерархии.

Теорема Тода. Схемная сложность класс PP

Классы \( \sharp P \) и \( PP \). Теорема Тода. \( P^{PP} = P^{\sharp P} \). Теорема Вэлианта о \( \sharp P \) -полноте 0/1 перманента (без доказательства). Интерактивное доказательство для перманента. Следствие об интерактивном доказательстве для \( P^{PP} \). Включение \( MA \) в \( PP \). Схемная сложность \( PP \).

Вероятностно проверяемые доказательства

Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. NP-трудность приближения MAX-3-SAT. Код Уолша-Адамара и его локальное декодирование.

Экспоненциальная PCP-теорема

NP\( \subseteq \)PCP(poly(n),1). Базис Фурье для булевых функций. Тестирование функции на линейность.

Односторонние функции

Односторонние в наихудшем случае функции. Слабые и сильные односторонние функции. Полиномиально моделируемые ансамбли распределений. Примеры предположительно односторонних функций (произведение чисел, дискретный логарифм, SUBSET_SUM). Односторонние функции с полиномиально моделируемым распределением на входах. Доступные распределения. Частичные односторонние функции.

Генератор псевдослучайных чисел

Односторонние перестановки, примеры. Вычислительная неразличимость. Генератор псевдослучайных чисел. Односторонняя функция из генератора псевдослучайных чисел. Трудная случайная величина и вычислительная неразличимость. Конструкция (n + 1)-генератора на основе перестановки с трудным битом. Конструкция p(n)-генератора на основе перестановки с трудным битом.

Трудный бит. Псевдослучайные функции.

Построение трудного бита для односторонних перестановок. Декодирование списком кодов Уолша-Адамара. Конструкция семейства псевдо-случайных функций из генератора псевдослучайных чисел.

Протоколы с секретным и открытым ключом

Одноразовые и многоразовые протоколы с секретным ключом. Пример одноразового протокола, который не является многоразовым. Конструкция многоразового протокол с секретным ключом. Протокол с открытым ключом. Эквивалентность одноразовой и многоразовой надежности. Конструкция, основанная на семействе односторонних перестановок с секретом.

Привязка к биту. Доказательства с нулевым разглашением.

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