2025-11-14T17:16:11.719199

Quantum One-Time Protection of any Randomized Algorithm

Gunn, Movassagh
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
academic

Квантовая одноразовая защита любого рандомизированного алгоритма

Основная информация

  • ID статьи: 2411.03305
  • Название: Quantum One-Time Protection of any Randomized Algorithm
  • Авторы: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • Классификация: quant-ph cs.CR
  • Дата публикации: 3 января 2025 г. (arXiv v2)
  • Ссылка на статью: https://arxiv.org/abs/2411.03305v2

Аннотация

Быстрое развитие моделей машинного обучения и зависимость от ценных данных обучения вновь обострили фундаментальное противоречие между удобством локального запуска программ и риском раскрытия деталей программы пользователям. Одновременно фундаментальные свойства квантовых состояний предоставляют новые решения для безопасности данных и программ, требующие минимальных квантовых ресурсов и обеспечивающие преимущества, выходящие за рамки времени вычислений. В данной работе такое решение демонстрируется посредством квантовых одноразовых токенов.

Квантовый одноразовый токен — это квантовое состояние, позволяющее конкретной программе быть вычисленной ровно один раз. Одноразовая безопасность гарантирует, что токен не может быть использован для многократного вычисления программы. Авторы предлагают схему построения квантовых одноразовых токенов для произвольных рандомизированных классических программ (включая модели генеративного ИИ) и доказывают в чёрном ящике, что схема удовлетворяет интересному определению одноразовой безопасности при условии, что выход классического алгоритма имеет достаточно высокую минимальную энтропию.

Исследовательский контекст и мотивация

Определение проблемы

Коммерциализация программного обеспечения сталкивается с фундаментальной дилеммой: как распространять программное обеспечение, не отказываясь от прав собственности? Традиционные решения содержат неотъемлемый компромисс между доступностью и исключительностью:

  1. Схемы обфускации программ: распространение обфусцированной версии программного обеспечения, но с риском пиратства и возможностью неограниченного запуска пользователем
  2. Схемы серверных запросов: сохранение программного обеспечения на сервере для ответа на запросы пользователей, но с снижением доступности и требованием постоянной коммуникации

Значимость проблемы

В эпоху генеративного ИИ эта проблема становится ещё более острой, поскольку:

  • Программное обеспечение может быть чрезвычайно ценным
  • Может содержать приватную информацию
  • Модели оплаты за запрос становятся всё более распространёнными

Ограничения существующих методов

Классическая информация всегда может быть скопирована; как только программное обеспечение распространяется, пользователь может запрашивать его или копировать произвольное количество раз. Это ограничение делает невозможным для традиционных схем одновременно достичь высокой доступности и сильной исключительности.

Преимущества квантового решения

Невозможность клонирования квантовой информации предоставляет возможность улучшить существующие решения:

  • Квантовая защита от копирования: улучшение схемы (1), предотвращение копирования программы при сохранении неограниченного запуска
  • Квантовые одноразовые программы: улучшение схемы (2), исключение онлайн-коммуникации в моделях оплаты за запрос

Основные вклады

  1. Первая универсальная схема квантовой токенизации программ: предложена первая универсальная схема использования квантовой информации для защиты произвольных рандомизированных алгоритмов, не ограниченная конкретными криптографическими функциями
  2. Требования квантовых ресурсов, независимые от сложности программы: размер и сложность квантового токена полностью независимы от защищаемой программы
  3. Теоретическое доказательство безопасности: доказано в чёрном ящике, что схема удовлетворяет определению одноразовой безопасности
  4. Практические соображения: схема достаточно простая для реализации в эпоху NISQ или ранних отказоустойчивых квантовых вычислений

Подробное описание метода

Определение задачи

Построение квантовых одноразовых токенов для защиты произвольного рандомизированного алгоритма f: X × R → Y таким образом, чтобы:

  • Токен позволял программе быть вычисленной ровно один раз
  • Обеспечивал гарантии одноразовой безопасности
  • Не требовал когерентной реализации программы на квантовом компьютере

Основная конструкция (Construction 2)

Криптографические примитивы

Схема опирается на три криптографических примитива:

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify): квантовая схема одноразовой аутентификации
  2. Obf: классический обфускатор программ
  3. H: хеш-функция (моделируется как случайный оракул)

Структура токена

