Односторонние функции и их применения

Бакалавриат 2023/2024

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Верещагин Николай Константинович, Мануйленко Никита Сергеевич

Язык: русский

Кредиты: 5

Контактные часы: 56

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,  по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,  схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации. Необходимы предварительные знания: знакомство с основными вычислительными  моделями: машинами Тьюринга, вероятностными машинами Тьюринга  и схемами из функциональных элементов.

Цель освоения дисциплины

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

Планируемые результаты обучения

Умение решать задачи на тему "односторонние функции"
Умение решать задачи на тему "Трудный бит"
Знание основных криптографических протоколов (ауентификация, цифровая подпись, шифрование).

Содержание учебной дисциплины

Слабо и сильно необратимые функции для равномерного и неравномерного противника. Односторонние функции.  Если P=NP, то односторонних функций нет.  Функция Mult.  Функция SubsetSum
Преобразование слабо необратимой функции в сильно необратимую. Полиномиально моделируемые и доступные распределения.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом.
Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ
Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.

Элементы контроля

Домашние задания
В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно присылать семинаристу.
Коллоквиум
Придя в аудиторию или подключившись к конференции в то время, в которое записались (см. ниже ссылку на таблицу), Вы получите  один вопрос на теорему с доказательством.  На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками.  После ответа на этот вопрос Вы получите второе задание, состоящее из двух вопросов на определение или формулировку теоремы.  На эти вопросы надо отвечать сразу.  Коллоквиум Вы сдаёте устно он-лайн одному из преподавателей.  Для уточнения оценки  преподаватель может задавать дополнительные вопросы на знание определений и  основных фактов курса.  Оценка за коллоквиум формируется следующим образом.  Полный ответ на первый вопрос оценивается в 5 баллов, а полные ответы на другие два вопроса --- в 2.5 балла.
Экзамен
Письменный экзамен длительностью 90 минут. Экзамен будет происходить очно, вариант будет состоять из 4 задач. Разрешено пользоваться печатными конспектами лекций, а также любыми бумажными материалами. Выходить из аудитории во время экзамена нельзя. Студенты на он-лайн обучении пишут экзаменационное задание с прокторингом. Более подробная инструкция тут: 1. Присоединиться к конференции надо на десять минут раньше, затем станут доступны задания, которые надо загрузить по ссылке в чате конференции. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена. 2. Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций (можно и на электронный вариант), писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ. 3. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

Промежуточная аттестация

2023/2024 учебный год 2 модуль
Итоговая оценка складывается из оценок за домашние задания, за коллоквиум, за экзамен и за дополнительные сложные задачи. Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов. Оценки за домашние задания, за коллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решенную дополнительную задачу к итоговой оценке прибавляется 0.5 балла. Точнее, итоговая оценка выставляется по следующий формуле: MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи).

Список литературы

Авторы

Верещагин Николай Константинович
Милованов Алексей Сергеевич

Программа дисциплины