Кафедра математической логики и теории алгоритмов

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

3 сентября

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

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

10 сентября

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

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

17 сентября

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

24 сентября

Лекции не было.

1 октября

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

8 октября

Теорема о преобразовании полиномиальной машины Тьюринга в последовательность схем.

NP полнота задач CIRCUIT-SAT и 3CNF.

Вероятностные полиномиальные алгоритмы. Амплификация. Класс BPP.

15 октября

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

Включение BPP в nuP.

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

22 октября

Односторонние функции.
Примеры предположительно односторонних функций. Если P=NP, то односторонних функций нет

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

25 октября (суббота)

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

Статистическая неотличимость. Доступность.

29 октября

Частичные односторонние функции. Функция Рабина, функция RSA,
Дискретная экспонента.

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

5 ноября

Вычислительно неотличимые случайные величины.
Генераторы псевдослучайных чисел (определение).

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

12 ноября

Вероятностное декодирование списком кода Адамара.

Теорема Левина-Голдрайха.

19 ноября

Лемма о трудном бите. Преобразование полиномиально вычислимой перестановки и трудного бита для нее в генератор ПСЧ.

26 ноября

Окончание построения генератора ПСЧ.
Особенности этого генератора, построенного на основе односторонней
перестановки с секретом.

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

3 декабря

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

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

10 декабря

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

17 декабря

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

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

11 февраля

Повторение пройденного в осеннем семестре.

18 февраля

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

Протоколы игры в орлянку по телефону.

25 февраля

Теорема Цермело о детерминированности конечных игр и объяснение о том, кто имеет
выигрышную стратегию в построенной игре.

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

Построение многоразового протокола, устойчивого относительно подслушивания:
на основе семейства ПСФ для закрытого ключа и на основе односторонней перестановки
с секретом для открытого ключа.

4 марта

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

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

11 марта

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

Протоколы подписи и разные виды атаки на них.
Построение одноразового протокола с закрытым ключом для подписи одного бита.
Построение одноразового протокола с открытым ключом для подписи одного бита.

18 марта

Построение одноразового протокола с открытым ключом для подписи сообщений фиксированной длины

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

25 марта

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

31 марта (мы переехали со среды на вторник)

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

7 апреля

Доказательство знания свидетелей отношения (определение).
Алгоритм доказательства знания раскраски графа с нулевым разглашением (без доказательства).

14 апреля

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

21 апреля

Конфиденциальные вычисления: определения для полу-честного и нечестного противников.

Протоколы забывчивой передачи: построение для получестного противника на основе
улучшенной односторонней переставновки с секретом.

28 апреля

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

5 мая

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

12 мая

Универсальные семейства хэш-функций.
Лемма о сглаживании.

Построение генератора ПСЧ исходя из односторонней инъекции.