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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Организационные вопросы)
 
(Организационные вопросы)
 
Строка 33: Строка 33:
 
Время — по понедельникам,  в 14:00.  
 
Время — по понедельникам,  в 14:00.  
  
 +
=== Материалы ===
 +
 +
==== Видео ====
 +
{{/Лекции весеннего семестра 2013}}
 +
 +
==== Книга ====
 
Драфт лекций-пособия:
 
Драфт лекций-пособия:
  
Строка 38: Строка 44:
  
 
Будем рады ответить на любые вопросы — пишите на [mailto:fomin@ispras.ru?subject=%D1%80%D0%B5%D0%B3%D0%B8%D1%81%D1%82%D1%80%D0%B0%D1%86%D0%B8%D1%8F%20%D0%BD%D0%B0%20%D0%BA%D1%83%D1%80%D1%81%20%22%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BA%D0%B8,%20%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B8%20%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F%22 fomin@ispras.ru] координатору курса Станиславу Фомину.
 
Будем рады ответить на любые вопросы — пишите на [mailto:fomin@ispras.ru?subject=%D1%80%D0%B5%D0%B3%D0%B8%D1%81%D1%82%D1%80%D0%B0%D1%86%D0%B8%D1%8F%20%D0%BD%D0%B0%20%D0%BA%D1%83%D1%80%D1%81%20%22%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BA%D0%B8,%20%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B%20%D0%B8%20%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F%22 fomin@ispras.ru] координатору курса Станиславу Фомину.
 
  
 
== Ссылки ==
 
== Ссылки ==
 
* [http://sites.google.com/site/latticecrypto/translate/Survey-of-lattice-base-cryptography Обзор по криптографии на основе задач теории решеток]
 
* [http://sites.google.com/site/latticecrypto/translate/Survey-of-lattice-base-cryptography Обзор по криптографии на основе задач теории решеток]

Текущая версия на 10:20, 24 апреля 2013

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

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

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

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

  • Кратко прослеживаются основные этапы развития криптографии как науки — от древних времен до современных криптосистем с секретным и открытым ключом.
  • Показана связь стойкости криптосистем с вычислительно трудными проблемами алгебры и теории чисел, в частности, проблемой вычисления дискретного логарифма и проблемой факторизации натуральных чисел. Обсуждается связь сложности в худшем случае и сложности в среднем, вводится основной примитив современной криптографии — понятие односторонней функции.
  • Обсуждаются слабости и недостатки в обосновании стойкости современных криптосистем, в частности, в свете результатов П. Шора о полиномиальных квантовых алгоритмах вычисления дискретного логарифма и факторизации чисел.
Основная часть курса посвящена изложению идей современного направления, зародившегося в конце 20-го века, и базирующегося на фундаментальных результатах венгерского математика Айтаи, которое на Западе получило название «Lattice based cryptography».
  • Излагаются сведения из теории колец, полей и решеток, необходимые для описания основных результатов и связанные, в частности,с понятием кольца, конечного поля и расширения полей, приведенного базиса решетки, критерием полноты решетки и леммой Минковского.
  • Излагаются алгоритмические аспекты теории решеток и их применение в криптографии, в частности, сложность решения систем линейных диофантовых уравнений, сложность нахождения кратчайшего ненулевого вектора решетки и вектора решетки, ближайшего к заданному вектору, известные приближенные алгоритмы для этих задач.
  • Формулируются результаты Айтаи (Miklós Ajtai ) о сложности поиска короткого вектора в случайной решетке.
  • Описаны некоторые современные криптосистемы на решетках: NTRU и другие.
  • Показана роль алгебраических методов в доказательстве полиномиальной разрешимости проверки простоты чисел.

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

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

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

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

Материалы

Видео

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

  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-20-lectures.uncut.mkv01:44:02
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-27-lectures.uncut.mkv01:44:02
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-06-lectures.uncut.mkv00:02:16
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv00:02:14
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv01:37:31
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-27-lectures.uncut.mkvVLC↑
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-04-03-lectures.uncut.mkv01:45:09

Книга

Драфт лекций-пособия:

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

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

Ссылки