Криптография на решётках 21/22 — различия между версиями
Ustinov (обсуждение | вклад) (→Экзамен) |
Ustinov (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 29: | Строка 29: | ||
== Контрольные мероприятия == | == Контрольные мероприятия == | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Экзамен === | === Экзамен === | ||
| − | 1 . | + | 1 . Решётки и их свойства. |
| + | |||
2. Матрица Грама. | 2. Матрица Грама. | ||
| + | |||
3. Теорема Минковского о выпуклом теле. | 3. Теорема Минковского о выпуклом теле. | ||
| − | 4. Процесс ортогонализации Грама | + | |
| + | 4. Процесс ортогонализации Грама - Шмидта. | ||
| + | |||
5. Минимумы Минковского. Константа Эрмита. | 5. Минимумы Минковского. Константа Эрмита. | ||
| − | 6. Алгоритм Лагранжа построения | + | |
| + | 6. Алгоритм Лагранжа построения приведённого базиса в двумерной решётке. | ||
| + | |||
7. Вычисление константы Эрмита в размерности 2. | 7. Вычисление константы Эрмита в размерности 2. | ||
| + | |||
8. Неравенство Эрмита. Алгоритм Эрмита. | 8. Неравенство Эрмита. Алгоритм Эрмита. | ||
| − | 9. LLL- | + | |
| + | 9. LLL-приведённые базисы и их свойства. | ||
| + | |||
10. LLL-алгоритм. | 10. LLL-алгоритм. | ||
| − | 11. Применение LLL- | + | |
| + | 11. Применение LLL-алгоритма к решению задачи о сумме подмножеств. | ||
Дополнительно требуется уметь доказывать свойства LLL-приведённых базисов (задача 5.23 из файла). | Дополнительно требуется уметь доказывать свойства LLL-приведённых базисов (задача 5.23 из файла). | ||
Текущая версия на 09:51, 14 апреля 2024
Содержание
О курсе
Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.
В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.
Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.
В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.
Лектор — Устинов Алексей Владимирович
Лекции
Проходят по вторникам 16:20 - 17:40 в R503.
План занятий
1. Решётки и их свойства. Матрица Грама.
2. Теорема Минковского о выпуклом теле. Процесс ортогонализации Грама-Шмидта. Укороченные базисы.
3. Минимумы Минковского. Константы Эрмита. Алгоритм Лагранжа построения приведённого базиса в двумерной решётке. Вычисление константы Эрмита в размерности. Неравенство Эрмита.
4. Алгоритмы Эрмита. LLL-приведённые базисы и их свойства. LLL-алгоритм.
5. Криптографические протоколы на решётках
Контрольные мероприятия
Экзамен
1 . Решётки и их свойства.
2. Матрица Грама.
3. Теорема Минковского о выпуклом теле.
4. Процесс ортогонализации Грама - Шмидта.
5. Минимумы Минковского. Константа Эрмита.
6. Алгоритм Лагранжа построения приведённого базиса в двумерной решётке.
7. Вычисление константы Эрмита в размерности 2.
8. Неравенство Эрмита. Алгоритм Эрмита.
9. LLL-приведённые базисы и их свойства.
10. LLL-алгоритм.
11. Применение LLL-алгоритма к решению задачи о сумме подмножеств.
Дополнительно требуется уметь доказывать свойства LLL-приведённых базисов (задача 5.23 из файла).
