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

7 сентября

Равнодоступные адресные машины, меры сложности: количество операций,
длина машинного слова, количество использованных регистров.
Полиномиальные РАМ (по всем трем мерам сложности).

Полиномиальные алгоритмы нахождения НОД и быстрого возведения в
степень по данному модулю.

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

14 сентября

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

Моделирование многолентночных машин на одноленточных.

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

Классы полиномиально вычислимых
функций и полиномиально разрешимых предикатов.
Независимость этих классов от вычислительной модели.

21 сентября

Вероятностные алгоритмы.
Полиномальные по времени вероятностные алгоритмы (время ограничено
полиномом от длины входа при любых исходах бросаний).
Определение вычисления с ограниченной ошибкой.
Уменьшение вероятности ошибки с помощью повторения.
Классы BPP и FBPP.

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

28 сентября

Схемы из функциональных элементов.
Верхняя оценка O(n2^n) схемной сложности
любой булевой функции.

Класс nuP. Включение P в nuP.

5 октября

Класс P/poly и его совпадение с классом nuP.
Принадлежность классу Р равносильно наличию алгоритма, который за
полиномиальное от n время находит схему, вычисляющую сужение предиката
на слова длины n.

Включение BPP в nuP.
Обзор известных нижних оценок.

12 октября

Класс NP.
Примеры задач из класса NP. Сводимость Карпа и ее свойства.
Определение NP трудной и NP полной задачи.

Теорема Кука-Левина о NP полноте задачи выполнимости схем из
функциональных элементов. NP полнота задач 3-КНФ и Клика.

19 октября

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

26 октября

Определение слабо и сильно необратимой функции. Односторонние функции.
Примеры. Обратимость любой полиномиально вычислимой
функции в предположении P=NP.

2 ноября

Теорема Левина и Голдрайха о преобразовании слабо односторонней
функции в сильно одностороннюю функцию.

9 ноября

Статистическое расстояние и доступные распределения.
Односторонние частичные функции. Примеры предположительно
односторонних частичных функций: функция Рабина и функция RSA.

16 ноября

Вычислительная неотличимость последовательностей случайных величин.
Генераторы ПСЧ, конечные и бесконечные. Слабая необратимость
генераторов. Существование генераторов при условии существования
односторонних функций.

23 ноября

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

30 ноября

Трудно вычислимые случайные величины.
Трудный бит для односторонней перестановки. Построение генератора
на основе трудного бита и односторонней перестановки (или функции,
сохраняющей равномерное распределение).

7 декабря

Построение генератора с любой степенью расширения из
генератора с минимальной степенью расширения.

14 декабря

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

8 февраля

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

15 февраля

Коллоквиум.

22 февраля

Шифрование с закрытым ключом. Одноразовая схема на основе генератора ПСЧ.
Многоразовая схема на основе семейства ПСФ и одноразовой схемы.

29 февраля

Многоразовая схема на основе семейства ПСФ и одноразовой схемы.
(Доказательство)

Схемы шифрования с открытым ключом (определение).

7 марта

Семейства перестановок с секретом.
Трудный бит перестановки с секретом.
Построение семейства перестановок с трудным битом.

Схемы шифрования с открытым ключом одного бита.

14 марта

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

Неинтерактивные схемы привязки к биту.

21 марта

Интерактивные алгоритмы.
Интерактивные протоколы привязки к биту.

28 марта

Протоколы подбрасывания монетки.

4 апреля

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

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

11 апреля

Неразглашение информации. Теорема о последовательном
повторении неразглашающего протокола.

Лемма о достаточности устойчивости относительно
атаки на протокол идентификации без подслушивания и неразглашения
информации.

18 апреля

Протокол индентификации с открытым ключом на основе функции Рабина.

25 апреля

Семейства хэш-функций: УСОХ и СТОК.
Построение СТОК, исходя из гипотезы о сильной
необратимости функции Рабина.

2 мая

Одноразовые схемы цифровой подписи: одного бита, сообщения
фиксированной длины и сообщения произвольной длины.

16 мая

Построение многоразовой схемы цифровой подписи на основе
одноразовой схемы подписи сообщений произвольной длины
и семейства ПСФ.