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

М.: Институт системного программирования РАН, 2011. – 130 с.Содержание:Основные понятия криптографии и теории сложности
Дискретный логарифм. Обмен ключами.
Дискретный логарифм и криптосистема Эль Гамаля.
Односторонние функции.
Система RSA и ее анализ.
Основные понятия теории сложности.
Кольца, поля, решетки
Кольца.
Кольца. Основные определения.
Идеалы и гомоморфизмы колец.
Коммутативные кольца.
Факториальные кольца.
Кольца многочленов.
Однозначность разложения на простые множители в кольце многочленов.
Кратные корни.
Поля.
Расширения полей.
Алгебраическое замыкание.
Конечные поля.
Корни из единицы.
Решетки.
Введение в решетки.
Критерий полноты решетки. Теорема Минковского
Применение алгебры. Полиномиальный алгоритм проверки простоты чисел.
Полиномиальная проверка простоты.
Алгоритмические аспекты теории решеток
Кратчайший ненулевой вектор решетки.
Некоторые задачи на решетках.
Алгоритм Гаусса.
LLL-алгоритм.
Некоторые криптосистемы на решетках
NTRU.
Описание NTRU-шифрования.
Выбор параметров.
Дешифрование.
Атаки.
Обзор современных результатов по алгоритмическим аспектам теории решеток