Сложностная криптография и сложность в среднем

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

Примерная программа экзамена

  1. Односторонние в наихудшем случае функции. Односторонние функции, соглашения о длинах входа. Сильные и слабые односторонние функции.
  2. Семейство односторонних функций. Универсальная односторонняя функция.
  3. Трудный бит и его существование.
  4. Вычислительная неразличимость и ее свойства. Односторонняя функция из генератора псевдослучайных чисел. Конструкция $(n+1)$-генератора.
  5. Конструкция $p(n)$-генератора. Протокол с секретным ключом.
  6. Неразличимость повторных распределений.
  7. Семейство псевдослучайных функций.
  8. Неинтерактивный протокол привязки к биту.
  9. Интерактивный протокол привязки к биту.
  10. (*)Доказательства с совершенно нулевым разглашением, доказательства с вычислительно нулевым разглашением. Протокол для изоморфизма графов.
  11. (*)Нулевое разглашение с использованием дополнительной информации. Нулевое разглашения для класса $NP$ (схема доказательства).
  12. (**)Шифрование одного бита с открытым ключом: полная криптосистема.
  13. (**)Шифрование сообщений с открытым ключом: неразличимость, семантическая надёжность, их эквивалентность.
  14. Семейства односторонних перестановок с секретом, примеры. Протоколы с открытым ключом, основанные на перестановках с секретом.
  15. Одноразовый протокол электронной подписи одного бита. Одноразовый протокол электронной подписи фиксированного полиномиального числа битов.
  16. Одноразовый протокол электронной подписи произвольных сообщений полиномиальной длины на основе СТОК.
  17. Построение СТОК через СТОЗ. Конструкция СТОЗ.
  18. Одноразовый протокол электронной подписи произвольных сообщений полиномиальной длины на основе универсального семейства односторонних функций.
  19. Многоразовый протокол электронной подписи.
  20. (**)Bit commitment.
  21. (**)Совместное вычисление функции.
  22. Распределенные задачи. Полиномиальность в среднем по Левину и Импальяццо.
  23. (*)Пример распределения, для которого сложность в среднем и наихудшем случае эквивалентны.
  24. Доминирование распределений. Универсальное полиномиально
    моделируемые распределение. Сведения. Полная задача в $(NP,PSamp)$.
  25. Обратимые полиномиально моделируемые распределения ($PISamp$). Вычислимые распределения, включение $PComp\subseteq PISamp\subseteq PSamp$. Полнота задачи об ограниченной остановке в $(NP, PISamp)$.
  26. Классы $HeurBPP$, $AvgBPP$, задачи поиска. Универсальные семейства хеш-функций. Лемма Вэлиэнта-Вазирани для универсального семейства хэш-функций.
  27. Сведение задач поиска к задачам распознавания.
  28. Вероятностные сведения для задач поиска. Замкнутость класса $\widetilde{HeurBPP}$ относительно этих сведений.
  29. Вероятностное сведение $(NP, PSamp)$ к $(NP,U)$.
  30. (*)Из существования полной задачи с равномерным распределением относительно детерминированных сведений следует, что $NEXP=EXP$.
  31. (*)Односторонние функции и трудные задачи в $(NP,U)$.
  32. (**)Эквивалентность существования б.ч. псевдослучайных генераторов, функции, трудной для обращения в среднем, задач, трудных для эвристических аксепторов, б.ч. односторонних функций. (Без трудной импликации.)

Литература

  1. O. Goldreich, Foundations of cryptography
  2. A. Bogdanov, L. Trevisan, Average case complexity