Дневник лекций (осень 2015 года, весна 2016 года)

1 сентября

Одноленточные и многоленточные машины Тьюринга. Время работы и память как меры сложности. Оценка количества шагов для копирования слова.

Моделирование многолентночных машин Тьюринга на одноленточных МТ. Полиномиально вычислимые функции и полиномиально разрешимые предикаты. Классы P и PF.

8 сентября

Равнодоступные адресные машины и связанные с ними ресурсы. Оценка времени для алгоритма Евклида и проверки простоты.

Моделирование машин Тьюринга на РАМ.

15 сентября

Моделирование РАМ на машинах Тьюринга.

Класс NP.

22 сентября

Сводимость Карпа. Сведение КНФ к ЦЛП.

Схемы из функциональных элементов. Преобразование полиномиальных машин Тьюринга в схему из функциональных элементов.

29 сентября

Теорема об NP полноте задачи CircuitSat. NP полнота задачи 3-CNF.

6 октября

NP полноте задач Клика, ВершинноеПокрытие, 3-Раскраска, СуммаПодмножества.

Вероятностные машины Тьюринга. Классы BPP и BPPF.

13 октября

Вероятностный алгоритм для проверки алгебраических тождеств.

Амплификация. Классы n.u.P и P/poly и их совпадение. Включение
BPP в P/poly.

20 октября

Сильно необратимые функции для равномерного и неравномерного противников. Сильно односторонние функции.

Если P=NP, то сильно односторонних функций нет.

27 октября

Слабо односторонние функции. Преобразование слабо односторонней функции в сильно одностороннюю функцию.

3 ноября

Полиномиально моделируемые и доступные последовательности распределений вероятностей. Односторонние частичные функции. Односторонние перестановки. Пример — функция Рабина.

10 ноября

Функция RSA и дискретная экспонента.

17 ноября

Одностороние перестановки с секретом.

24 ноября

Статистически неотличимые последовательности случайных величин. Вычислительно неотличимые последовательности случайных величин.

Генераторы псевдослучайных чисел: определение. Любой генератор является слабо односторонней функцией.

1 декабря

Свойства вычислительно неотличимых случайных величин.

Определение трудного бита для данной односторонней перестановки. Общий план построения генератора исходя из односторонней перестановки.

8 декабря

Лемма Яо о трудном бите. Построение генератора ПСЧ, исходя из односторонней перестановки и трудного бита (доказательство).

15 декабря

Генераторы, производящие бесконечное количество бит, построение такого генератора на основе односторонней перестановки и трудного бита.

Генераторы, построенные из односторонней перестановки с секретом и трудного бита для нее.

8 февраля

Теорема Левина — Голдрайха о построении трудного бита для односторонней перестановки. Основная лемма: декодирование списком кода Адамара.

15 февраля

Теорема Левина — Голдрайха о построении трудного бита для односторонней перестановки.

Псевдослучайные функции — интуитивный подход.

20 февраля (вместо 22 февраля)

Псевдослучайные функции — построение и доказательство ослабленной надёжности.

29 февраля

Псевдослучайные функции — усиленная надежность. Построение семейства ПСФ, область определение которых состоит из всех слов.

Схемы шифрования. Три вида атак.

14 марта

Построение одноразовой СШЗК на основе генератора ПСЧ.

Построение многоразовой СШЗК на основе семейства псевдослучайных функций с помощью побитового шифрования сообщений.

21 марта

Построение более экономной многоразовой СШЗК на основе семейства псевдослучайных функций и генератора ПСЧ. Объяснение, почему она выдерживает атаку с подбрасыванием сообщений.

28 марта

Схемы шифрования с открытым ключом. Построение СШОК на основе односторонней перестановки с секретом.

4 апреля

Неинтерактивные протоколы привязки. Построение такого протокола на основе односторонней перестановки (частичной).

18 апреля

Интерактивные протоколы привязки. Построение такого протокола на основе генератора ПСЧ.

19 апреля (замена занятия от 11 апреля)

Протоколы электронной монеты.

25 апреля

Протоколы идентификации с закрытым и открытым ключом. Три вида атаки на такие протоколы.

Построение протоколов идентификации с закрытым и открытым ключом, выдерживающих атаку без подслушивания и атаку с подслушиванием.

16 мая

Протокол идентификации с открытым ключом на основе необратимости функции Рабина. Доказательство того, что он выдерживает простую атаку.

23 мая

Протокол идентификации с открытым ключом на основе необратимости функции Рабина. Доказательство того, что он имеет нулевое разглашение, и, следовательно, выдерживает атаку с фальшивым банкоматом.