Исследователь Amazon Web Services (AWS) Дэниел Саймон представил новый квантовый алгоритм, который потенциально позволяет значительно быстрее решать некоторые математические задачи, лежащие в основе постквантовой криптографии.
По его утверждению, время работы алгоритма растет не экспоненциально, а как степень размера задачи. Если результат подтвердится, это может изменить представления об устойчивости некоторых задач к квантовым вычислениям. При этом документ не содержит практической атаки на действующие стандарты, включая ML-KEM и ML-DSA.
В 1990-х Саймон разработал одноименный квантовый алгоритм, ставший одним из первых примеров существенного преимущества квантовых вычислений и предшественником алгоритма Шора.
https://forklog.com/cryptorium/chto-takoe-kvantovoe-prevoshodstvo-poleznost-i-preimushhestvo
В новой работе исследователь рассмотрел математическую задачу под названием 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. Саймон не атаковал конкретный криптографический стандарт и не показал способ взлома его реальных параметров. Работа касается математических задач и определенных вариантов их решения.
Кроме того, LWE представляет собой целое семейство задач. В практической постквантовой криптографии используются их специально структурированные варианты, поэтому результат для одного класса LWE нельзя автоматически переносить на любую основанную на нем криптографическую систему.
В препринте также нет оценки количества логических кубитов, квантовых вентилей или операций коррекции ошибок, необходимых для запуска алгоритма при криптографически значимых размерах. На момент публикации независимого экспертного консенсуса по исследованию нет.
В этой области уже были случаи, когда громкие предварительные результаты не выдерживали проверки. В 2024 году исследователь Йилей Чэнь заявил о полиномиальном квантовом алгоритме для LWE и связанных решетчатых задач. Через несколько дней специалисты обнаружили ошибку в ключевой части доказательства, после чего автор отказался от основного вывода.
Напомним, в мае разработчики Quantus указали на зависимость значительной части криптоиндустрии от алгоритмов, уязвимых для потенциальных квантовых атак, и необходимость перехода к постквантовым решениям.
О том, можно ли заработать на квантовых технологиях, как блокчейны готовятся к «квантовой» эре и реально ли взломать квантовый интернет, читайте в новой рубрике «Quantum & After».
