Дневник лекций (осень 2009 года, весна 2010 года)
19 мая
Протокол конфиденциального вычисления любой пары полиномиально
вычислимых функций
на основе протокола OT^4_1 (для полу-честных игроков).
Доказательства знания. Переделывание
протокола конфиденциального вычисления для полу-честных игроков
в протокол конфиденциального вычисления для нечестных игроков.
12 мая
Протоколы конфиденциальных вычислений: определение с полу-честными
игроками. Забывающая передача (oblivious transfer) OT^k_1.
Улучшенные односторонние перестановки с секретом (УПС) и построение
протокола OT^k_1, исходя из УПС (для полу-честных игроков).
5 мая
Еще раз о протоколе многоразовой подписи.
Пороговые схемы разделения секрета (схема Блейкли и Шамира).
Схемы разделения секрета с данным доступом.
28 апреля
Протокол многоразовой подписи
на основе протокола одноразовой подписи сообщения произвольной длины
и семейства случайных функций.
21 апреля
Протокол одноразовой цифровой подписи сообщения
фиксированной длины. Протокол одноразовой
цифровой подписи сообщения произвольной длины
(на основе УСОХ).
14 апреля
Протоколы цифровой подписи (общее определение, атака самая общая — с выбором
сообщений для подписи). Протокол цифровой подписи одного бита.
Универсальные семейство односторонних хешфункций.
Построение УСОХ на основе тотальной односторонней перестановки.
31 марта
Семейства функций с трудно обнаружимыми коллизиями (СТОК).
Семейства функций с трудно обнаружимыми зацеплениями (СТОЗ), построение такого
семейства на основе функции Рабина. Построение СТОК исходя из СТОЗ.
Неразглашение информации в протоколе аутентификации.
29 марта
Интерактивное доказательство с нулевым разглашением
раскрашиваемости графа в три цвета.
24 марта
Протоколы аутентфикации. Построение протокола аутентификации на основе
необратимости функции Рабина. Доказательство (без неразглашения информации).
Лемма о последовательном повторении неразглашающей стратегии.
17 марта
Интерактивное доказательство неизоморфности двух графов.
Интерактивное доказательство с нулевым разглашением
изоморфности двух графов.
(Доказательство неразглашения было по модулю леммы о последовательном
повторении неразглашающей стратегии.)
10 марта
Интерактивные протоколы привязки к биту.
Построение ИППБ на основе генератора ПСЧ
Протоколы бросания монетки по телефону.
Построение такого протокола на основе протокола привязки к биту.
3 марта
Неинтерактивные протоколы привязки к биту.
Построение НППБ на основе односторонней инъекции с полиномиально
разрешимой областью определения.
Построение НППБ на основе односторонней инъекции, для которой
полиномиально генерируемая трудная случайная величина принимает
значения только в области определения функции.
Определение интерактивного протокола привязки к биту.
24 февраля
Схемы шифрования с открытым ключом (с атакой без выбора сообщений).
Конструкция СШОК одного бита на основе необратимой
перестановки с секретом. Конструкция СШОК сообщений любой длины
на основе СШОК одного бита. Прямая конструкция СШОК
сообщений любой длины на основе необратимой
перестановки с секретом.
Трудный бит для необратимой перестановки с секретом.
Генераторы ПСЧ, полученные из необратимой перестановки с секретом.
17 февраля
Необратимые перестановки с секретом (trapdoor permutations): определение и
кандидаты.
Доказательство устойчивости многоразовой схемы
относительно атаки второго вида (с выбором сообщений).
10 февраля
Напоминание определений схем шифрования и их построения. Доказательство
устойчивости многоразовой схемы
относительно атаки первого вида (без выбора сообщений).
16 декабря
Схема шифрования с закрытым ключом. Два вида схем — одноразовые и многоразовые.
Два вида атаки на многоразовые схемы: перехват зашифрованных сообщений и
атака с выбором шифруемых сообщений и последующим перехватом одного сообщения.
Построение многоразовой схемы, исходя из одноразовой схемы
и семейства ПСФ.
9 декабря — Коллоквиум
2 декабря
Псевдослучайные функции (доказательство).
Сильно псевдослучайные функции (определение и доказательство).
25 ноября
Доказательство леммы о декодировании списком кода Адамара.
Построение генератора ПСЧ с произвольной степенью расширения
из генератора p(n)->p(n)+1.
Псевдослучайные функции (определение и построение).
18 ноября
Теорема Левина-Гольдрайха о трудном бите.
Лемма о декодировании списком кода Адамара.
11 ноября
Лемма о трудном бите. Построение генератора, исходя из односторонней
перестановки с трудным битом.
Понятие трудного бита для данной функции. Если трудный бит для
перестановки существует, то она сильно необратима.
Пример: последний бит, выдаваемый генератором ПСЧ, является трудным
битом для остатка.
4 ноября лекции не было (праздник)
28 октября
Свойства вычислительно неотличимых
случайных величин.
Полиномиально генерируемые и доступные последовательности
случайных величин.
Обобщение понятия односторонней функции — частичные односторонние
функции (с равномерным распределением).
Односторониие перестановки. Функция Рабина, функция RSA,
дискретная экспонента.
21 октября
Доказательство теоремы Левина — Гольдрайха о
преобразовании
слабо односторонней
функции в сильно одностороннюю.
Определение генераторов ПСЧ k(n)->l(n).
Статистическое расстояние между случайными величинами.
Статистическая и вычислительная неотличимость последовательностей
случайных величин. Рефлексивность, транзитивность и симметричность.
19 октября (лекция вместо пропущенной лекции 14 октября)
Односторонние функции (сильно и слабо).
Обратимость любой функции при условии P=NP.
Преобразование слабо односторонней
функции в сильно одностороннюю.
7 октября
NP полнота задач 3-КНФ, КЛИКА, ВершинноеПокрытие, 3-раскраска и
СуммаПодмножества.
30 сентября
Нижние оценки для времени с помощью сводимости и теорем о иерархии
(кратко и без доказательств).
Класс NP. Примеры языков из NP: составные числа, изоморфные графы,
выполнимость формул и схем, 3-раскраска, Сумма подмножества, Разбиение,
вершинное покрытие.
Сводимости задач (по Карпу). Примеры: 4-КНФ сводится к 3-КНФ (и обратно),
КНФ сводится к ЦЛП.
Определение NP полной и NP трудной задачи. Теорема Кука-Левина об NP
полноте задачи выполнимости схем.
23 сентября
Схемы полиномиального размера для сложения и умножения.
Класс nuP. Включение P в nuP.
Класс P/poly и его совпадение с классом nuP.
Включение BPP в nuP.
16 сентября
Уменьшение вероятности ошибки с помощью повторения.
Классы BPP и FBPP.
Вероятностный полиномиальный алгоритм проверки полиномиального
тождества.
Схемы из функциональных элементов. Верхняя оценка O(n2^n) схемной сложности
любой булевой функции.
9 сентября
Моделирование РАМ на машинах Тьюринга. Классы полиномиально вычислимых
функций и полиномиально разрешимых предикатов.
Независимость этих классов от вычислительной модели.
Вероятностные алгоритмы.
Полиномальные по времени вероятностные алгоритмы (время ограничено
полиномом от длины входа при любых исходах бросаний).
Определение вычисления с ограниченной ошибкой.
5 сентября
Однолентночные и многоленточные машины Тьюринга. Время работы и память
как меры сложности. Оценка количества шагов для переворачивания слова.
Полиномиальные машины Тьюринга (по времени и памяти).
Равнодоступные адресные машины, меры сложности: количество операций,
длина машинного слова, количество использованных регистров.
Полиномиальные РАМ (по всем трем мерам сложности).
Моделирование машин Тьюринга на РАМ.