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

Дневник лекций (весна 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

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

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