Курс лекций «Решетки, алгоритмы и современная криптография» — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (→Слайды) |
StasFomin (обсуждение | вклад) (→Слайды) |
||
| Строка 42: | Строка 42: | ||
==== Слайды ==== | ==== Слайды ==== | ||
| − | ===== | + | ===== Основные понятия и определения теории решеток ===== |
| − | * [https://discopal-lab.0x1.tv/share/public_paths/c7cf388cc62d8bdd1b36d42b68e750b315737afb | + | * [https://discopal-lab.0x1.tv/share/public_paths/c7cf388cc62d8bdd1b36d42b68e750b315737afb Основные понятия и определения теории решеток (latlct1)] |
===== Алгоритмы Гаусса и LLL ===== | ===== Алгоритмы Гаусса и LLL ===== | ||
| + | <!-- | ||
* [https://discopal-lab.0x1.tv/share/public_paths/f2ed3ceccd5b87590fe2647170a17cd268e40c68 Алгоритмы Гаусса и LLL], | * [https://discopal-lab.0x1.tv/share/public_paths/f2ed3ceccd5b87590fe2647170a17cd268e40c68 Алгоритмы Гаусса и LLL], | ||
| + | --> | ||
| − | * [https://discopal-lab.0x1.tv/share/public_paths/a1f1e12c8ba4a0de35ae14df5aec85fcd3b837bf | + | * [https://discopal-lab.0x1.tv/share/public_paths/a1f1e12c8ba4a0de35ae14df5aec85fcd3b837bf Алгоритмы Гаусс (latlct2)] |
| − | * [https://discopal-lab.0x1.tv/share/public_paths/912ce4c9ed2bded59ea073a9aff6bfac981fe526 | + | * [https://discopal-lab.0x1.tv/share/public_paths/912ce4c9ed2bded59ea073a9aff6bfac981fe526 LLL‐алгоритм (latlct3)] |
| + | * [https://vimeo.com/800835326 видео] | ||
| + | |||
| + | ====== LLL/ACVP-алгоритмы ===== | ||
| + | |||
| + | * [https://discopal-lab.0x1.tv/share/public_paths/7dc76da92a068be83d17fe313726ede000c36a0e Задача CVP (lct4)] | ||
| − | |||
* [https://discopal-lab.0x1.tv/share/public_paths/c1a3cc4599640b13fa940fab41c916650c0493aa LLL/ACVP-алгоритмы] | * [https://discopal-lab.0x1.tv/share/public_paths/c1a3cc4599640b13fa940fab41c916650c0493aa LLL/ACVP-алгоритмы] | ||
| − | * [https://discopal-lab.0x1.tv/share/public_paths/ad62e332707a7cf571b1d1763cfb69cbdcf81c7a Сложность CVP/SVP], | + | * [https://discopal-lab.0x1.tv/share/public_paths/ad62e332707a7cf571b1d1763cfb69cbdcf81c7a Сложность CVP/SVP], |
| − | * [https:// | + | |
| + | * [https://vimeo.com/803588855 видео] | ||
* [https://discopal-lab.0x1.tv/share/public_paths/80d3cb697cfca80c5c47503c5099ff8cafb97373 О сложности задач CVP и SVP (crypto7-8)] | * [https://discopal-lab.0x1.tv/share/public_paths/80d3cb697cfca80c5c47503c5099ff8cafb97373 О сложности задач CVP и SVP (crypto7-8)] | ||
| + | ====== NTRU ===== | ||
* [https://discopal-lab.0x1.tv/share/public_paths/65498fc7919f64846804371b84241f47aebaa141 NTRU (latlct6)] | * [https://discopal-lab.0x1.tv/share/public_paths/65498fc7919f64846804371b84241f47aebaa141 NTRU (latlct6)] | ||
| − | * [https://discopal-lab.0x1.tv/share/public_paths/ | + | * [https://discopal-lab.0x1.tv/share/public_paths/7c3f6449ec19cb07df11332124fa1e018cd77833 NTRU (crypto11)] |
| − | + | ||
== Ненужно === | == Ненужно === | ||
Версия 11:20, 21 марта 2023
Курс лекций «Решетки, алгоритмы и современная криптография»
лекторы: к. ф.-м. н. А. В. Шокуров, д. ф.-м. н. Н. Н. Кузюрин
Семестровый спецкурс по выбору для студентов 4—6 курсов МФТИ.
Цель курса — показать как такое классическое понятие алгебры как решетка применяется в современной криптографии, определяя, по-существу, самое перспективное направление ее развития. В курсе
- Кратко прослеживаются основные этапы развития криптографии как науки — от древних времен до современных криптосистем с секретным и открытым ключом.
- Показана связь стойкости криптосистем с вычислительно трудными проблемами алгебры и теории чисел, в частности, проблемой вычисления дискретного логарифма и проблемой факторизации натуральных чисел. Обсуждается связь сложности в худшем случае и сложности в среднем, вводится основной примитив современной криптографии — понятие односторонней функции.
- Обсуждаются слабости и недостатки в обосновании стойкости современных криптосистем, в частности, в свете результатов П. Шора о полиномиальных квантовых алгоритмах вычисления дискретного логарифма и факторизации чисел.
Основная часть курса посвящена изложению идей современного направления, зародившегося в конце 20-го века, и базирующегося на фундаментальных результатах венгерского математика Айтаи, которое на Западе получило название «Lattice based cryptography».
- Излагаются сведения из теории колец, полей и решеток, необходимые для описания основных результатов и связанные, в частности,с понятием кольца, конечного поля и расширения полей, приведенного базиса решетки, критерием полноты решетки и леммой Минковского.
- Излагаются алгоритмические аспекты теории решеток и их применение в криптографии, в частности, сложность решения систем линейных диофантовых уравнений, сложность нахождения кратчайшего ненулевого вектора решетки и вектора решетки, ближайшего к заданному вектору, известные приближенные алгоритмы для этих задач.
- Формулируются результаты Айтаи (Miklós Ajtai ) о сложности поиска короткого вектора в случайной решетке.
- Описаны некоторые современные криптосистемы на решетках: NTRU и другие.
- Показана роль алгебраических методов в доказательстве полиномиальной разрешимости проверки простоты чисел.
Содержание
Организационные вопросы
Место чтения курса - ИСП РАН (Москва, м. Таганская, Большая Коммунистическая, д. 25).
Комната 110 или 301.
Время — по понедельникам, в 14:00.
Материалы
Видео
Записанное видео лекций Александра Владимировича Шокурова, за весенний семестр 2013 года.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-20-lectures.uncut.mkv01:44:02
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-27-lectures.uncut.mkv01:44:02
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-06-lectures.uncut.mkv00:02:16
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv00:02:14
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv01:37:31
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-27-lectures.uncut.mkvVLC↑
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-03-lectures.uncut.mkv01:45:09
Слайды
Основные понятия и определения теории решеток
Алгоритмы Гаусса и LLL
= LLL/ACVP-алгоритмы
= NTRU
Ненужно =
- История криптографии (crypto1)
- Порождение трудных входов для алгоритмических задач на решетках. Результаты Айтаи (cryptol3)
- Криптосистема Айтаи‐Дворка (lct5)
- Криптосистема Айтаи‐Дворка (lctl5n)
- Криптосистема Айтаи‐Дворка (crypto12)]
- Порождение трудных входов для алгоритмических задач на решетках. Криптосистема Айтаи‐Дворка (cryptol9-10)
Книга
- Страхующая старая версия (если испортится свежая):
Будем рады ответить на любые вопросы — пишите на fomin@ispras.ru координатору курса Станиславу Фомину.