Криптография на решётках 23/24 — различия между версиями
Ustinov (обсуждение | вклад) |
Ustinov (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
== Полезные материалы == | == Полезные материалы == | ||
===Книги=== | ===Книги=== | ||
| − | |||
| − | |||
# [ГН] [http://new.math.msu.su/department/number/dw/lib/exe/fetch.php?media=%D1%82%D1%87%D0%BC%D0%BA.pdf Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012 ] | # [ГН] [http://new.math.msu.su/department/number/dw/lib/exe/fetch.php?media=%D1%82%D1%87%D0%BC%D0%BA.pdf Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012 ] | ||
| + | # [HS] [https://libgen.li/edition.php?id=28163895 Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008 ] | ||
| + | # [LLL] [https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1129_LLL.pdf Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients. | ||
| + | Math. Ann., Vol. 261 (1982), 515-534.] | ||
| + | # [LLL+] [https://libgen.li/edition.php?id=136753335 Nguyen Phong Q., Vallée Brigitte (ed.) The LLL algorithm. Survey and applications. 2010 ] | ||
Версия 09:57, 14 апреля 2024
Содержание
О курсе
Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.
В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.
Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.
В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.
Лектор — Устинов Алексей Владимирович
Полезные ссылки
За расписанием курса можно следить по таблице
Укороченный вариант курса читался ранее, см. Криптография на решётках 21/22. Там есть, в частности, конспекты первых лекций.
Ассистент
Лекции
Лекция 1 (14.04.2024) Решётки и их свойства. Матрица Грама. [ГН] Теорема Минковского о выпуклом теле.
Домашние задания
Правила сдачи заданий
Экзамен
Полезные материалы
Книги
- [ГН] Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012
- [HS] Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008
- [LLL] [https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1129_LLL.pdf Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients.
Math. Ann., Vol. 261 (1982), 515-534.]
