Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Бахарев А.О.
Верхние оценки сложности реализации квантового оракула для задачи нахождения кратчайшего вектора целочисленной решётки
Аннотация:
В силу развития квантовых вычислений возникает необходимость в разработке и анализе криптосистем, устойчивых к атакам с использованием квантового компьютера - алгоритмов постквантовой криптографии. Стойкость многих известных постквантовых криптосистем, основанных на теории решёток, базируется на сложности решения проблемы нахождения кратчайшего вектора в решетке (SVP). Для предложенной ранее модели квантового оракула, используемого в гибридном квантово-классическом алгоритме решения задачи SVP, получены новые уточнённые оценки сложности реализации. Разработана и проанализирована новая модель квантового оракула, использующая классическую память для хранения списка векторов.
Ключевые слова:
задача поиска кратчайшего вектора, квантовые вычисления
