Исследователь AWS представил квантовый алгоритм для DCP

Исследователь Amazon Web Services Дэниел Саймон в препринте представил квантовый алгоритм для задачи Dihedral Coset Problem (DCP). В документе содержится утверждение, что время решения при его методе растёт не экспоненциально, а как степень размера задачи. Препринт не демонстрирует практической атаки на стандарты ML‑KEM или ML‑DSA.

DCP — это математическая задача, в которой квантовый компьютер получает набор связанных квантовых состояний и должен выявить скрытое значение, связывающее эти состояния. Сама по себе DCP не применяется напрямую для защиты сетей или кошельков, но в теории её решения связаны с некоторыми вариантами задач на многомерных решётках.

В начале 2000-х Одед Регев показал связь между DCP и вариантами Shortest Vector Problem (SVP). В своей работе Саймон пишет, что удалось обойти ранее использовавшийся идеализированный инструмент и выполнить требуемое преобразование непосредственно на квантовом компьютере.

Сочетание результатов Саймона и предыдущих математических работ потенциально относится к некоторым версиям SVP и к задачам Learning With Errors (LWE). SVP — это поиск достаточно короткого вектора в высокоразмерной решётке. LWE — система уравнений с добавленным шумом, используемая для сокрытия секретов в криптографии.

В 2024 году Национальный институт стандартов и технологий (NIST) стандартизировал механизм ML‑KEM, безопасность которого связана с Module Learning With Errors — структурированным вариантом LWE. Стандарт подписи ML‑DSA также опирается на задачи решётчатой теории. В препринте Саймона не показано, как перевести предложенный алгоритм на реальные параметры этих стандартов.

В документе отсутствуют оценки ресурсов, необходимых для практической реализации: нет расчётов числа логических кубитов, числа квантовых вентилей и объёма операций по коррекции ошибок для размеров, релевантных криптографии. На момент публикации независимого экспертного консенсуса по выводам не было.

В 2024 году исследователь Йилей Чэнь заявил о полиномиальном квантовом алгоритме для LWE; вскоре в доказательстве обнаружили ошибку, и основной вывод был отозван. Этот случай указывается в тексте как пример необходимости проверки предварительных результатов.

В статье также содержится историческая ремарка: в 1990‑х годах Дэниел Саймон разработал алгоритм, получивший его имя, который стал одним из ранних примеров заметного квантового преимущества. Препринт текущей работы остаётся теоретическим: независимая проверка и оценка требований к ресурсам названы необходимыми для определения применимости результатов к действующим криптографическим параметрам.