2007-02-22

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

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

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

семестре 2007 г.

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

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

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

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


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

Время: понедельник, 18:00.

Первая лекция: 26.02.2007


Доска курса: программа, обьявления, контакты (вероятно то, что вы читаете):
http://docs.google.com/Doc?id=dfxc7f9q_19ggg3mp

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



2007-02-06

домашняя бухгалтерия против Альфа-банка.

В начале декабря стали вести домашнюю бухгалтерию. Сначала посмотрел существующие программы, но не удовлетворился, и сделал собственную версию. Технологии: Google Spreadsheets + Excel + CVS.

Условно говоря, в сетевой таблице ведется журнал текущих операций (последний месяц, ввод возможен из любого места, возможно параллельное редактирование), там же, в нем же ведутся остатки на счетах (наличность, банк, долги и т. п.), включая ожидаемые остатки на них, рассчитываемые по операциям. Раз в месяц провожу аудит кошельков и счетов, ввожу необходимую коррекцию (сколько неучтенных денег потерял или нашел) переношу операции из сетевой таблицы в Excel, рассчитываю сводные таблицы и графики, пакую и фиксирую очередную версию в CVS.

Появились первые плюсы — при аудите, поймал Альфа-банк на повторном (через полтора месяца) списании денег за онлайн-покупку (400 евро все-таки...). Без бухгалтерии, с большой вероятностью бы не заметил, или заметил, но поздно. А так, подал претензию, надеюсь разберутся. Хотя всякое может быть, опыта бодания с банком первый. Вообще, конечно, все эти карты, с которых деньги списываются уведомительным порядком — must die однозначно. Да здравствуют e-деньги!