Многокопийная безопасность в некопируемой криптографии

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

• ID статьи: 2510.12626
• Название: Multi-Copy Security in Unclonable Cryptography
• Авторы: Alper Çakan, Vipul Goyal, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
• Классификация: quant-ph cs.CR (квантовая физика, криптография и безопасность)
• Дата публикации: 14 октября 2024 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.12626v1

Аннотация

Некопируемая криптография использует принцип квантовой некопируемости для защиты криптографических функций от копирования. Хотя большинство существующих работ решают проблему базовой однокопийной безопасности, концепция более сильной многокопийной безопасности остаётся в значительной степени неисследованной. В данной статье представлен универсальный компилятор, который при наличии только односторонних функций повышает устойчивые к сговору некопируемые примитивы до достижения многокопийной безопасности. Используя эту схему, авторы получают первые конструкции многокопийной безопасности для публичного квантового денежного обращения (называемого квантовыми монетами), шифрования с одним дешифровщиком, некопируемого шифрования и других примитивов. Статья также вводит расширенную концепцию квантовых монет — обновляемые квантовые монеты, которые позволяют слабую верификацию при более слабых предположениях и могут быть обновлены до полной открытой верификации при более сильных предположениях путём публикации банком дополнительной классической информации.

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

Основная проблема

Центральная проблема, решаемая в данной статье, — это повышение от однокопийной безопасности к многокопийной безопасности. В некопируемой криптографии традиционные исследования сосредоточены на параметре некопируемости 1→2 (противник получает одну копию чистого квантового состояния, но не может создать две копии), тогда как более общий параметр q→q+1 (противник получает q копий, но не может создать q+1 копию) изучен меньше.

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

Многокопийная безопасность имеет важное значение:

1. Операционные преимущества: Равенство чистых состояний может быть эффективно проверено с помощью SWAP-теста, что полезно в приложениях
2. Анонимность: Несколько копий одного и того же чистого состояния естественным образом обеспечивают гарантии анонимности
3. Концептуальная мотивация: Несколько копий чистого состояния соответствуют одному и тому же физическому объекту, тогда как состояния, выбранные из одного распределения, могут быть различными

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

Существующие результаты по многокопийной безопасности весьма ограничены:

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

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

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

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

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

Многокопийная безопасность: Для любого полинома t, имея t копий одного и того же чистого состояния, противник не может создать t+1 действительную копию. Это отличается от устойчивости к сговору, при которой даны t независимо сгенерированных состояний.

Основная техника: компилятор очистки (Purification Compiler)

Основная теорема (Теорема 7)

Пусть GenState — это QPT-алгоритм с классическим детерминированным выходом и длиной случайности r(λ). Для ключа PRS k и ключа PRF K определим:

$|ψ_{z,k,K}⟩ = \sum_x α_{k,x}|x⟩ ⊗ |φ_{z,F(K,x)}⟩$

где $\sum_x α_{k,x}|x⟩$ — состояние, создаваемое схемой PRS, а $|φ_{z,F(K,x)}⟩$ — состояние, полученное вызовом GenState(z;F(K,x)).

Основная идея: Через PRS и PRF можно преобразовать t независимо сгенерированных состояний в t копий одного и того же состояния, вычислительно неразличимых.

Принцип работы компилятора

1. Фаза запроса состояния: Испытатель получает от противника запрос количества t, первоначально запускает GenState(st) t раз с независимыми случайными величинами
2. После модификации: Испытатель выводит t идентичных состояний: $\sum_x α_{k_i,x}|x⟩ ⊗ |φ_x⟩$ где $|φ_x⟩ = \text{GenState}(st; F(K_i,x))$
3. Безопасность: На основе безопасности PRS и PRF модифицированный эксперимент вычислительно неразличим от исходного

Примеры применения

1. Конструкция квантовых монет

Компилятор на основе PRS:

• Установка: использование публичной мини-схемы, цифровой подписи и PRS
• Состояние банка: содержит ключ подписи, ключ PRF и ключ PRS
• Генерация банкноты: создание состояния $|⟩ = \sum_x α_x|x⟩|sn_x⟩|\text{Sign}(sgk, sn_x)⟩|$_x⟩$
• Верификация: измерение всех регистров, кроме регистра мини-банкноты, проверка подписи и мини-банкноты

2. Шифрование с одним дешифровщиком

Компилятор от однокопийного к устойчивому к сговору:

