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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Слайды)
(Книга)
 
(не показано 13 промежуточных версий этого же участника)
Строка 42: Строка 42:
 
==== Слайды ====
 
==== Слайды ====
  
* [https://discopal-lab.0x1.tv/share/public_paths/a3145ed71cce67e4fb6884f90dcbe196044a8118 История криптографии (crypto1)]
+
===== Основные понятия и определения теории решеток =====
* [https://discopal-lab.0x1.tv/share/public_paths/906acca5168a561a3fda36ece7bb8c0f8b59aa29 Порождение трудных входов для алгоритмических задач на решетках. Результаты Айтаи]
+
* [https://discopal-lab.0x1.tv/share/public_paths/c7cf388cc62d8bdd1b36d42b68e750b315737afb Основные понятия и определения теории решеток (latlct1)]
* [https://discopal-lab.0x1.tv/share/public_paths/f2ed3ceccd5b87590fe2647170a17cd268e40c68 Алгоритмы Гаусса и LLL], [https://vimeo.com/800835326 видео]
+
* [https://discopal-lab.0x1.tv/share/public_paths/c1a3cc4599640b13fa940fab41c916650c0493aa LLL/ACVP-алгоритмы]
+
* [https://discopal-lab.0x1.tv/share/public_paths/ad62e332707a7cf571b1d1763cfb69cbdcf81c7a Сложность CVP/SVP], [https://vimeo.com/803588855 видео]
+
  
* [https://discopal-lab.0x1.tv/share/public_paths/7c3f6449ec19cb07df11332124fa1e018cd77833 NTRU (crypto11)]
+
===== Алгоритмы Гаусса и LLL =====
 +
<!--
 +
* [https://discopal-lab.0x1.tv/share/public_paths/f2ed3ceccd5b87590fe2647170a17cd268e40c68 Алгоритмы Гаусса и LLL],
 +
-->
  
* [https://discopal-lab.0x1.tv/share/public_paths/b2da3c3267efcffbbb746d49e6328ec2ee6e0072 Криптосистема Айтаи‐Дворка (crypto11n)]
+
* [https://discopal-lab.0x1.tv/share/public_paths/a1f1e12c8ba4a0de35ae14df5aec85fcd3b837bf Алгоритмы Гаусса (latlct2)]
 +
* [https://discopal-lab.0x1.tv/share/public_paths/912ce4c9ed2bded59ea073a9aff6bfac981fe526 LLL‐алгоритм (latlct3)]
  
* [https://discopal-lab.0x1.tv/share/public_paths/4537d3c86565c0cd539badc4bebbf578da80e1a4 Криптосистема Айтаи‐Дворка (crypto12)]]
+
* [https://vimeo.com/800835326 видео]
  
* [https://discopal-lab.0x1.tv/share/public_paths/906acca5168a561a3fda36ece7bb8c0f8b59aa29 Порождение трудных входов для алгоритмических задач на решетках. Результаты Айтаи (cryptol3)]
+
===== LLL/ACVP-алгоритмы =====
  
* [https://discopal-lab.0x1.tv/share/public_paths/80d3cb697cfca80c5c47503c5099ff8cafb97373 О сложности задач CVP и SVP (crypto7-8)]
+
* [https://discopal-lab.0x1.tv/share/public_paths/65eee2b54e9d73b28b65fb8590066c507cefaf4a Задача CVP (latlct4)]
  
* [https://discopal-lab.0x1.tv/share/public_paths/b36f386612528525ea4171430864e05f651afba8 Порождение трудных входов для алгоритмических задач на решетках. Криптосистема Айтаи‐Дворка (cryptol9-10)]
+
* [https://vimeo.com/803588855 видео]
 +
 
 +
 
 +
===== Айтай =====
 +
* [https://discopal-lab.0x1.tv/share/public_paths/6235cc569f60c27dc5d8c370c6f488a8f5530a03 latlct5]
 +
 
 +
===== NTRU =====
  
* [https://discopal-lab.0x1.tv/share/public_paths/c7cf388cc62d8bdd1b36d42b68e750b315737afb Решетки, алгоритмы и современные проблемы криптографии. Основные понятия и определения теории решеток (latlct1)]
 
* [https://discopal-lab.0x1.tv/share/public_paths/a1f1e12c8ba4a0de35ae14df5aec85fcd3b837bf Решетки, алгоритмы и современные проблемы криптографии. Алгоритмы Гаусса и LLL (latlct2)]
 
* [https://discopal-lab.0x1.tv/share/public_paths/912ce4c9ed2bded59ea073a9aff6bfac981fe526 Решетки, алгоритмы и современные проблемы криптографии. LLL‐алгоритм (latlct3)]
 
 
* [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/7dc76da92a068be83d17fe313726ede000c36a0e Задача CVP (lct4)]
 
* [https://discopal-lab.0x1.tv/share/public_paths/6009a31da47fb893ee5993e40cac5f0d5bdf28f0 Криптосистема Айтаи‐Дворка (lct5)]
 
* [https://discopal-lab.0x1.tv/share/public_paths/3cfdd90b876fbbf8694f4644bbb2e14031edec1d https://discopal-lab.0x1.tv/share/public_paths/3cfdd90b876fbbf8694f4644bbb2e14031edec1d (lctl5n)]
 
  
 
==== Книга ====
 
==== Книга ====
* [https://discopal-lab.0x1.tv/share/public_paths/c4676c42ed36884f2321c8e591df10bef06e90d6 Свежая версии книги-пособия]
+
* [https://discopal-lab.0x1.tv/share/public_paths/daa0d349f9f28831eb97affb2ff02ff0ab5314f3 Свежая версии книги-пособия]
  
 
* Страхующая старая версия (если испортится свежая):
 
* Страхующая старая версия (если испортится свежая):

Текущая версия на 11:43, 21 марта 2023

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

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

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

Курс лекций «Решетки, алгоритмы и современная криптография» 2023-01-08 12-01-31 image0.png

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

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

Книга

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

Решетки, алгоритмы и современная криптография.pdf Решетки, алгоритмы и современная криптография.pdf


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

Ссылки