Версия 18:54, 21 апреля 2024

О курсе

Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.

В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.

Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.

В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.

Лектор — Устинов Алексей Владимирович

Полезные ссылки

Чат в telegram для обсуждений:

Google classroom: d3zoqb2

За расписанием курса можно следить по таблице

Укороченный вариант курса читался ранее, см. Криптография на решётках 21/22. Там есть, в частности, конспекты первых лекций.

Ассистент

Пётр Шевченко

Лекции

Лекция 1 (12.04.2024) Решётки и их свойства. Матрица Грама. [ГН] Теорема Минковского о выпуклом теле.

Лекция 2 (19.04.2024) Процесс ортогонализации Грама - Шмидта. Минимумы Минковского. Константа Эрмита. [LLL+]

Домашние задания

ДЗ-1 ДЗ-2

Правила сдачи заданий

В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.

Экзамен

Оценка

Итоговая оценка=0.5*экзамен + 0.5*ДЗ (округляется арифметически).

Полезные материалы

Книги

1. [ГН] Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012
2. [HS] Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008
3. [LLL] Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients. Math. Ann., Vol. 261 (1982), 515-534.
4. [LLL+] Nguyen Phong Q., Vallée Brigitte (ed.) The LLL algorithm. Survey and applications. 2010

Дополнительные материалы

1. Joseph H. Silverman "More Tips on Keeping Secrets in a Post-Quantum World: Lattice-Based Cryptography"