OpenAI заявляє про прорив у криптографії: негайної загрози для Bitcoin немає
OpenAI заявляє, що її ШІ-система спростувала гіпотезу експоненційного часу (ETH) — давнє припущення про обчислювальну складність окремих логічних задач. Заява від 26 жовтня спонукала дослідників організувати незалежну перевірку. Оприлюднений результат не демонструє практичної атаки на Bitcoin. Абревіатура ETH тут означає гіпотезу експоненційного часу, а не Ether.
Гіпотеза стосується 3SAT — задачі, у якій комп’ютер має присвоїти значення true або false, щоб задовольнити набір логічних умов. Згідно з гіпотезою, розв’язки для найгіршого випадку потребують часу, що зростає експоненційно з кількістю змінних. Рукопис від 17 жовтня, переглянутий 25 жовтня, заявляє про детермінований алгоритм точного підрахунку задовольняючих наборів для булевих формул фіксованої ширини. У ньому йдеться про субекспоненційний час виконання та поліноміальні вимоги до пам’яті. Субекспоненційний час зростає повільніше за експоненційну межу зі збільшенням розміру задачі, але це не означає, що сучасні комп’ютери легко її розв’яжуть. Заявлена межа не встановлює ні поліноміального алгоритму, ні рішення P=NP. Питання P=NP полягає в тому, чи кожна задача прийняття рішення, розв’язок якої можна перевірити за поліноміальний час, має також розв’язок, обчислюваний за поліноміальний час.
OpenAI каже, що результат перевірив помічник доведення Lean. Водночас примітка Lean про сферу застосування описує слабшу субекспоненційну межу часу, ніж найсильніше твердження рукопису. Дослідники, які організовують незалежну перевірку, прямо відмовилися від сертифікації. У їхньому листі зазначено: «Нашу участь не слід вважати підтвердженням цього твердження». CryptoSlate ознайомився лише з вступними сторінками 1–8, а не з повним доведенням.
Майнінг Bitcoin і авторизація витрат — це різні безпекові задачі. Майнери шукають хеш заголовка блоку, що нижчий за ціль. Підписи засвідчують право на витрачання. Bitcoin використовує підписи ECDSA і Schnorr на еліптичній кривій secp256k1, як описано в BIP340. Безпекові припущення BIP340 стосуються дискретних логарифмів на еліптичній кривій і хеш-функцій. Відновлення ключа — це питання, чи може атакуючий отримати приватний ключ із відповідного публічного ключа. Спростування припущення SAT для найгіршого випадку саме по собі не демонструє способу подолати ці конкретні механізми безпеки. Практична атака потребувала б належного кодування, робочої реалізації та порівняння витрат для цільової задачі. Кількість змінних SAT-формули не можна підставляти замість бітової довжини криптографічного ключа чи хешу. Межа Lean виражена через змінні закодованої формули та довжину входу. Підстановка криптографічної бітової довжини в цю межу обійшла б необхідне подання фактичної задачі.
Bitcoin коригує ціль майнінгу кожні 2 016 блоків. Коригування регулює виробництво блоків, а не авторизацію підписів. Воно не усунуло б важливості приватної переваги в майнінгу. 7 жовтня Джастін Дрейк закликав готуватися до «режиму бункера» після попередньої математичної заяви OpenAI. Його попередження стосувалося потенційної майбутньої атаки, тоді як попередня заява не продемонструвала практичного зламу ECDSA чи RSA. Твердження OpenAI від 26 жовтня стосується окремого результату.
Раян Вільямс повідомив, що його, Рассела Імпальяццо та Могана Патурі попросили організувати відкриту незалежну перевірку без угод про нерозголошення та без оплати. Окремо Вільямс сказав, що просив OpenAI перевірити, чи не скомпрометовано чинні криптосистеми, і передав, що вони, вочевидь, залишилися безпечними. Свідчення Вільямса — переказ про перевірку, запитану в OpenAI, а не незалежний криптографічний аудит. OpenAI каже, що для практичних покращень потрібні значні додаткові дослідження. За словами Вільямса, він не знав, чи побачать розробники переваги, тож залишав відкритими і прогрес протягом 12 місяців, і відсутність такого розвитку. Організатори планують публікувати результати під час перевірки.