Программный токен состоит из двух частей:

  • |ψ⟩: неклонируемое квантовое состояние, не зависящее от f
  • Obf(P): обфусцированная классическая схема P, зависящая от f

Алгоритмический процесс

KeyGen(1^λ, f):

  1. Выборка sk ← AuthKeyGen(1^λ)
  2. Определение классической схемы P: X × {0,1}^m → Y ∪ {⊥}
    • Вычисление Verify(sk, (x,z)); если отклонено, вывод ⊥
    • Иначе вывод f(x; H(x,z))
  3. Вычисление обфускации P̂ = Obf(P)
  4. Вывод (sk, P̂)

TokenGen(sk):

  1. Вычисление одноразового токена аутентификации |tk⟩ ← AuthTokenGen(sk)
  2. Вывод |tk⟩

TokenEval(x, |tk⟩, P̂):

  1. Вычисление z ← Sign(x, |tk⟩)
  2. Вычисление и вывод P̂(x,z)

Квантовая схема одноразовой аутентификации

Определение (Definition 1)

Квантовая схема одноразовой аутентификации должна удовлетворять:

  • Корректность: легитимные подписи проходят проверку
  • Одноразовая невозможность подделки: любой полиномиальный противник не может сгенерировать две различные действительные пары подписей

Конкретная конструкция (Construction 1)

Основана на одноразовой аутентификации одного бита с использованием скрытых подпространственных состояний:

AuthKeyGen(1^λ): выборка случайного подпространства A ⊆ F₂^λ размерности λ/2

AuthTokenGen(A): вывод |A⟩ = 2^(-λ/4) ∑_{a∈A} |a⟩

Sign(x, |A⟩):

  • Если x = 0: измерение в стандартном базисе и вывод результата
  • Если x = 1: измерение в базисе Адамара и вывод результата

Verify(A, (x,z)): проверка, находится ли z в соответствующем подпространстве

Технические инновации

  1. Программно-независимые квантовые ресурсы: квантовое состояние |ψ⟩ не зависит от защищаемой программы, позволяя защищать сложные программы с помощью небольших квантовых устройств
  2. Механизм привязки случайности: через H(x,z) определяется случайность, эффективно "смешивая" вход, аутентификацию и выход
  3. Свойства коллапсирующей хеш-функции: использование квантовых свойств, где измерение выхода вызывает коллапс входа и метки аутентификации

Теоретический анализ

Определения безопасности

Игра чёрного ящика одноразовой программы G^BB-OTP

  1. Противник получает |ψ⟩ и квантовый доступ к оракулу P̂
  2. Противник отправляет квантовый запрос, вызывающий вычисляет P̂ и измеряет результат y
  3. Если y = ⊥, игра прерывается и противник проигрывает
  4. Противник отправляет второй запрос, вызывающий измеряет y'
  5. Если y' ∉ {y, ⊥}, противник побеждает

Основная теорема

Теорема 2: Если для каждого x ∈ X функция f(x;r) имеет минимальную энтропию по крайней мере poly(λ) относительно случайного r, и квантовая схема одноразовой аутентификации безопасна, то Construction 2 является чёрным ящиком одноразово-безопасным для f.

Ядро доказательства: коллапсирующая хеш-функция

Лемма 1: Пусть f: {0,1}^m × {0,1}^n → Y. Если для всех x функция f(x;r) имеет минимальную энтропию по крайней мере τ относительно случайного r, то при H, являющейся случайным оракулом, функция g^H: x ↦ f(x;H(x)) является коллапсирующей с преимуществом O(q³·2^(-τ)).

Идея доказательства

Использование техники сжимающего оракула:

  1. Доказательство того, что Invert_f и CPhsO почти коммутируют
  2. Использование условия минимальной энтропии для ограничения вероятности коллизий
  3. Реализация коллапса входа через измерение выхода

Экспериментальные результаты и приложения

Требования квантовых ресурсов

  • При использовании схемы одноразовой подписи CLLZ21 пользователю требуется только:
    • Хранение квантового состояния постоянного размера
    • Измерения в стандартном базисе и базисе Адамара

Практические соображения

  1. Ближайшая реализуемость: требования квантовых возможностей независимы от сложности программы
  2. Масштабируемая безопасность: дополнительные квантовые ресурсы используются только для повышения безопасности
  3. Замена классической коммуникацией: возможна замена квантовой коммуникации классической через протоколы удалённой подготовки состояния

