OpenAI заявляет о прорыве в криптографии: немедленной угрозы для биткоина нет

OpenAI утверждает, что её ИИ-система опровергла гипотезу об экспоненциальном времени — давнее допущение о вычислительной сложности некоторых логических задач. Заявление от 26 октября побудило исследователей организовать независимую проверку. Обнародованный результат не демонстрирует практической атаки на биткоин. Аббревиатура ETH здесь обозначает гипотезу об экспоненциальном времени (Exponential Time Hypothesis), а не Ether. Гипотеза касается задачи 3SAT: компьютеру нужно присвоить значения «истина» или «ложь», удовлетворяющие набору логических условий. Согласно гипотезе, решение в худшем случае требует времени, растущего экспоненциально с числом переменных. Рукопись датирована 17 октября, пересмотрена 25 октября; в ней заявлен детерминированный алгоритм точного подсчёта выполняющих наборов булевых формул фиксированной ширины. Авторы заявляют субэкспоненциальное время работы и полиномиальные требования к памяти. Субэкспоненциальное время растёт медленнее экспоненциальной оценки по мере увеличения размера задачи, но это не значит, что современные компьютеры легко её решат. Заявленная оценка не даёт ни алгоритма полиномиального времени, ни решения вопроса P=NP. Вопрос P=NP — это вопрос о том, имеет ли каждая задача разрешения, решение которой проверяется за полиномиальное время, также решение, вычислимое за полиномиальное время. OpenAI сообщает, что результат проверил пруф-ассистент Lean. Однако в примечании о границах применимости Lean указана более слабая субэкспоненциальная оценка времени, чем сильнейшее утверждение рукописи. Исследователи, организующие независимую проверку, прямо отказались от сертификации результата. В письме организаторов говорится: «Наше участие не должно восприниматься как подтверждение заявленного результата». CryptoSlate ознакомился только с вводными страницами, а не с полным доказательством. Майнинг биткоина и авторизация расходования средств — разные задачи безопасности. Майнеры ищут хеш заголовка блока ниже целевого значения. Подписи подтверждают право на расходование. Биткоин использует подписи ECDSA и Schnorr на эллиптической кривой secp256k1, как описано в BIP340. Допущения безопасности в BIP340 опираются на дискретные логарифмы в группе точек эллиптической кривой и на хеш-функции. Восстановление ключа — это вопрос о том, может ли атакующий получить закрытый ключ по соответствующему открытому ключу. Опровержение допущения о SAT в худшем случае само по себе не демонстрирует способа обойти эти конкретные механизмы защиты. Практическая атака потребовала бы подходящего кодирования, работающей реализации и сравнения затрат для целевой задачи. Число переменных в SAT-формуле нельзя подставить вместо длины битового ключа или хеша. В примечании Lean оценка выражена через переменные закодированной формулы и длину входа. Подстановка битовой длины криптографического примитива в эту оценку обошла бы необходимую процедуру представления реальной задачи. Биткоин корректирует целевую сложность каждые 2016 блоков. Эта корректировка управляет выпуском блоков, а не авторизацией подписей. Она не устранила бы значимости приватного преимущества в майнинге. 7 октября Джастин Дрейк призвал готовиться к «режиму бункера» после более раннего анонса OpenAI по математике. Предупреждение Дрейка касалось потенциальной будущей атаки, тогда как тот анонс не демонстрировал практического взлома ECDSA или RSA. Заявление OpenAI от 26 октября относится к другому результату. Райан Уильямс сообщил, что его, Рассела Импальяццо и Мохана Патури попросили организовать открытую независимую проверку без соглашений о неразглашении и без оплаты. Уильямс также сказал, что просил OpenAI проверить, не скомпрометированы ли существующие криптосистемы, и передал, что они, судя по всему, остаются в безопасности. Его слова — сведения из вторых рук о проверке, запрошенной у OpenAI, а не независимый криптографический аудит. OpenAI заявляет, что для практических улучшений необходимы существенные дополнительные исследования. Уильямс сказал, что не знает, получат ли разработчики выгоду, оставив открытыми как прогресс в течение 12 месяцев, так и отсутствие такого прогресса. Организаторы планируют публиковать результаты по ходу проверки.