Исследователь компании Amazon Web Services (AWS) Дэниел Саймон опубликовал работу, в которой представил новый квантовый алгоритм. Данный алгоритм потенциально позволяет ускорить решение определенных математических задач, лежащих в основе постквантовой криптографии. Согласно утверждению автора, время работы алгоритма растет пропорционально степени размера задачи, а не экспоненциально. Стоит отметить, что документ не описывает практическую атаку на действующие криптографические стандарты, такие как ML-KEM и ML-DSA.

В исследовании рассматривается математическая задача Dihedral Coset Problem (DCP). Ранее математики, включая Одеда Регева, доказали связь DCP с задачами на многомерных решетках. Саймон утверждает, что его алгоритм позволяет выполнять необходимое преобразование непосредственно на квантовом компьютере, обходя ограничения предыдущих полиномиальных подходов, требовавших идеализированных вычислительных инструментов. Этот результат потенциально распространяется на варианты задач Shortest Vector Problem (SVP) и Learning With Errors (LWE). Данные задачи являются фундаментом для многих постквантовых криптографических систем, включая механизмы ML-KEM и ML-DSA, стандартизированные Национальным институтом стандартов и технологий (NIST) в 2024 году.

Авторы подчеркивают, что текущие результаты не означают взлома стандартов ML-KEM или подделки подписей ML-DSA. Практическая постквантовая криптография использует специфические структурированные варианты задач LWE, и результаты для одного класса задач не могут быть автоматически перенесены на все криптографические системы, основанные на них. Кроме того, в работе отсутствует оценка вычислительных ресурсов, таких как количество логических кубитов и операций коррекции ошибок, необходимых для реализации алгоритма при криптографически значимых размерах. Экспертное сообщество относится к заявлению с осторожностью, учитывая прецеденты, такие как опровергнутая в 2024 году работа Йилея Чэна о полиномиальном квантовом алгоритме для LWE, в которой была обнаружена ошибка в ключевой части доказательства.