Применимые сценарии

  • Защита моделей генеративного ИИ
  • Программные услуги с оплатой за запрос
  • Программы, требующие локального выполнения с высокими требованиями безопасности

Связанные работы

Историческое развитие

  • GKR08: первоначальное исследование одноразовых программ (без квантовых вычислений)
  • BGS13: предложение концепции квантовых одноразовых программ, доказательство невозможности для детерминированных программ
  • BS23: защита функций подписи в стандартной модели
  • GLR+24: параллельная независимая работа, предоставляющая более сильные определения безопасности

Вклад данной работы в сравнении

  • Первая универсальная схема защиты произвольных рандомизированных алгоритмов
  • Простое самодостаточное доказательство безопасности
  • Ориентированный на практику дизайн

Заключение и обсуждение

Основные выводы

  1. Квантовые одноразовые токены могут защищать произвольные рандомизированные классические программы
  2. Безопасность зависит от высокой минимальной энтропии выхода программы
  3. Требования квантовых ресурсов независимы от сложности программы
  4. Схема имеет потенциал реализации в эпоху NISQ

Ограничения

  1. Требование высокой энтропии: выход программы должен иметь достаточно высокую минимальную энтропию
  2. Модель чёрного ящика: доказательство безопасности в идеализированной модели чёрного ящика
  3. Ограничение на детерминированные программы: неприменимо к детерминированным программам (ограничено результатом невозможности BGS13)
  4. Сложные протоколы классической коммуникации: хотя теоретически возможна замена квантовой коммуникации классической, протоколы чрезвычайно сложны

Направления будущих исследований

  1. Анализ безопасности в стандартной модели
  2. Снижение требований к энтропии выхода программы
  3. Реализация и тестирование на реальных квантовых устройствах
  4. Анализ связи с работой GLR+24

Глубокая оценка

Преимущества

  1. Теоретическая инновация: первое предложение универсальной квантовой схемы защиты произвольных рандомизированных алгоритмов
  2. Практический дизайн: развязывание требований квантовых ресурсов от сложности программы повышает практичность
  3. Строгое доказательство: предоставление простого доказательства безопасности на основе коллапсирующих хеш-функций
  4. Перспективы применения: прямое применение к текущим потребностям защиты генеративного ИИ

Недостатки

  1. Идеализированные предположения: зависимость от модели чёрного ящика и модели случайного оракула
  2. Ограничения условия энтропии: требование высокой минимальной энтропии может ограничить диапазон практических приложений
  3. Сложность реализации: хотя теоретически элегантна, практическая реализация всё ещё сталкивается с инженерными вызовами
  4. Определение безопасности: авторы признают, что это не окончательное определение одноразовой безопасности

Влияние

  1. Академическая ценность: предоставление новой теоретической базы для проблемы защиты программ в квантовой криптографии
  2. Практический потенциал: предложение возможного квантового решения для защиты ценных моделей ИИ
  3. Технологический прогресс: продвижение развития некопируемой криптографии
  4. Вдохновляющее значение: предоставление новых идей для практического применения квантовых вычислений в ближайшем будущем

Применимые сценарии

  • Поставщики услуг ИИ, нуждающиеся в защите интеллектуальной собственности
  • Модели лицензирования программного обеспечения с оплатой за использование
  • Защита чувствительных алгоритмов с экстремальными требованиями безопасности
  • Кандидаты для демонстрации квантового преимущества

Библиография

В данной работе цитируются важные работы в области квантовой криптографии, некопируемой криптографии и теории квантовой сложности вычислений, в частности:

  • Aar09 Пионерская работа Ааронсона о квантовой защите от копирования
  • BS23 Работа Бен-Давида и Саттата о квантовых цифровых подписях
  • CLLZ21 Конструкции скрытых смежных классов и некопируемой криптографии
  • Zha19 Работа Жандри о технике сжимающего оракула

Данная статья вносит важный вклад в область теоретической квантовой криптографии, предоставляя элегантное решение для балансирования противоречия между доступностью и безопасностью при распространении программного обеспечения. Хотя остаются вызовы практической реализации, работа предоставляет многообещающее направление для ближайшей реализации приложений квантовых вычислений в криптографии.