TL;DR. Новая работа Yilei Chen предлагает квантовый алгоритм для решения задачи Learning With Errors (LWE) — фундамента современной решётчатой криптографии. Это вызывает обоснованную тревогу в сообществе постквантовой криптографии.
Ключевые выводы
- Идея. Алгоритм Chen атакует LWE с определёнными параметрами с подэкспоненциальной квантовой сложностью.
- Подход. Использует квантовые осцилляторные состояния для решения SVP-подобных задач.
- Влияние. Если результат подтвердится, потребуется пересмотр параметров ML-KEM и других PQC-стандартов.
Контекст #
Чем важна LWE #
Задача Learning With Errors — математическая основа большинства современных решёточных криптосистем, включая ML-KEM (стандарт NIST FIPS 203). Если LWE окажется уязвима к эффективным квантовым атакам, весь стек постквантовой криптографии нуждается в пересмотре.
Идея #
Что предлагает работа Chen #
Алгоритм атакует LWE с определёнными «структурированными» параметрами с подэкспоненциальной квантовой сложностью. Это значительно лучше, чем существующие квантовые атаки (которые в основном повторяют классические).
Подход #
Технические детали #
Метод использует:
- Квантовые осцилляторные состояния
- Преобразование пространства задачи через специально подобранные квантовые операции
- Сведение к структурированной SVP (Shortest Vector Problem)
Влияние #
Что это значит #
Важно различать два сценария:
- Алгоритм работает только на специфических параметрах — стандартные параметры ML-KEM могут оказаться безопасными
- Алгоритм обобщается — потребуется пересмотр всего PQC-стандартизации
Сообщество криптографов проводит независимую проверку. На момент публикации статьи окончательной ясности нет.
Заключение #
Этот эпизод подчёркивает важный принцип: постквантовая криптография — молодая область, и стойкость её алгоритмов основана на отсутствии известных атак, а не на доказанной невозможности атак. Поэтому crypto-agility — способность быстро менять криптографические алгоритмы — критически важна. Банки должны строить системы так, чтобы переключение с одной PQC-схемы на другую было операционно возможным.
Последняя проверка .