Криптография на решётках 23/24
Содержание
О курсе
В 2016 г. Национальный институт стандартов и технологий США (NIST) объявил о программе и конкурсе по обновлению своих стандартов для того, чтобы включить в них постквантовую криптографию, т. е. такие криптосистемы, которые оставались бы стойкими даже после появления квантовых компьютеров, см NIST Post-Quantum Cryptography Standardization. После трёх туров отбора в финал вышло 7 криптосистем, из которых 5 основаны на решётках.
Курс посвящён именно этому новому направлению в криптографии – криптографии на решётках. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.
В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.
Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.
В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.
Лектор — Устинов Алексей Владимирович
Полезные ссылки
Чат в telegram для обсуждений:
За расписанием курса можно следить по таблице
Укороченный вариант курса читался ранее, см. Криптография на решётках 21/22. Там есть, в частности, конспекты первых лекций.
Ассистент
Лекции
Лекция 1 (12.04.2024) Решётки и их свойства. Матрица Грама. [ГН] Теорема Минковского о выпуклом теле.
Лекция 2 (19.04.2024) Процесс ортогонализации Грама - Шмидта. Минимумы Минковского. Константа Эрмита. [LLL+]
Лекция 3 (26.04.2024) Оценка констант Эрмита с помощью теоремы Минковского. Приведённые по Лагранжу базисы. Алгоритм Лагранжа. Неравенство Эрмита (два доказательства).
Лекция 4 (10.05.2024)
Домашние задания
Правила сдачи заданий
В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.
Экзамен
Оценка
Итоговая оценка=0.5*экзамен + 0.5*ДЗ (округляется арифметически).
Полезные материалы
Основные источники
- [ГН] Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012
- [HS] Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008
- [LLL] Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients. Math. Ann., Vol. 261 (1982), 515-534.
- [LLL+] Nguyen Phong Q., Vallée Brigitte (ed.) The LLL algorithm. Survey and applications. 2010
Дополнительные материалы
- Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы (в 2 томах), 1990. том 1, том 2.
- Milnor J., Husemoller D. Symmetric bilinear forms 1973
- Silverman J. H. "More Tips on Keeping Secrets in a Post-Quantum World: Lattice-Based Cryptography"