Квантовый алгоритм для нахождения кратчайшего пути в ациклическом ориентированном графе

И. О. Кузнецов, Petr F. Kartsev

Мухамедиева Д.Т., Раупова М.Х., Тагаев Ф.А.

В данной работе рассматривается квантовый алгоритм нахождения минимального решения уравнения Пелля для заданного n-битного числа , не являющегося полным квадратом. Используется метод поиска скрытой подгруппы, позволяющий эффективно определять приближённое значение , где . Проведённые квантовые измерения показали, что наиболее вероятный результат соответствует , что позволяет классическими методами вычислить минимальное решение уравнения Пелля. Алгоритм использует разложение в цепную дробь, определяет период и вычисляет соответствующую фундаментальную пару . Результаты симуляции на квантовом компьютере подтверждают полиномиальную сложность нахождения R, что существенно превосходит известные классические алгоритмы. Предложенный метод имеет важные криптографические последствия, так как он потенциально угрожает безопасности криптосистем на основе уравнения Пелля, таких как схема Бухмана-Вильямса.

А.М. БАШАРОВ, А. И. ТРУБИЛКО

Макаров Артём Олегович

Alexander Olegovich Bakharev

Аннотация.Криптосистемы на основе решёток являются одними из основных постквантовых альтернатив асимметричной криптографии, используемой в настоящее время.Большинство атак на такие криптосистемы можно свести к задаче нахождения кратчайшего вектора в решётке (SVP).Ранее авторами была предложена модель квантового оракула из алгоритма Гровера для реализации гибридного квантово-классического алгоритма, основанного на алгоритме GaussSieve и решающего SVP.В настоящей работе предложена и проанализирована новая модель квантового оракула.Предложены и оценены две реализации новой модели квантового оракула.Проанализирована сложность реализации новой модели квантового оракула для атаки на постквантовые криптосистемы, основанные на решётках и являющиеся финалистами конкурса постквантовой криптографии NIST.Приведено сравнение полученных результатов для новой и уже существующей моделей квантового оракула.Табл.4, ил. 10, библиогр.48.Ключевые слова: квантовый поиск, криптография с открытым ключом, криптография на решётках, постквантовая криптография, алгоритм Гровера, квантовые вычисления. ВведениеРазвитие квантовых вычислений ведёт к необходимости в разработке и анализе криптосистем, устойчивых к атакам с использованием квантовых компьютеров алгоритмов постквантовой криптографии [1-3].Программа на квантовом компьютере может быть представлена квантовой

Алексей Юрьевич Китаев, Aleksei Yur'evich Kitaev