RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2023, том 30, выпуск 3, страницы 5–42 (Mi da1325)

Эта публикация цитируется в 1 статье

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

А. О. Бахарев

Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

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

Ключевые слова: квантовый поиск, криптография с открытым ключом, криптография на решётках, постквантовая криптография, алгоритм Гровера, квантовые вычисления.

УДК: 519.7

Статья поступила: 18.11.2022
Переработанный вариант: 21.03.2023
Принята к публикации: 03.04.2023

DOI: 10.33048/daio.2023.30.756



© МИАН, 2025