Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Решётки в криптографии
Криптографические протоколы


Что: Лекция
Когда: Среда, 18 августа 2010, 02:00–03:30
Где: ПОМИ РАН
Слайды: cryptoprotocols2014_lecture_180810.pdf

Описание

Основы теории решёток: базис, определитель, задача поиска кратчайшего вектора (SVP). Ортогонализация Грама–Шмидта. LLL–редуцированные базисы и оценка на размер rратчайшего вектора. Алгоритм LLL. Его применения в криптоанализе: решение subset sum низкой плотности, поиск корней многочленов и атака на RSA с маленькой экспонентой. Криптографические примитивы, основанные на решётках: конструкция семейства хеш–функций Ajtai и идея доказательства стойкости, конструкция криптосистемы Ajtai–Dwork.