Дневник лекций (весна 2008 года)
12, 19, 26 февраля, 4, 11, 18 марта
Определение необратимой и односторонней функции.
Примеры предположительно односторонних функций.
Слабо необратимые функции и слабо односторонние функции.
Построение односторонней функции из слабо односторонней функции.
Определение статистически и вычислительно неотличимых
последовательностей случайных величин.
Свойства вычислительно неотличимых
последовательностей случайных величин.
Частично необратимые функции. Примеры: функция Рабина, функци RSA,
функция Блюма—Микэли.
Построение односторонней функции из любой частично односторонней функции.
Если P=NP, то односторонних функций нет.
Определение генераторов ПСЧ типа poly(n) -> poly(n)
Генераторы и слабо односторонние функции.
Расширители. Построение генератора, исходя из расширителя.
Трудный бит, характеризация расширителей в терминах трудного бита.
24-Mar-2008
Универсальное семейство хэш-функций.
Вероятностное декодирование списком кода Адамара
(лемма, используемая в доказательстве
теоремы Левина-Голдрайха).
31-Mar-2008
Теорема Левина—Голдрайха.
8-Apr-2008
Схема шифрования одного сообщения с закрытым ключом.
Построение такой схемы на основе генератора ПСЧ.
Схема шифрования нескольких сообщений с закрытым ключом.
Построение такой схемы на основе псевдослучайных функций.
15-Apr-2008
Построение псевдослучайных функций на основе генератора ПСЧ.
Односторонние функции с секретом (trapdoor functions)
22-Apr-2008
Схема шифрования с открытым ключом. Построение
такой схемы на основе односторонней частичной перестановки с секретом.
Неинтерактивные протоколы привязки к биту (bit commitment).
Построение такого протокола на основе односторонней инъективной
функции с полиномиально разрешимой областью определения.
29-Apr-2008
Интерактивные протоколы привязки к биту.
Построение такого протокола на основе генратора псевдослучайных
чисел.
5-May-2008
Протоколы бросания монетки по телефону (электронная монета).
Построение такого протокола на основе протокола
привязки к биту.
Протоколы аутентификации. Построение протокола аутентификации
на основе необратимости функции Рабина.