В следующий вторник 7 октября в ауд. 1408 Главного здания МГУ начнется полугодовой спецкурс Н.К. Верещагина "Односторонние функции и их применения".
Лекции будут по вторникам на пятой паре 16:45-18:20 на мехмате МГУ.
Аннотация.
По определению одностороннюю функцию легко вычислить, но обратную к ней вычислить трудно. Односторонние функции используются при построении генераторов случайных чисел, схем шифрования, протоколов электронной подписи и др.
Программа.
Односторонние функции (сильно и слабо). Теорема Левина - Гольдрайха о преобразовании слабо односторонней функции в сильно одностороннюю. Обобщение понятия односторонней функции --- частичные односторонние функции (с равномерным распределением). Односторонние перестановки. Функция Рабина, функция RSA, дискретная экспонента.
Статистически и вычислительно неотличимые случайные величины. Свойства вычислительно неотличимых случайных величин. Полиномиально генерируемые и доступные последовательности случайных величин. Генераторы псевдослучайных чисел (ПСЧ). Слабая необратимость генераторов ПСЧ.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом. Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки.
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ. Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.
Список источников
Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.
М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.
O. Goldreich.
Foundations of cryptography. Basic tools.
Cambridge Univ. Press. 2001. 400 p.
O. Goldreich.
Foundations of cryptography. Basic applications.
Cambridge Univ. Press. 2004