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