Курс лекций «Решетки, алгоритмы и современная криптография» — различия между версиями

Версия 08:47, 21 марта 2023

Курс лекций «Решетки, алгоритмы и современная криптография»

лекторы: к. ф.-м. н. А. В. Шокуров, д. ф.-м. н. Н. Н. Кузюрин

Семестровый спецкурс по выбору для студентов 4—6 курсов МФТИ.

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

• Кратко прослеживаются основные этапы развития криптографии как науки — от древних времен до современных криптосистем с секретным и открытым ключом.

• Показана связь стойкости криптосистем с вычислительно трудными проблемами алгебры и теории чисел, в частности, проблемой вычисления дискретного логарифма и проблемой факторизации натуральных чисел. Обсуждается связь сложности в худшем случае и сложности в среднем, вводится основной примитив современной криптографии — понятие односторонней функции.

• Обсуждаются слабости и недостатки в обосновании стойкости современных криптосистем, в частности, в свете результатов П. Шора о полиномиальных квантовых алгоритмах вычисления дискретного логарифма и факторизации чисел.

• Излагаются сведения из теории колец, полей и решеток, необходимые для описания основных результатов и связанные, в частности,с понятием кольца, конечного поля и расширения полей, приведенного базиса решетки, критерием полноты решетки и леммой Минковского.
• Излагаются алгоритмические аспекты теории решеток и их применение в криптографии, в частности, сложность решения систем линейных диофантовых уравнений, сложность нахождения кратчайшего ненулевого вектора решетки и вектора решетки, ближайшего к заданному вектору, известные приближенные алгоритмы для этих задач.
• Формулируются результаты Айтаи (Miklós Ajtai ) о сложности поиска короткого вектора в случайной решетке.

• Описаны некоторые современные криптосистемы на решетках: NTRU и другие.

• Показана роль алгебраических методов в доказательстве полиномиальной разрешимости проверки простоты чисел.

Организационные вопросы

Место чтения курса - ИСП РАН (Москва, м. Таганская, Большая Коммунистическая, д. 25).

Комната 110 или 301.

Время — по понедельникам, в 14:00.

Материалы

Видео

Записанное видео лекций Александра Владимировича Шокурова, за весенний семестр 2013 года.

• Как смотреть многопоточное MKV-видео

• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-20-lectures.uncut.mkv^01:44:02
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-27-lectures.uncut.mkv^01:44:02
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-06-lectures.uncut.mkv^00:02:16
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv^00:02:14
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv^01:37:31
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-27-lectures.uncut.mkv^VLC↑
• http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-03-lectures.uncut.mkv^01:45:09

Слайды

• История криптографии (crypto1)
• Порождение трудных входов для алгоритмических задач на решетках. Результаты Айтаи
• Алгоритмы Гаусса и LLL, видео
• LLL/ACVP-алгоритмы
• Сложность CVP/SVP, видео

• NTRU (crypto11)

• Криптосистема Айтаи‐Дворка (crypto11n)

• Криптосистема Айтаи‐Дворка (crypto12)]

• Порождение трудных входов для алгоритмических задач на решетках. Результаты Айтаи (cryptol3)

• О сложности задач CVP и SVP (crypto7-8)

cryptol9-10.beam.pdf latlct1.beam.pdf latlct2.beam.pdf latlct3.beam.pdf latlct6.beam.pdf lct4.beam.pdf lct5.beam.pdf lctl5n.beam.pdf

Книга

• Свежая версии книги-пособия

• Страхующая старая версия (если испортится свежая):

Будем рады ответить на любые вопросы — пишите на fomin@ispras.ru координатору курса Станиславу Фомину.

Ссылки

• Обзор по криптографии на основе задач теории решеток