Алгоритм Саймона для DCP: що він стверджує і чому ML-KEM та ML-DSA поки не під загрозою

• Поліноміальний розв’язувач DCP. Автор заявляє, що його алгоритм розв’язує DCP за поліноміальний час на квантовому комп’ютері. Підхід спирається на попередні результати, зокрема на роботу Одеда Регева, яка пов’язала діедральну задачу підгруп із DCP .
• Закриття багаторічної теоретичної прогалини. Якщо доведення виявиться правильним, результат може заповнити прогалину, що залишалася після встановлення зв’язку між DCP і ґратковими задачами приблизно у 2002–2004 роках .
• Нова технічна ідея. Замість ключового оракула, використаного в попередніх підходах, Саймон пропонує техніку «блоків і запитів» для вилучення інформації про приховану підгрупу .
• Заявлені наслідки для ґраток. У препринті стверджується, що новий алгоритм можна поєднати зі зведеннями Регева та їхніми подальшими вдосконаленнями, щоб отримати поліноміальні квантові алгоритми для низки ґраткових задач. Серед прикладів названо пошук наближеного найкоротшого вектора (SVP) і задачу навчання з помилками (LWE) .

Окремо автор заявляє, що алгоритм може працювати за частки несправних зразків до рівня 1/O(log n). На думку авторів препринту, це дає змогу ефективно поєднати його зі зведеннями до ґраткових задач .

Чи підтверджено результат

Станом на 7–8 серпня 2026 року відповідь — ні. Робота з’явилася в архіві IACR ePrint як попередній рукопис: за повідомленнями, її отримали 3 серпня, а схвалили до розміщення 6 серпня . Це не означає, що результат неправильний, але він ще не пройшов звичайну процедуру незалежної наукової перевірки.

Ранні реакції криптографічної спільноти були обережними й переважно скептичними:

• Рецензування ще не відбулося. Препринт не опублікований у рецензованому журналі чи матеріалах конференції .
• Ключові доведення подані стисло. Експерти звернули увагу, що кілька критично важливих частин аргументації мають форму ескізів, а фінальний висновок щодо SVP і LWE частково спирається на неопубліковані особисті повідомлення .
• Незалежного підтвердження немає. У перші дні після появи препринту не було опубліковано ні незалежного підтвердження, ні спростування .
• Спільнота закликає не робити передчасних висновків. Загальний підхід можна описати як «спочатку факти, потім реакції» .

Тому нинішній статус роботи — це важлива, але неперевірена теоретична заява, а не встановлений криптоаналітичний результат.

Що це означає для ML-KEM і ML-DSA

Для організацій, які впроваджують або оцінюють стандарти NIST, практичний висновок наразі простий: підстав змінювати плани через цей препринт немає .

Практичної атаки не продемонстровано

У роботі немає реалізованої атаки на ML-KEM — механізм інкапсуляції ключів за стандартом FIPS 203 — або на ML-DSA, алгоритм цифрового підпису за FIPS 204 . Жоден набір параметрів NIST не був атакований .

Зв’язок із конкретними стандартами не є автоматичним

DCP пов’язана з ґратковими задачами через теоретичні зведення. Але цього недостатньо, щоб одразу отримати атаку на Module-LWE чи Module-SIS — конкретні припущення про складність, на яких базуються ML-KEM і ML-DSA .

Інакше кажучи, твердження «певну ґраткову задачу можна розв’язати швидше» не тотожне твердженню «стандартний алгоритм ML-KEM або ML-DSA зламано». Для такого висновку потрібно довести, що ланцюжок зведень застосовується до відповідних структурованих варіантів задач і дає практично придатну атаку.

Потенційна проблема — структурна, а не негайна

Якщо результат Саймона підтвердять, він може посилити теоретичні аргументи на користь того, що квантові комп’ютери здатні ефективно розв’язувати окремі ґраткові задачі. Проте поняття «ґраткові задачі» охоплює значно ширший клас проблем, ніж конкретні структуровані припущення, використані у стандартах NIST .

Контекст попередніх результатів

У 2025 році дослідники вже представили квазіполіноміальний квантовий алгоритм для обмеженого варіанта DCP — екстрапольованої DCP над модулями, що є степенями двійки . Повна поліноміальна розв’язність DCP стала б значним кроком уперед порівняно з цим результатом, але саме це твердження поки не підтверджене.

Як реагує експертна спільнота

Поточна позиція фахівців зводиться до трьох слів: чекати, перевіряти, не панікувати .

Деякі аналітики постквантової безпеки описують першу реакцію як «глибокий скептицизм» через ескізний характер доведень і посилання на неопубліковані матеріали . Водночас навіть підтвердження поліноміального алгоритму для DCP не означало б автоматичного краху всієї ґраткової криптографії: наслідки для PQC залежать від конкретного шляху зведення, а не лише від самого факту розв’язності DCP .

Станом на зазначений період NIST, академічні лабораторії та організації, що розробляють стандарти, не оприлюднили формальних заяв . Для препринту, якому лише кілька днів, це очікувано.

Висновок

Робота Деніела Саймона може виявитися важливим теоретичним результатом для квантових алгоритмів, DCP і дослідження ґраткової криптографії. Якщо її доведення витримають незалежну перевірку, наслідки для теоретичних основ постквантової безпеки будуть серйозними.

Але на цей момент це лише неперевірений препринт із критично важливими частинами доведення, поданими у стислому вигляді. Він не містить практичної атаки на ML-KEM або ML-DSA, не демонструє зламу параметрів NIST і сам по собі не є підставою змінювати поточні плани розгортання постквантової криптографії .