Криптография на решётках 21/22

О курсе

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