Определение необратимой и односторонней функции. Примеры предположительно односторонних функций. Слабо необратимые функции и слабо односторонние функции.
Построение односторонней функции из слабо односторонней функции.
Определение статистически и вычислительно неотличимых последовательностей случайных величин. Свойства вычислительно неотличимых последовательностей случайных величин.
Частично необратимые функции. Примеры: функция Рабина, функци RSA, функция Блюма--Микэли. Построение односторонней функции из любой частично односторонней функции.
Если P=NP, то односторонних функций нет.
Определение генераторов ПСЧ типа poly(n) -> poly(n) Генераторы и слабо односторонние функции.
Расширители. Построение генератора, исходя из расширителя. Трудный бит, характеризация расширителей в терминах трудного бита.
Универсальное семейство хэш-функций.
Вероятностное декодирование списком кода Адамара (лемма, используемая в доказательстве теоремы Левина-Голдрайха).
Теорема Левина--Голдрайха.
Схема шифрования одного сообщения с закрытым ключом. Построение такой схемы на основе генератора ПСЧ.
Схема шифрования нескольких сообщений с закрытым ключом. Построение такой схемы на основе псевдослучайных функций.
Построение псевдослучайных функций на основе генератора ПСЧ.
Односторонние функции с секретом (trapdoor functions)
Схема шифрования с открытым ключом. Построение такой схемы на основе односторонней частичной перестановки с секретом.
Неинтерактивные протоколы привязки к биту (bit commitment). Построение такого протокола на основе односторонней инъективной функции с полиномиально разрешимой областью определения.
Интерактивные протоколы привязки к биту. Построение такого протокола на основе генратора псевдослучайных чисел.
Протоколы бросания монетки по телефону (электронная монета). Построение такого протокола на основе протокола привязки к биту.
Протоколы аутентификации. Построение протокола аутентификации на основе необратимости функции Рабина.