Бакалавриат
2022/2023![Цель освоения дисциплины](/f/src/global/i/edu/objectives.svg)
![Планируемые результаты обучения](/f/src/global/i/edu/results.svg)
![Содержание учебной дисциплины](/f/src/global/i/edu/sections.svg)
![Промежуточная аттестация](/f/src/global/i/edu/intermediate_certification.svg)
![Список литературы](/f/src/global/i/edu/library.svg)
Односторонние функции и их применения
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,
по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,
схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
Необходимы предварительные знания: знакомство с основными вычислительными
моделями: машинами Тьюринга, вероятностными машинами Тьюринга
и схемами из функциональных элементов.
Цель освоения дисциплины
- Изучение основных свойств односторонних функций.
- Изучить теоретические основы криптографии с открытым и закрытым ключом.
- Изучение криптографически стойких генераторов псевдослучайных чисел.
- Изучение криптографических основ задачи ауентификации.
Планируемые результаты обучения
- Умение решать задачи на тему "односторонние функции"
- Умение решать задачи на тему "Трудный бит"
- Знание основных криптографических протоколов (ауентификация, цифровая подпись, шифрование).
Содержание учебной дисциплины
- Слабо и сильно необратимые функции для равномерного и неравномерного противника. Односторонние функции. Если P=NP, то односторонних функций нет. Функция Mult. Функция SubsetSum
- Преобразование слабо необратимой функции в сильно необратимую. Полиномиально моделируемые и доступные распределения.
- Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
- Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
- Теорема о вероятностном декодировании списком кода Адамара.
- Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
- Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
- Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
- Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
- Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
- Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом.
- Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки
- Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ
- Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.
Промежуточная аттестация
- 2022/2023 учебный год 2 модуль0.4 * Домашние задания + 0.4 * Колллоквиум + 0.2 * Экзамен
Список литературы
Рекомендуемая основная литература
- Шень, А. Х. Классические и квантовые вычисления/ : учебное пособие / А. Х. Шень, М. Н. Вялый. — 2-е изд. — Москва : ИНТУИТ, 2016. — 273 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100617 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Goldreich, O. (2001). Foundations of Cryptography: Volume 2, Basic Applications. Cambridge: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=616989
- Goldreich, O. (2003). Foundations of Cryptography: Volume 1, Basic Tools (Vol. [Rev. ed.]). Cambridge, U.K.: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=112539