#матлог #учёба #спецкурс

В следующий вторник 7 октября в ауд. 1408 Главного здания МГУ начнётся полугодовой спецкурс Н.К. Верещагина "Односторонние функции и их применения".

Лекции будут по вторникам на пятой паре 16:45-18:20 на мехмате МГУ, аудитория 1408.

❗Ранее в группе было объявление про этот спецкурс, но во времени проведения была ошибка! Поэтому публикуем объявление повторно, дополнив его информацией о спецкурсе.

Аннотация.
По определению одностороннюю функцию легко вычислить, но обратную к ней вычислить трудно. Односторонние функции используются при построении генераторов случайных чисел, схем шифрования, протоколов электронной подписи и др.

Программа.
Односторонние функции (сильно и слабо). Теорема Левина - Гольдрайха о преобразовании слабо односторонней функции в сильно одностороннюю. Обобщение понятия односторонней функции —- частичные односторонние функции (с равномерным распределением). Односторонние перестановки. Функция Рабина, функция 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

➰ ВК