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-схемы на другую было операционно возможным.
Последняя проверка .
Перепубликовать эту статью
Скопировать формат для Medium
# Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau > Originally published at [https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/](https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/) Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности. Read the full article on sebastienrousseau.com: https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/
Скопировать формат для Mastodon
Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности. https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/
Копировать в формате для LinkedIn
Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности. Вот ключевые стратегические выводы: - Контекст. Задача Learning With Errors — математическая основа большинства современных решёточных криптосистем, включая ML-KEM (стандарт NIST FIPS 203). - Идея. Алгоритм атакует LWE с определёнными «структурированными» параметрами с подэкспоненциальной квантовой сложностью. - Подход. Метод использует:. - Влияние. Важно различать два сценария:. Каков подход вашей организации к вызовам, описанным в этой статье? → https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/ #КвантовыйАлгоритм #Lwe #LearningWithErrors #РешётчатаяКриптография #MlKem Sebastien Rousseau | CC-BY-4.0
Цитировать эту статью
Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau
Новый квантовый алгоритм решает ключевую криптографическую задачу, призывая ускорить исследования в области квантово-устойчивой безопасности.
BibTeX
@online{rousseau2024квантовый,
author = {Rousseau, Sebastien},
title = {{Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau}},
year = {2024},
url = {https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/},
urldate = {2024}
}RIS
TY - GEN AU - Rousseau, Sebastien TI - Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau PY - 2024 UR - https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/ ER -
Vancouver
Rousseau S. Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau. sebastienrousseau.com. 2024 Apr 15. Available from: https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/
Chicago
Rousseau, Sebastien. "Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau." sebastienrousseau.com. April 15, 2024. https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/.
APA
Rousseau, S. (2024, April 15). Квантовый алгоритм бросает вызов решётчатой криптографии — Sebastien Rousseau. sebastienrousseau.com. https://sebastienrousseau.com/ru/2024-04-15-kvantovyi-algoritm-brosaet-vyzov-reshetchatoi-kriptografii/
Опубликовать заново
Квантовый алгоритм бросает вызов решётчатой криптографии — 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.