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