У світі криптографії назріває потенційний тектонічний зсув. Дослідник з 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, але через кілька днів у його доведенні було знайдено фатальну помилку, і він відкликав свій висновок. Цей випадок — яскраве нагадування про те, що в квантовій криптографії необхідна багаторазова верифікація результатів. На даний момент незалежного експертного консенсусу щодо роботи Саймона немає, і це головний фактор невизначеності.

Мій аналіз: Ця публікація — це не сигнал до паніки і не привід для негайної міграції, а важливий дзвінок для всієї криптоспільноти. Вона підкреслює, що навіть найнадійніші на сьогодні математичні конструкції можуть бути вразливими перед новими теоретичними проривами. Індустрії необхідно не лише впроваджувати постквантові стандарти, а й активно фінансувати дослідження у сфері квантової стійкості, а також розробляти гібридні схеми, щоб бути готовими до будь-яких сценаріїв розвитку подій. Ми стоїмо на порозі нової ери, де межа між теорією та практикою стає дедалі тоншою.