Квантовый алгоритм бросает вызов решётчатой криптографии

TL;DR. Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности.

Points clés

Контекст. Задача Learning With Errors — математическая основа большинства современных решёточных криптосистем, включая ML-KEM (стандарт NIST FIPS 203).
Идея. Алгоритм атакует LWE с определёнными «структурированными» параметрами с подэкспоненциальной квантовой сложностью.
Подход. Метод использует:.
Влияние. Важно различать два сценария:.

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-схемы на другую было операционно возможным.

Последняя проверка 2026-06-15.

Опубликовать заново

Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau

Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности.

Эта статья распространяется по лицензии Creative Commons Attribution 4.0 International. При повторной публикации требуется указание канонической ссылки.

Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau

Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности.

Originally published at https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER