Потенциальная угроза постквантовой криптографии: алгоритм Саймона

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

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

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

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

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

Напомним, в мае разработчики Quantus подчеркнули зависимость криптоиндустрии от алгоритмов, уязвимых для квантовых атак, и необходимость перехода к постквантовым решениям.