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

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

10 мая

Определение протокола цифровой подписи.
Построение протокола цифровой подписи одного бита.

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

3 мая

Неразглашение информации в протоколах аутентификации.
Построение протокола аутентификации
в предположении сильной необратимости функции RSA и дискретной экспоненты (в виде
задач).

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

26 апреля

Протоколы аутентификации. Построение протокола аутентификации
в предположении сильной необратимости функции Рабина. (Неразглашение
информации не доказано.)

19 апреля

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

12 апреля

Семинар: решение задач об интерактивных доказательствах
и о протоколах электронной монетки.

5 апреля

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

Лемма об уменьшении ошибки при последовательном повторении интерактивного
протокола.

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

29 марта

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

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

22 марта

Решение задач о неинтерактивных протоколах привязки к биту.

15 марта

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

Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (определение).
Построение протокола на основе генератора ПСЧ (только конструкция).

8 марта

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

1 марта

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

22 февраля

Коллоквиум.

15 февраля

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

10 февраля

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

16 декабря

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

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

9 декабря

Односторонние перестановки с секретом (trapdoor permutations).

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

2 декабря

Надежность генераторов по Яо.

Построение генератора n->\infty, исходя из генератора n->n+1

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

25 ноября

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

20 ноября

Код Адамара. Декодирование кодового слова, испорченного
менее чем в четверти позиций.
Переборный алгоритм декодирования списком кодового слова,
испорченного менее чем в половине позиций.
Полиномиальный вероятностный алгоритм декодирования
списком кодового слова,
испорченного менее чем
в половине позиций (набросок).

18 ноября

Трудный бит для данной функции.
Лемма о трудном бите.
Построение генератора k -> \infty, исходя из
трудного бита и односторонней перестановки.

4 ноября

Односторонние перестановки: определение и кандидаты

28 октября

Вычислительно неотличимые случайные величины и их свойства.
Генераторы ПСЧ вида k -> l и k -> \infty.
Генератор является слабо односторонней функцией.

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

Дискретная эспонента.

21 октября

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

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

14 октября

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

7 октября

NP трудные и NP полные задачи. Теорема Кука — Левина об NP полноте задачи о выполнимости
схем. NP полнота задач 3-КНФ,
Клика, Независимое подмножество, Вершинное покрытие,
Сумма подмножества.

30 сентября

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

Сводимость Карпа и ее свойства.

Включение BPP в P/poly.

23 сентября

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

Класс nuP. Включение P в nuP.
Класс P/poly и его совпадение с классом nuP.

16 сентября

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

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

9 сентября

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

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

2 сентября

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