Криптография на решётках 23/24 — различия между версиями
Ustinov (обсуждение | вклад) |
Ustinov (обсуждение | вклад) |
||
Строка 17: | Строка 17: | ||
За расписанием курса можно следить по [https://docs.google.com/spreadsheets/d/1yFtl68nItGlSd6bRWkCEgoSmlfepxvBFxNg0D4g_MIs/edit#gid=0 таблице] | За расписанием курса можно следить по [https://docs.google.com/spreadsheets/d/1yFtl68nItGlSd6bRWkCEgoSmlfepxvBFxNg0D4g_MIs/edit#gid=0 таблице] | ||
− | Укороченный вариант курса читался ранее, см.[http://wiki.cs.hse.ru/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%80%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0%D1%85_21/22 Криптография на решётках 21/22.] Там есть, в частности, конспекты первых лекций. | + | Укороченный вариант курса читался ранее, см. [http://wiki.cs.hse.ru/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%80%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0%D1%85_21/22 Криптография на решётках 21/22.] Там есть, в частности, конспекты первых лекций. |
=== Ассистент === | === Ассистент === |
Версия 09:52, 14 апреля 2024
Содержание
О курсе
Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.
В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.
Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.
В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.
Лектор — Устинов Алексей Владимирович
Полезные ссылки
За расписанием курса можно следить по таблице
Укороченный вариант курса читался ранее, см. Криптография на решётках 21/22. Там есть, в частности, конспекты первых лекций.
Ассистент
Лекции
Лекция 1 (14.04.2024) Решётки и их свойства. Матрица Грама. [ГН] Теорема Минковского о выпуклом теле.