Дневник лекций 2006/2007 года

8-Nov-2006

Доказательство NP-полноты задач о гамильтоновом цикле,
о коммивояжере и о сумме подмножеств (SUBSET-SUM).

Определение необратимой и односторонней функции.

15-Nov-2006

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

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

Слабо необратимые функции и слабо односторонние функции.
Построение односторонней функции из слабо односторонней функции.

22-Nov-2006

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

29-Nov-2006

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

Частично необратимые функции. Примеры: функция Рабина, функци RSA,
функция Блюма—Микэли.
Построение односторонней функции из любой частично односторонней функции.

Если P=NP, то односторонних функций нет.

29-Nov-2006

Свойства вычислительно неотличимых
последовательностей случайных величин.

Определение генераторов ПСЧ типа poly(n) -> poly(n)
и типа n -> бесконечность.

4-Dec-2006

Генераторы и слабо односторонние функции.

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

13-Dec-2006

Расширители. Построение генератора, исходя из расширителя.

Односторонние перестановки. Односторонние обобщенные перестановки, примеры.

12-Feb-2007

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

19-Feb-2007

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

27-Feb-2007

Вероятностное декодирование списком кода Адамара
(подготовка к доказательству
теоремы Левина-Голдрайха).

6-Mar-2007

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

Определение схемы шифрования с закрытым ключом.

13-Mar-2007

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

Определение схемы шифрования с открытым ключом.

Определение односторонней обобщенной перестановки с секретом.

20-Mar-2007

Повторение пройденного (лекцию читал А. Шень)

27-Mar-2007

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

Неинтерактивные протоколы привязки к биту (bit commitment).

3-Apr-2007

Неинтерактивные протоколы привязки к биту.

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

10-Apr-2007

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

17-Apr-2007

Протоколы аутентификации

24-Apr-2007

Протоколы аутентификации