(русский / in Russian) Сложность вычислений и основы криптографии | Дмитрий Ицыксон (The complexity of computing and the basics of cryptography | Dmitry Itsykson)

# playlist (click the video's upper-left icon)

source: Лекториум          2013年7月16日
Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира 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.
Н.К. Верещагин, Конспект лекций по теоретико-сложностным проблемам криптографии.
Подписывайтесь на канал: https://www.lektorium.tv/ZJA
Следите за новостями:
https://vk.com/openlektorium
https://www.facebook.com/openlektorium