Світ постквантової безпеки сколихнула свіжа наукова робота, представлена дослідником Amazon Web Services (AWS) Деніелом Саймоном. У новому препринті він описує квантовий алгоритм, який, за його твердженням, здатен розв'язувати ключові математичні задачі, що лежать в основі сучасних постквантових стандартів, з поліноміальною складністю — тобто час його роботи зростає як степінь розміру задачі, а не експоненційно, як вважалося раніше.
Якщо цей результат виявиться правильним, він може кардинально переглянути наші уявлення про стійкість ґратчастої криптографії до квантових обчислень. Однак важливо наголосити: документ не містить практичної атаки на чинні стандарти, такі як ML-KEM (механізм інкапсуляції ключів) або ML-DSA (цифрові підписи). Йдеться про теоретичний прорив, який ще належить перевірити.
Суть алгоритму та його зв'язок із ґратками
Саймон, відомий своїм однойменним алгоритмом 1990-х років, який став попередником знаменитого алгоритму Шора, у новій роботі зосередився на так званій проблемі діедральних суміжних класів (Dihedral Coset Problem, DCP). Спрощено, квантовий комп'ютер отримує набір пов'язаних станів і має виявити приховане значення між ними. Сама по собі DCP не використовується безпосередньо для шифрування, але ще на початку 2000-х математик Одед Регев довів, що ефективне розв'язання DCP дозволило б атакувати певні варіанти задач на багатовимірних ґратках, включно з Shortest Vector Problem (SVP) та Learning With Errors (LWE).
Головне обмеження підходу Регева полягало в необхідності ідеалізованого інструменту для розв'язання іншої складної задачі. Саймон стверджує, що йому вдалося обійти цю перешкоду, виконавши необхідне перетворення безпосередньо на квантовому комп'ютері. Це потенційно відкриває шлях до прискореного розв'язання структурованих варіантів LWE, на яких побудовані стандарти NIST, ухвалені у 2024 році.
Паніка передчасна: що залишилося за кадром
Попри гучні заголовки, робота Саймона не демонструє зламу ML-KEM або підробки підпису ML-DSA. Дослідник не атакував конкретні криптографічні параметри, а його алгоритм не містить оцінки кількості логічних кубітів, квантових вентилів або операцій корекції помилок, необхідних для практичної реалізації. Крім того, LWE — це ціле сімейство задач, і результат для одного класу не переноситься автоматично на всі структуровані варіанти, що використовуються в індустрії.
У науковій спільноті вже були прецеденти, коли гучні заяви про поліноміальні квантові алгоритми для ґраток не проходили перевірку. Наприклад, у 2024 році дослідник Їлей Чень заявив про подібний прорив, але через кілька днів у його доведенні знайшли фатальну помилку, і він відмовився від своїх висновків. Зараз незалежного консенсусу щодо роботи Саймона немає, і це головний індикатор того, що висновки робити зарано.
Мій аналіз: Цей препринт — важливий сигнал для індустрії, але не привід для паніки. Він підкреслює крихкість наших поточних теоретичних моделей безпеки. Навіть якщо алгоритм Саймона виявиться правильним, до практичної загрози — десятиліття. Однак криптоспільнота має прискорити перехід до гібридних схем та диверсифікації постквантових алгоритмів, щоб не ставити всю безпеку на одну математичну основу.