23 июля Прабханджан Анант (Калифорнийский университет в Санта-Барбаре) и Амит Сахаи (UCLA) выложили на arXiv статью «Unconditional Unclonable Encryption», которая закрывает проблему, стоявшую перед квантовыми криптографами шесть лет. Но не меньше самого результата обсуждают короткий раздел в конце введения: конструкция и основные идеи доказательства были целиком сгенерированы агентом Codex на модели GPT-5.6 Sol Ultra. Люди придумали для модели программную обвязку, а затем проверили и отшлифовали каждое утверждение — и берут на себя полную ответственность за результат.
Речь про unclonable encryption — «нескопируемое» шифрование. Обычный шифртекст — это просто данные: его можно размножить на тысячу флешек, и если ключ однажды утечет, прочитают все, у кого осталась копия. Квантовая механика позволяет сделать иначе: неизвестное квантовое состояние невозможно скопировать — это не техническая трудность, а закон природы (теорема о запрете клонирования, 1982 год). Еще в 2003 году Дэниел Готтесман предложил записывать шифртекст в кубиты, чтобы тот существовал в единственном экземпляре; ключ при этом остается обычной классической строкой битов — квантовый здесь только сам шифртекст. Получается свойство, немыслимое для классической криптографии: даже если секретный ключ потом объявить всему миру, прочитать сообщение сможет только один человек — тот, у кого оригинальное состояние. Остальным просто нечего расшифровывать.
Формально безопасность описывается игрой с тремя участниками. Атакующий получает один экземпляр квантового шифртекста и пытается изготовить из него две полезные «копии» любыми средствами, которые разрешает физика, а результат делит между Бобом и Чарли — дальше те не общаются. Затем обоим выдают ключ, и каждый называет свою догадку про зашифрованный бит. Один из двоих может угадать всегда: достаточно отдать ему шифртекст целиком, и он честно расшифрует. Весь вопрос в том, могут ли угадать оба сразу — если да, значит, копирование в каком-то смысле удалось. Стойкость означает, что вдвоем у них не выходит существенно лучше, чем если бы они заранее договорились называть один и тот же случайный бит.
В 2020 году Энн Бродбент и Себастьен Лорд доказали для своей схемы слабый вариант стойкости — search security: если зашифровать длинное случайное сообщение, Боб и Чарли не смогут оба восстановить его целиком. Для практики этого мало, потому что настоящие сообщения не случайны: если противник знает, что в депеше либо «наступаем», либо «отступаем», ему не нужно читать текст — достаточно отличить одно от другого. Защиту от такого дает сильный вариант, indistinguishability: атакующий сам выбирает два сообщения, хоть «да» и «нет», и должен лишь понять, какое из них зашифровано. Именно он и оставался открытым.
Шесть лет полный результат не давался. Сильную стойкость умели доказывать, но каждый раз с одним неприятным компромиссом: то ключи приходилось делать квантовыми (вместо удобных классических), то доказательство работало только в идеализированных моделях со случайным оракулом, то шифрование требовало экспоненциального времени, то преимущество атакующего удавалось прижать лишь до обратно полиномиального. Накапливались и результаты о невозможности: было показано, что целые классы естественных подходов — например, схемы на BB84-состояниях с XOR-повторением — до нужной границы не дотягивают в принципе.
Юэн описывает причину тупика военной метафорой: у сообщества, по его словам, была «одна пуля в барабане» — метод анализа через моногамию запутанности из работы Томамичела, Фера, Каневского и Венера 2012 года. Все известные доказательства стойкости в этой области так или иначе сводились к нему, а к задаче про indistinguishability его приложить не удавалось. ChatGPT, пишет Юэн, судя по всему, нашел другой способ анализа нескопируемого шифрования, который к этому методу не сводится.
Что именно в статье. Ключ описывает случайный оператор Паули на n кубитах — гарантированно не единичный — и занимает 2n−1 классических бит. Секретный бит спрятан в знаке: шифртекст готовится так, чтобы измерение этого оператора давало +1 для нуля и −1 для единицы. Шифрование обходится однокубитными гейтами, дешифрование — локальными измерениями, все за линейное время. Сама конструкция при этом не нова: ее предложили Пьер Боттерон, Энн Бродбент и соавторы, которые сформулировали гипотезу о ее стойкости и проверили ее численно, но лишь для небольших значений параметра (до 17) — а доказать не смогли. Вклад Ананта и Сахаи — доказательство: преимущество любого атакующего, даже вычислительно неограниченного, не превышает 2^((−(n+1)/2)), то есть экспоненциально мало. Никаких недоказанных предположений, никаких оракулов.
Интересно, что доказательство собрано из элементарных инструментов — линейная алгебра, неравенство Коши — Шварца, ни одной тяжелой квантовой теоремы. Атака сводится к оценке нормы одного оператора, собранного из операторов измерений Боба и Чарли. Ключевых хода два: оператор центрируют (вычитают единичный — предшественники работали с нецентрированной версией и дальше гипотезы продвинуться не смогли), а его максимальное собственное число ограничивают специально построенным «фильтром», подавляющим направления, в которых ответы Боба и Чарли расходятся. Схема рассуждения достаточно короткая, чтобы ее можно было проверить вручную — что авторы, по их словам, и сделали.
Теперь про роль ИИ, как она описана самими авторами. В разделе «Statement on AI usage» сказано: конструкция и главные идеи доказательства целиком сгенерированы Codex на GPT-5.6 Sol Ultra; люди придумали идеи харнесса — той самой обвязки, которая ставит модели задачу и организует ее работу. Харнесс собран на основе UCLA Moonshot Harness (университетский проект, среди руководителей которого сам Сахаи и Теренс Тао) и промпта, который OpenAI опубликовала после июльской истории с доказательством гипотезы о двойном покрытии циклами. То есть «промптинг теорем» перестает быть разовым фокусом: методичка выложена публично, и по ней уже работают сторонние группы.
А через два дня выяснилось, что вторая пуля у модели не одна. 25 июля на Cryptology ePrint Archive появилась независимая работа Сеюна Рагавана из MIT «Efficient Unclonable Encryption from Pauli Eigenstates»: та же задача, близкая конструкция на собственных состояниях операторов Паули — и снова GPT-5.6 Sol Ultra. По признанию автора, доказательство центральной леммы модель отыскала в длинном диалоге с ним и сама набросала черновик статьи. Причем рассуждение устроено иначе: вместо «фильтра» — спектральные свойства коммутационной структуры группы Паули. Одна и та же модель за несколько дней дважды закрыла одну шестилетнюю проблему — с разными людьми, в разных интерфейсах и разными математическими путями.
О чем стоит помнить. Обе работы — препринты, рецензирования еще не было. Формулировка «конструкция сгенерирована ИИ» требует оговорки: модель, по сути, переоткрыла уже опубликованную схему Боттерона и Бродбент, так что подлинная новизна — в доказательстве. Однако авторы — криптографы первой величины, взявшие на себя ответственность за каждое утверждение, доказательство короткое и проверяемое без компьютера, а Генри Юэн — один из ведущих специалистов области — уже публично назвал проблему решенной (твит в начале статьи). Да и два независимых доказательства всегда лучше одного.
P.S. Поддержать меня можно подпиской на канал «сбежавшая нейросеть», где я рассказываю про ИИ с творческой стороны.
ссылка на оригинал статьи https://habr.com/ru/articles/1063122/