Криптография как учение о шифрах появилась несколько тысячелетий назад, однако наукой она стала лишь во второй половине 20-го века, когда появились строгое определения криптографических протоколов, понятий о их надежности и сформировалась культура строгих доказательств надежности. В курсе пойдет речь о теоретических основаниях криптографии на языке теории сложности. Детали практических реализаций либо не будут упоминаться совсем, либо будут упоминаться лишь вскользь.
К сожалению, только в очень редких частных ситуациях в криптографии удается безусловно доказать утверждение о надежности некоторого протокола. Обычно утверждение о надежности основывается на криптографических предположениях: либо о вычислительной трудности конкретной задачи, либо о существовании криптографических примитивов (кирпичиков, на которых строятся криптографические протоколы). В первой части курса речь пойдет об основных криптографических примитивах: односторонние функции, трудный бит, генератор псевдослучайных чисел, семейство псевдослучайных функций и пр.
Во второй части курса на основе криптографических примитивов мы построим конкретные криптографические протоколы: протокол с секретным ключом, протокол с открытым ключом, привязка к биту, протокол подкидывания монетки, секретное вычисление функций, протокол цифровой подписи, доказательства с нулевым разглашением и пр.
Третья часть курса согласно пожеланиям слушателей может быть посвящена либо теории сложности в среднем, либо построению гомоморфной криптосистемы (в этой криптосистеме можно выполнять алгоритмы с зашифрованными данными, не расшифровывая их), либо какой-нибудь другой теме.
Курс требует от слушателей знаний основ теории сложности (классы P, NP, сведения, NP-полные задачи, булевы схемы, вероятностные алгоритмы, желательно слышать про интерактивные доказательства), дискретной теории вероятности и начальных сведений из линейной алгебры, теории чисел и математического анализа. От слушателей ожидается готовность воспринимать сложные определения и сложные доказательства теорем (лектор постарается сделать все возможное, чтобы облегчить восприятие). Курс состоит из лекций и практических занятий, на которых будут обсуждаться задачи на темы лекций.
Курс входит в магистерскую программу теоретическая информатика Академического университета.
Рекомендуемая литература:
Теоретико-сложностные проблемы криптографии, http://lpcs.math.msu.su/~ver/teaching/cryptography/index.html
