Версия 21:25, 30 марта 2025

О курсе

В 2016 г. Национальный институт стандартов и технологий США (NIST) объявил о программе и конкурсе по обновлению своих стандартов для того, чтобы включить в них постквантовую криптографию, т. е. такие криптосистемы, которые оставались бы стойкими даже после появления квантовых компьютеров, см NIST Post-Quantum Cryptography Standardization. После трёх туров отбора в финал вышло 7 криптосистем, из которых 5 основаны на решётках.

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

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

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

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

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

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

Группа в ТГ

Google classroom: cdopselo

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

Ассистент

Данила Солунов

Лекции (план)

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

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

Лекция 3 (18.04.2025) Оценка констант Эрмита с помощью теоремы Минковского. Приведённые по Лагранжу базисы. Алгоритм Лагранжа. Неравенство Эрмита (два доказательства). [LLL+]

Лекция 4 (25.04.2025) Алгоритм Эрмита (два варианта). Свойства базиса, приведённого по Эрмиту. LLL-приведённые базисы. Три интерпретации условия Ловаса. LLL-алгоритм. Оценка числа шагов LLL-алгоритма. [LLL+]

Лекция 5 (02.05.2025) Задача о подмножестве с данной суммой. Криптосистема Меркла — Хеллмана. Линейные коды. Порождающая и проверочная матрицы. Минимальное расстояние кода. Код Хемминга. Синдром кодового слова. Задача декодирования. Задача декодирования синдрома.

Лекция 6 (16.05.2025) Двойственные коды. Эквивалентность задач декодирования слова и декодирования синдрома. Криптосистемы Мак-Элиса и Нидеррайтера. Алгоритмически сложные задачи на решётках.

Лекция 7 (23.05.2025) Криптосистема, основанная на сравнениях. Прототип системы полного гомоморфного шифрования. Алгоритм Бабая. Криптосистема GGH (Goldreich — Goldwasser — Halevi).

Лекция 8 (30.05.2025) Дискретное преобразование Фурье. Криптосистема PASS.

Лекция 9? (06.06.2025)

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

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

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

Экзамен

??.06.2025 На экзамен можно принести собственноручно написанную шпаргалку - лист А4.

Оценка

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

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

Основные источники

1. [ГН] Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012
2. [HS] Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008
3. [LLL+] Nguyen Phong Q., Vallée Brigitte (ed.) The LLL algorithm. Survey and applications. 2010

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

1. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы (в 2 томах), 1990. том 1, том 2.
2. Берлекэмп Э. Алгебраическая теория кодирования, 1971.
3. Блейхут Р. Теория и практика кодов, контролирующих ошибки, 1986.
4. Bremner M. R. Lattice basis reduction. An introduction to the LLL algorithm and its applications. 2012
5. [LLL] Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients. Math. Ann., Vol. 261 (1982), 515-534.
6. Micciancio D., Goldwasser Sh. Complexity of Lattice Problems: a cryptographic perspective 2002
7. Milnor J., Husemoller D. Symmetric bilinear forms 1973
8. Silverman J. H. "More Tips on Keeping Secrets in a Post-Quantum World: Lattice-Based Cryptography" (Обзорная лекция + криптосистемы GGH и PASS)
9. Tanja Lange: Post-quantum cryptography (серия лекций на YouTube)