OpenAI заявила, что её новая модель Astra добилась прогресса в решении десятка открытых математических задач, которые годами не поддавались научному сообществу. Среди этих задач есть имеющие отношение к криптографии.

📣 Мы попросили прокомментировать это Ивана Чижова, заместителя руководителя лаборатории криптографии по научной работе в компании «Криптонит». Делимся с вами! #мнения_экспертов

Часть полученных OpenAI результатов имеет значение для криптографии — как классической, так и постквантовой. Например, в одной из работ с помощью Astra получен результат по задаче поиска ближайшего вектора (Closest Vector Problem, CVP).

Сама NP-трудность CVP известна с 1981 года; доказана NP-трудность её приближённого решения с полиномиальным множителем — раньше такая трудность была известна лишь для почти полиномиальных множителей.

🔴Результат укрепляет теоретическую картину вокруг криптографии на решётках, но надёжности постквантовых схем он не доказывает: это трудность в худшем случае, тогда как реальные схемы опираются на трудность в среднем этих задач.
 
❗️За четыре дня до публикации OpenAI, 28 июля, компания Anthropic показала результат своего эксперимента по использованию ИИ в криптографии. Она опубликовала улучшенную атаку восстановления ключа на постквантовую схему подписи HAWK, найденную с помощью модели Claude Mythos Preview.

Речь не о взломе: атака остаётся экспоненциальной, но вдвое снижает эффективную длину ключа. Секретный ключ удалось восстановить за несколько часов на одном сервере — для набора параметров HAWK-256.

Оговорка, которую часто теряют в пересказах: 256 здесь — степень многочлена, с помощью которого задано кольцо, а не длина ключа. HAWK-256 представляет собой испытательный набор параметров для криптоаналитиков, не отвечающий ни одному уровню стойкости NIST.

❗️Боевые наборы, HAWK-512 и HAWK-1024, атакой практически не затронуты, и нигде не применяются — HAWK был кандидатом конкурса, а не действующим стандартом. Тем не менее разработчики признали проблему и отозвали схему: восстановить запас стойкости можно было бы примерно удвоив размеры ключей, а это лишило бы HAWK главного преимущества — компактности подписей.

🧠Сейчас есть мощные модели ИИ, способные работать со сложными математическими задачами. Я и сам применял одну продвинутую модель для ускорения поиска ошибок в доказательствах. Если пользоваться ею с умом и проверять результаты, это очень сильный инструмент.

🔴Но узким местом становится как раз проверка: в работе Anthropic двое исследователей потратили около месяца, чтобы убедиться в корректности одной найденной моделью атаки. Так что ручной анализ никуда не уходит — меняется то, на что уходит время математика: постановка задачи, её формальное описание и разбор полученного вывода.

Канал «Криптонита» в MAX