Мир постквантовой безопасности всколыхнула свежая научная работа, представленная исследователем Amazon Web Services (AWS) Дэниелом Саймоном. В новом препринте он описывает квантовый алгоритм, который, по его утверждению, способен решать ключевые математические задачи, лежащие в основе современных постквантовых стандартов, с полиномиальной сложностью — то есть время его работы растет как степень размера задачи, а не экспоненциально, как считалось ранее.
Если этот результат окажется верным, он может кардинально пересмотреть наши представления об устойчивости решетчатой криптографии к квантовым вычислениям. Однако важно подчеркнуть: документ не содержит практической атаки на действующие стандарты, такие как ML-KEM (механизм инкапсуляции ключей) или ML-DSA (цифровые подписи). Речь идет о теоретическом прорыве, который еще предстоит проверить.
Суть алгоритма и его связь с решетками
Саймон, известный своим одноименным алгоритмом 1990-х годов, который стал предшественником знаменитого алгоритма Шора, в новой работе сосредоточился на так называемой проблеме диэдральных смежных классов (Dihedral Coset Problem, DCP). Упрощенно, квантовый компьютер получает набор связанных состояний и должен выявить скрытое значение между ними. Сама по себе DCP не используется напрямую для шифрования, но еще в начале 2000-х математик Одед Регев доказал, что эффективное решение DCP позволило бы атаковать определенные варианты задач на многомерных решетках, включая Shortest Vector Problem (SVP) и Learning With Errors (LWE).
Главное ограничение подхода Регева заключалось в необходимости идеализированного инструмента для решения другой сложной задачи. Саймон утверждает, что ему удалось обойти это препятствие, выполнив необходимое преобразование непосредственно на квантовом компьютере. Это потенциально открывает путь к ускоренному решению структурированных вариантов LWE, на которых построены стандарты NIST, принятые в 2024 году.
Паника преждевременна: что осталось за кадром
Несмотря на громкие заголовки, работа Саймона не демонстрирует взлом ML-KEM или подделку подписи ML-DSA. Исследователь не атаковал конкретные криптографические параметры, а его алгоритм не содержит оценки количества логических кубитов, квантовых вентилей или операций коррекции ошибок, необходимых для практической реализации. Кроме того, LWE — это целое семейство задач, и результат для одного класса не переносится автоматически на все структурированные варианты, используемые в индустрии.
В научном сообществе уже были прецеденты, когда громкие заявления о полиномиальных квантовых алгоритмах для решеток не проходили проверку. Например, в 2024 году исследователь Йилей Чэнь заявил о подобном прорыве, но через несколько дней в его доказательстве нашли фатальную ошибку, и он отказался от своих выводов. Сейчас независимого консенсуса по работе Саймона нет, и это главный индикатор того, что выводы делать рано.
Мой анализ: Этот препринт — важный сигнал для индустрии, но не повод для паники. Он подчеркивает хрупкость наших текущих теоретических моделей безопасности. Даже если алгоритм Саймона окажется верен, до практической угрозы — десятилетия. Однако криптосообщество должно ускорить переход к гибридным схемам и диверсификации постквантовых алгоритмов, чтобы не ставить всю безопасность на одну математическую основу.