Криптография на решётках 23/24 — различия между версиями
Ustinov (обсуждение | вклад) |
Ustinov (обсуждение | вклад) |
||
(не показаны 4 промежуточные версии этого же участника) | |||
Строка 30: | Строка 30: | ||
Лекция 2 (19.04.2024) Процесс ортогонализации Грама - Шмидта. Минимумы Минковского. Константа Эрмита. [LLL+] | Лекция 2 (19.04.2024) Процесс ортогонализации Грама - Шмидта. Минимумы Минковского. Константа Эрмита. [LLL+] | ||
+ | |||
+ | Лекция 3 (26.04.2024) Оценка констант Эрмита с помощью теоремы Минковского. Приведённые по Лагранжу базисы. Алгоритм Лагранжа. Неравенство Эрмита (два доказательства). | ||
+ | |||
+ | Лекция 4 (10.05.2024) | ||
== Домашние задания == | == Домашние задания == | ||
− | [https://drive.google.com/file/d/1b-7Q5F0_H5zWIVx5tqRUxuEp0t3p_At5/view?usp=sharing ДЗ-1] [https://drive.google.com/file/d/1KyHS7VGSE_dMFTrB8OwxqPzxIJf9TZVv/view?usp=sharing ДЗ-2] | + | [https://drive.google.com/file/d/1b-7Q5F0_H5zWIVx5tqRUxuEp0t3p_At5/view?usp=sharing ДЗ-1] [https://drive.google.com/file/d/1KyHS7VGSE_dMFTrB8OwxqPzxIJf9TZVv/view?usp=sharing ДЗ-2] [https://drive.google.com/file/d/1I6VqWPtBp7s7cGuYbA2y47i_Bl_CrBfp/view?usp=sharing ДЗ-3] |
=== Правила сдачи заданий === | === Правила сдачи заданий === | ||
Строка 46: | Строка 50: | ||
== Полезные материалы == | == Полезные материалы == | ||
− | === | + | ===Основные источники=== |
# [ГН] [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 ] | # [HS] [https://libgen.li/edition.php?id=28163895 Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008 ] | ||
Строка 54: | Строка 58: | ||
===Дополнительные материалы=== | ===Дополнительные материалы=== | ||
− | # | + | # Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы (в 2 томах), 1990. [https://libgen.li/edition.php?id=135785023 том 1], [https://libgen.li/edition.php?id=135785024 том 2]. |
− | + | # Milnor J., Husemoller D. [https://libgen.li/edition.php?id=135780681 Symmetric bilinear forms 1973 ] | |
+ | # Silverman J. H. [https://www.ntwebseminar.org/previous-talks#h.nc99vbqpdgq8 "More Tips on Keeping Secrets in a Post-Quantum World: Lattice-Based Cryptography"] |
Версия 23:02, 28 апреля 2024
Содержание
О курсе
Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 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"