• Использование функционального шифрования как промежуточного слоя
• Построение схемы REone.pk для обработки различных режимов шифрования
• Обеспечение безопасности доказательства путём сортировки меток

3. Некопируемое шифрование

Преобразование от SDE к UE:

• Обмен ролей шифротекста и ключа
• Использование техники одноразового заполнения
• На основе устойчивости к сговору при поиске с одинаковыми вызовами

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

Теоретическая аналитическая схема

Статья в основном проводит теоретический анализ, доказывая безопасность через серию гибридных экспериментов:

1. Гибридная последовательность: Построение последовательности вычислительно неразличимых гибридных экспериментов
2. Аргумент редукции: Редукция безопасности новой конструкции к безопасности базовых примитивов
3. Выбор параметров: Обеспечение пренебрежимой потери безопасности путём надлежащего выбора параметров

Техники доказательства безопасности

Доказательство безопасности квантовых монет

• Hyb0 к Hyb1: Безопасность PRF
• Hyb1 к Hyb2: Лемма о квантовом состоянии, доступном только для чтения один раз, с малым диапазоном
• Последующие гибриды: Безопасность цифровой подписи BZ и мини-схемы

Техника пороговой реализации

Использование техники пороговой реализации Zhandry и др.:

• TI_t(P): Пороговая реализация POVM P
• Свойства: Если тест пройден, вероятность успеха измеренного состояния составляет по крайней мере t

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

Основные теоретические результаты

Эффективность конструкций

1. Квантовые монеты: На основе скрытия подпространства и односторонних функций
2. Шифрование с одним дешифровщиком: На основе полиномиально безопасного iO и односторонних функций
3. Некопируемое шифрование: На основе полиномиально безопасного iO и односторонних функций

Гарантии безопасности

• Многокопийная безопасность: Для произвольного полиномиального количества копий
• Стандартная модель: Не зависит от модели случайного оракула
• Оптимальные предположения: Более слабые предположения по сравнению с существующими работами

Сравнительный анализ

Сравнение с существующими работами

vs. Poremba и др. PRV24:

• Данная работа: неограниченная многокопийная безопасность, стандартные концепции безопасности
• PRV24: ограниченная многокопийная, концепции безопасности оракула
• Сила предположений: данная работа требует iO, PRV24 требует только односторонние функции

vs. Ananth и др. AMP25:

• Данная работа: стандартная безопасность аутентифицированного удаления
• AMP25: концепции безопасности оракула
• Применимые сценарии: данная работа поддерживает переиспользуемые и публичные параметры

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

Развитие некопируемой криптографии

1. Квантовое денежное обращение: От сопряжённого кодирования Wiesner к современным публичным схемам
2. Защита от копирования: Квантовая защита программ от копирования
3. Безопасная аренда: Временная передача прав использования ключей
4. Аутентифицированное удаление: Доказуемое удаление данных

Многокопийная vs устойчивость к сговору

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

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

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

1. Впервые представлен универсальный компилятор от устойчивости к сговору к многокопийной безопасности
2. Решена проблема конструкции квантовых монет в стандартной модели
3. Реализованы многокопийные безопасные версии нескольких важных некопируемых примитивов

Ограничения

1. Сила предположений: Некоторые конструкции требуют более сильных криптографических предположений (например, iO)
2. Проблемы эффективности: Компилятор может вносить дополнительные вычислительные затраты
3. Область применения: Требует, чтобы базовые алгоритмы имели классический детерминированный выход

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

1. Оптимизация предположений: Поиск конструкций на основе более слабых предположений
2. Улучшение эффективности: Оптимизация конкретной реализации компилятора
3. Новые приложения: Исследование применения многокопийной безопасности в других криптографических примитивах

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

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

1. Теоретический прорыв: Решение важной теоретической проблемы многокопийной безопасности
2. Универсальность: Предоставление унифицированной схемы, применимой к различным примитивам
3. Техническая инновация: Умелое сочетание техник PRS, PRF и квантового тестирования
4. Полнота: Предоставление полных решений от теоретической схемы до конкретных конструкций

Недостатки

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

Влияние

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

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

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

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

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

• Оригинальные работы Wiesner по квантовому денежному обращению
• Публичное квантовое денежное обращение Aaronson-Christiano
• Псевдослучайные квантовые состояния Ji-Liu-Song
• Техники квантового тестирования Zhandry
• Недавние работы по некопируемому шифрованию и безопасной аренде

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