Оценки сложности реализации квантового криптоанализа постквантовых криптосистем, основанных на решётках

В силу развития квантовых вычислений возникает необходимость в разработке и анализе криптосистем, устойчивых к атакам с использованием квантового компьютера  — алгоритмов постквантовой криптографии. Стойкость многих известных постквантовых криптосистем, основанных на теории решёток, базируется на сложности решения проблемы нахождения кратчайшего вектора в решетке (SVP). В настоящей статье разработана и описана модель квантового оракула из алгоритма Гровера для реализации гибридного квантово-классического алгоритма на основе GaussSieve, который может быть использован для атак на криптосистемы, стойкость которых зависит от решения задачи SVP. Получены выражения для верхних оценок числа кубитов и глубины схемы двух реализаций предложенной модели квантового оракула: минимизирующей число кубитов и минимизирующей глубину схемы. Проанализирована сложность реализации предложенной модели квантового оракула для атаки на постквантовые криптосистемы, основанные на решётках и являющиеся финалистами конкурса постквантовой криптографии NIST. Табл. 6, ил. 12, библиогр. 34.