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

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

Суть угрозы: от теории к практике

Заявленный алгоритм, по словам автора, решает задачи не экспоненциально, а полиномиально, то есть время его работы растет как степень размера задачи, а не как показательная функция. В сочетании с работами Регева это потенциально распространяется на такие фундаментальные проблемы, как Shortest Vector Problem (SVP) и Learning With Errors (LWE). Именно на структурированных вариантах LWE, таких как Module-LWE, построены стандарты Национального института стандартов и технологий США (NIST), включая механизм инкапсуляции ключей ML-KEM и алгоритм цифровой подписи ML-DSA, стандартизированные в 2024 году.

Однако крайне важно сохранять хладнокровие. Этот препринт не содержит практической атаки на действующие стандарты. Саймон не демонстрирует восстановление ключей ML-KEM или подделку подписей ML-DSA с реальными параметрами безопасности. Более того, LWE — это целое семейство задач, и результат для одного класса не может быть автоматически перенесен на все структурированные варианты, используемые в индустрии. В документе также отсутствует оценка необходимых ресурсов — количества логических кубитов, квантовых вентилей и объема коррекции ошибок, что делает его далеким от практической реализации.

Осторожность прежде всего

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

Мой анализ: Данная публикация — это не сигнал к панике и не повод для немедленной миграции, а важный звонок для всего криптосообщества. Она подчеркивает, что даже самые надежные на сегодняшний день математические конструкции могут быть уязвимы перед новыми теоретическими прорывами. Индустрии необходимо не только внедрять постквантовые стандарты, но и активно финансировать исследования в области квантовой устойчивости, а также разрабатывать гибридные схемы, чтобы быть готовыми к любым сценариям развития событий. Мы стоим на пороге новой эры, где грань между теорией и практикой становится все тоньше.