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

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

Подсчет количества операций в алгоритме Эвклида нахождения НОД натуральных чисел.

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

Равнодоступные адресные машины (РАМ). Моделирование РАМ на многоленточных машинах Тьюринга.

Вероятностные машины Тьюринга (два равносильных определения). Определение вычисления данной функции с ошибкой не более $\epsilon$. Классы FBPP и BPP. Независимость этих классов от разрешенной вероятности ошибки.

Вероятностный алгоритм Миллера--Рабина распознавания простоты данного числа.

Доказательство корректности алгоритма Миллера--Рабина. Полиномиальный алгоритм извлечения корня данной степени.

Схемы из функциональных элементов. Классы n.u.P и P/poly. Включение класса P в класс n.u.P

Совпадение классов n.u.P и P/poly. Включение класса BPP в класс P/poly.

NP-представления и класс NP. Примеры языков из класса NP. Сводимость Карпа и основные ее свойства. Сводимость задачи КЛИКА к задаче НЕЗАВИСИМОЕ МНОЖЕСТВО, сводимость последней задачи к задаче ВЕРШИННОЕ ПОКРЫТИЕ, сводимость задачи о выполнимости КНФ к задаче ЦЛП и сводимость задачи 4-КНФ к задаче 3-КНФ.

Классы PSPACE и EXP. Включение класса NP в класс PSPACE и класса PSPACE в класс EXP.

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

NP-полнота задачи о сумме подмножеств. Слабо и сильно односторонние функции. Кандидаты. Статистически неотличимые случайные величины.

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

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

Односторонние перестановки. Трудный бит для данной односторонней функции. Построение генератора, исходя из односторонней перестановки и трудного бита.

Обобщенные перстановки. Построение генератора, исходя из обобщенной перестановки и трудного бита. Обратный переход (от генератора к обобщенной перестановке и трудному биту). Неотличимость случайных величин по Яо. Эквивалентность неотличимости по Яо и вычислительной неотличимости (в случае, когда одна из величин равномерно распределена).

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

Доказательство леммы о декодировании списком кода Адамара.

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

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

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

Неинтерактивные протоколы привязки к биту. Построение такого протокола на основе необратимой инъективной функции.

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

18 февраля лекции не было!

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

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

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

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

Лемма о неразглашение информации при последовательном выполнении неразглашающей стратегии.

Схемы аутентификации. Построение схемы аутентификации на основе необратимости функции Рабина.

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

Семейства хэш-функций с трудно обнаружимыми коллизиями. (Свободные от коллизий хэш-функции.)

Схема одноразовой цифровой подписи сообщения произвольной длины на основе семейства хэш-функций с трудно обнаружимыми коллизиями.

Семейства пар функций с трудно обнаружимыми зацепленями. Использование таких семейств для пострения семейств хэш-функций с трудно обнаружимыми коллизиями.

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

Схема Лампорта подписи одного сообщения произвольной длины на основе одноразовой цифровой подписи сообщения фиксированной длины и семейства хеш-функций (без доказательства).

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

Oblivious transfer (забывающая передача). Улучшенная перестановка с секретом. Построение забыающей передачи с помощью улучшенной перестановки с секретом.