Теоретическая криптография

Магистратура 2019/2020

Статус: Курс обязательный (Системное программирование)

Направление: 09.04.04. Программная инженерия

Кто читает: Базовая кафедра «Системное программирование» Института системного программирования им. В.П. Иванникова РАН (ИСП РАН)

Где читается: Факультет компьютерных наук

Когда читается: 2-й курс, 1, 2 модуль

Формат изучения: с онлайн-курсом

Преподаватели: Федоров Сергей Николаевич

Прогр. обучения: Системное программирование

Язык: русский

Кредиты: 8

Контактные часы: 56

Полная версия программы учебной дисциплины

Аннотация

Теоретическая криптография — раздел математики, изучающий математические модели криптографических протоколов, которые разрабатываются для защиты информации, передаваемой в небезопасной среде. Теория сложности вычислений позволяет обосновывать стойкость криптографических конструкций, используя строгие математические рассуждения. При этом возможно доказывать стойкость против любых действий заданного противника, не только относительно набора известных методов криптоанализа, как это принято в «практической» криптографии. В курсе даются строгие определения основных понятий теоретической криптографии, особое значение среди которых имеет односторонняя функция. Рассматриваются возможности и условия построения криптографических примитивов и протоколов, обладающих тем или иным типом стойкости.

Цель освоения дисциплины

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

Планируемые результаты обучения

Знать примеры криптографических протоколов (криптографических схем) и задач, которые они решают
Уметь строить математические модели криптографических средств защиты информации
Знать формулировки основных результатов теоретической криптографии
Уметь анализировать корректность обоснований стойкости криптографических протоколов
Уметь математически строго формулировать требования к стойкости криптографических протоколов (схем)
Владеть техниками вывода утверждений о возможности/невозможности криптографической защиты информации в тех или иных условиях
Знать определения основных понятий теоретической криптографии
Владеть навыками оперирования основными криптографическими понятиями

Содержание учебной дисциплины

Из истории криптографии
Примеры систем шифрования с античности до начала XX века. Шифр Вернама. Начало криптографии как науки. «Новые направления криптографии» (1970-е гг.), примеры криптографических протоколов (протокол Диффи—Хеллмана, криптосистема Эль-Гамаля, криптосистема RSA, схема подписи RSA, схема разделения секрета Блэкли, протокол Блюма подбрасывания монеты по телефону).
Предмет теоретической криптографии
ри задачи криптографии. Криптографические протоколы. Криптографические примитивы. Модель противника. Понятие стойкости. Криптосинтез и криптоанализ.
сновные положения теории Шеннона
Системы связи с секретностью. Критерии оценки таких систем. Априорные и апостериорные вероятности. Совершенная секретность и ее необходимое условие. Энтропия как мера неопределенности. Расстояние единственности. Идеальные системы.
Элементы теории сложности вычислений
Вычислительная задача: распознавательный и поисковый варианты (язык и отношение). Однородная и неоднородная модели вычислений: машина Тьюринга (детерминированная, недетерминированная, вероятностная, с оракулом) и семейство булевых схем. Тезисы Тьюринга—Чёрча и Эдмондса. Классы сложностей DTIME, P, EXP, NP, BPP, RP, PSPACE, P/poly и их соотношения. Теоремы о распознаваемости языков из P/poly семейством схем полиномиального размера и о соотношении классов BPP и P/poly.
Односторонняя функция и трудный предикат
Сильно и слабо односторонние функции. Теорема Яо. Односторонние семейства функций. Дискретная экспонента как кандидат в односторонние функции. Трудный предикат для функции. Теорема Гольдрайха—Левина.
Генераторы псевдослучайных последовательностей
Два определения криптографически стойкого генератора псевдослучайных последовательностей. Теорема Яо об эквивалентности этих определений. Теорема о «растягивании» выхода псевдослучайного генератора. Теорема Хостада—Импальяццо—Левина—Луби.
Криптосистемы с секретным ключом
Определение. Блоковые и потоковые криптосистемы. Модель противника (варианты атак и угроз). Пример определения стойкости и (гипотетический) пример стойкой криптосистемы. Необходимое и достаточное условие существования стойких криптосистем.
Криптографические хэш-функции
Определения семейства хэш-функций с трудно обнаружимыми коллизиями и одностороннего семейства хэш-функций. Лемма об l-композиции. Теорема об l(n)-композиции. Теорема Наора—Юнга. Теорема Ромпеля для хэш-функций.
Схемы электронной подписи
Определение и пример. Модель противника (варианты атак и угроз). Пример определения стойкости. Одноразовая схема Лэмпорта, преобразование её в многоразовую. Теорема Ромпеля о стойкой схеме электронной подписи.
Доказательства с нулевым разглашением
Интерактивное доказательство. Свойство нулевого разглашения (три варианта определения). Классы сложностей IP, ZK, SZK, PZK. Теорема Гольдрайха—Микали—Вигдерсона. Интерактивное доказательство с нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ. Протокол привязки к биту.
Криптосистемы с открытым ключом
Определение, пример. Атаки и угрозы. Семейства функций с секретом. Достаточное и необходимое условия существования стойких криптосистем с открытым ключом. Семейство функций Рабина как гипотетический пример семейства функций с секретом. Полиномиальная стойкость. Криптосистема Гольдвассер—Микали.
Системы электронных платежей
Общая схема. Задача неотслеживаемости. Схема подписи вслепую.

Элементы контроля

Домашнее задание (ДЗ)
Предлагается в ходе лекций для выполнения письменно во внеучебное время. Оценивается по мере готовности.
Контрольная работа (КР)
Проводится в течение 2—3 академических часов в письменной форме. Оценивается правильность и полнота решений предложенных задач.
Экзамен (Э)

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.15 * Домашнее задание (ДЗ) + 0.15 * Контрольная работа (КР) + 0.7 * Экзамен (Э)

Программа дисциплины