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