Исследователь AWS нашел потенциальную уязвимость постквантовой криптографии

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

При этом документ не содержит практической атаки на действующие стандарты, включая ML-KEM и ML-DSA. В 1990-х Саймон разработал одноименный квантовый алгоритм, ставший одним из первых примеров существенного преимущества квантовых вычислений и предшественником алгоритма Шора. В новой работе исследователь рассмотрел математическую задачу под названием Dihedral Coset Problem (DCP).

Динамика рынка

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

В начале 2000-х Одед Регев показал, что эффективный алгоритм для DCP можно использовать для решения определенных вариантов задач на многомерных решетках. Однако существовавший полиномиальный подход требовал идеализированный инструмент для решения другой сложной вычислительной задачи. Саймон утверждает, что смог обойти это ограничение.

Его алгоритм должен выполнять необходимое преобразование непосредственно на квантовом компьютере. Результат затрагивает основу постквантовой криптографии В сочетании с предыдущими математическими работами алгоритм Саймона потенциально распространяется на определенные варианты Shortest Vector Problem (SVP) и Learning With Errors (LWE). SVP можно упрощенно представить как поиск достаточно короткого пути между точками в очень сложной многомерной структуре.

Влияние на рынки

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

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

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

Эта перемена продолжает формировать ландшафт цифровых активов.