OWF2021 — различия между версиями
Milovanov (обсуждение | вклад) |
Milovanov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
= Односторонние функции и их применения (4-ий курс ТИ) 2021 год = | = Односторонние функции и их применения (4-ий курс ТИ) 2021 год = | ||
| − | Лекции проходят по четвергам 14:40 - 16:00 в ауд. D201, семинары по средам 18:10-19:30 в ауд. | + | Лекции проходят по четвергам 14:40 - 16:00 в ауд. D201, семинары по средам 18:10-19:30 в ауд. D502. Первая лекция 2 сентября, первый семинар 8 сентября. |
==Новости== | ==Новости== | ||
Версия 17:10, 22 сентября 2021
Содержание
- 1 Односторонние функции и их применения (4-ий курс ТИ) 2021 год
Односторонние функции и их применения (4-ий курс ТИ) 2021 год
Лекции проходят по четвергам 14:40 - 16:00 в ауд. D201, семинары по средам 18:10-19:30 в ауд. D502. Первая лекция 2 сентября, первый семинар 8 сентября.
Новости
- 16 сентября Лекция 30 сентября отменяется!
Семинар 15 сентября будет онлайн. Ссылка: meet.google.com/itr-jufj-bxb
Контакты
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, телеграм: nikolay_vereshchagin
Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov
Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy
Краткое описание
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону, по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел, схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
Необходимы предварительные знания: знакомство с основными вычислительными моделями: машинами Тьюринга, вероятностными машинами Тьюринга и схемами из функциональных элементов.
Отчётность по курсу и критерии оценки
Итоговая оценка складывается из оценок за домашние задания, оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценки за домашние задания - с коэффициентом 0.2.
В домашних заданиях иногда будут даваться бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.
Домашние задания
В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу или лектору устно (онлайн или лично). Сдача домашних заданий после их срока невозможна.
Сдать ДЗ лектору можно с помощью Google Meet https://meet.google.com/noy-cait-jph
Сдать ДЗ семинаристу можно ... .
Коллоквиум и письменный экзамен
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов, и заново сдать коллоквиум и/или экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
Правила округления
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.
Коллоквиум
Коллоквиум будет ... .
[ Программа коллоквиума.]
Экзамен
[ Программа экзамена.]
Пересдачи
Примерные сроки контрольных мероприятий
Первое домашнее будет выложено 24 сентября, срок сдачи 14 октября.
Второе домашнее будет выложено 15 октября, крайний срок сдачи 3 ноября.
Третье домашнее будет выложено 5 ноября, крайний срок сдачи 25 ноября.
Четвертое домашнее будет выложено 26 ноября, крайний срок сдачи - 16 декабря.
Домашние задания
[Домашнее задание 1] Cрок сдачи
Результаты
Прочитанные лекции
Лекция 1 (2 сентября).
Слабо и сильно необратимые функции для равномерного и неравномерного противника. Односторонние функции. Если P=NP, то односторонних функций нет. Функция Mult. Функция SubsetSum.
Лекция 2 (9 сентября).
Преобразование слабо необратимой функции в сильно необратимую. Полиномиально моделируемые и доступные распределения.
Лекция 3 (16 сентября).
Функция Рабина , функция RSA и дискретная экспонента.
Планируемые лекции
Лекция 4 (23 сентября).
Односторонние перестановки - общее определение. Односторонние перестановки с секретом (определение) и улучшенные односторонние перестановки с секретом. Статистически неотличимые и вычислительно неотличимые случайные величины. Свойства вычислительно неотличимых случайных величин
Лекция 5 (7 октября).
Генераторы ПСЧ. Любой генератор ПСЧ является слабо односторонней функцией. Теорема о существовании генератора ПСЧ (без доказательства), если существуют односторонние функции.
Лекция 6 (14 октября).
Определение трудного предиката. Лемма Яо. Использование трудного предиката и инвариантного распределения для построения генератора ПСЧ.
Лекция 7 (28 октября).
Теорема Левина-Голдрайха о коде Адамара. Построение трудного предиката для данной односторонней функции.
Лекция 8 (11 ноября).
Построение генератора ПСЧ из односторонней перестановки. Одноразовые схемы шифрования с закрытым ключом. Построение одноразовой СШЗК на основе генератора ПСЧ.
Лекция 9 (18 ноября).
Одноразовые схемы шифрования с открытым ключом. Построение одноразовой СШOК на основе генератора односторонней перестановки с секретом. Многоразовые схемы шифрования. Семейства ПСФ. Построение семейства ПСФ на основе генератора ПСЧ. Многоразовая СШЗК на основе семейства ПСФ
Лекция 10 (25 ноября).
Многоразовая СШЗК на основе семейства ПСФ. Сильные семейства ПСФ (без доказательства). Устойчивость многоразовой СШЗК относительно атаки с выбором шифруемых сообщений.
Неинтерактивные протоколы привязки к биту и строке. Построение протокола привязки к биту на основе инъективной односторонней функции.
Лекция 11 (2 декабря).
Построение протокола привязки к биту на основе инъективной односторонней функции (доказательство выполнения требований). Построение не интерактивного протокола привязки к строке. Интерактивные алгоритмы. Интерактивные протоколы привязки к биту и строке. Построение интерактивного протокола привязки к биту на основе генератора ПСЧ.
Лекция 12 (9 декабря).
Игра в орлянку по телефону. Протоколы идентификации: определение. Три вида атаки: простая атака, атака с подслушиванием и атака с фальшивым банкоматом. Построение протоколов идентификации с закрытым ключом для всех трех видов атаки.
Лекция 13 (16 декабря).
Построение протокола идентификации с открытым ключом, выдерживающего простую атаку и атаку с подслушиванием.
Семинары
Семинар 1 (8 сентября).
Семинар 2 (15 сентября).
Семинар 3 (22 сентября).
Конспекты лекций
В этой незаконченной книге есть все, что будет на лекциях.
Рекомендуемая литература
0. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. Изд-во МЦНМО.
1. Введение в криптографию. Под общей редакцией В.В.Ященко. --- 3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.
2. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко. Криптография в банковском деле. М.: МИФИ, 1997.
3. O. Goldreich. Foundations of cryptography. Basic tools. Cambridge Univ. Press. 2001. 400 p.
4. O. Goldreich. Foundations of cryptography. Basic applications. Cambridge Univ. Press. 2004.
