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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:52, 7 декабря 2015.
Classical Cryptographic Protocols in a Quantum World
Classical Cryptographic Protocols in a Quantum World.png
Авторы Sean Hallgren[@: 1], Adam Smith[@: 2], and Fang Song

Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, U.S.A.

Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Michael Sokolov
Год перевода 2015 г.
Скачать оригинал

Аннотация. Криптографические протоколы, такие как протоколы вычисления функции надежности (SFE), сыграли решающую роль в развитии современной криптографии. Однако значительная часть теории в этих протоколах имеет дело исключительно с классическими атаками. Если принять, что квантовая обработка информации является наиболее реалистичной моделью физически возможных вычислений, то мы должны спросить: что классические протоколы оставляют безопасным в отношении квантовых атак? Наш основной вклад показывает существование классических двухсторонних протоколов для оценки безопасности любой полиномиальной функции при разумных вычислительных допущениях (например, достаточно того, что проблема обучения с ошибками трудна для квантового полиномиального времени). Наши выводы показывают, что основная двухпартийная технико-экономическая картина неизменна в квантовом мире.

Введение

Криптографические протоколы, такие как протоколы вычисления функции надежности (SFE), сыграли решающую роль в развитии современной криптографии. Голдрейх, Микали и Вигдерсон [1], опираясь на доказательство с нулевым разглашением (ZK) [2][3], показали, что протоколы SFE существуют для любой полиномиальной функции с умеренными допущениями (грубо говоря, существование безопасных криптосистем с открытым ключом). Исследования и анализ таких протоколов в настоящее время большая область в криптографии; Также определяются важные достижения в более традиционных областях криптографии таких, как создание схем шифрования, аутентификации и схем подписей.

Однако значительная часть теории в этих протоколах имеет дело исключительно с классическими атаками. Однако, учитывая наше нынешнее знание физики, квантовая обработка информации является наиболее реалистичной моделью физически возможных вычислений. Естественен вопрос: что классические протоколы оставляют безопасным в отношении квантовых атак? Во многих случаях, даже противники с небольшими возможностями квантовых вычислений, таких как возможность обмениваться и хранить связанные парамы фотонов, не защищены существующими доказательствами безопасности. Понятно, что не все протоколы небезопасны: мы можем опустить все, что основывается на вычислительной сложности факторинга, дискретном логарифмировании [4], или проблеме главного идеала [5].

Более тонко, основные методы, используемые для размышления о безопасности не могут применяться в квантовой обстановке. Например, протоколы передачи анализируются путем просмотра доказывающей стороны, как длинных таблиц, которые исправляются до запросов проверяющего; квантовое связывание предотвращает анализ и некоторые протоколы незащищены против сговоривщихся квантовых доказателей (Крепау,[6]). В вычислительной области, перемотка - ключевая техника для основы безопасности протокола на тяжести какой-либо основной проблемы. Намоточные доказательства состоят из мысленного эксперимента, в котором злоумышленник действует несколько раз, используя осторожные изменения из данных входных данных. На первый взгляд, перемотка кажется невозможной с квантовым злоумышленником, поскольку несколько действий может изменить связь между внутренним хранилищем и внешний системой ссылок, изменяя, таким образом, поведение системы в целом.

Ватроуз [7] показал, что особый тип доказательства с нулевым разглашением может быть безопасным с помощью перемотки аргумента приспособленного для квантовых злоумышленников. Дамгард и Луниман[8] показали, что подобный анализ может быть применен к варианту протокола Блюма. Халлгрен[9] показал, что определенные классические преобразования доверенного проверяющего в вредоносного проверяющего могут быть изменены для обеспечения безопасности от вредоносных квантовых проверяющих.

Некоторые классические протоколы безопасности могут противостоять квантовым атакам[10][11][12][13]. И наконец, над протоколами еще существует много работы, которая включает квантовые связи, начиная с алгоритма обмена ключами Беннетт-Брассард. В целом, однако, мало что известно о том, много-ли классической теории может быть применено в квантовой области. Смотрите "Связанная работа" ниже, для более подробного описания.

Наш вклад

Наш основной вклад показывает существование классических двухсторонних протоколов для оценки безопасности любой полиномиальной функции при разумных вычислительных допущениях (например, достаточно того, что проблема обучения с ошибками трудна для квантового полиномиального времени). Наши выводы показывают, что основная двухпартийная технико-экономическая картина неизменна в квантовом мире. Единственные двусторонние общие протоколы SFE, которые ранее были проанализированы на присутствие квантовых атак, потребовали квантовых вычислений и связи доверенных участников (например, [14][15]).

В дальнейшем, мы будем различать два основных параметра: в автономной обстановке протоколы работают в режиме изоляции, без других протоколов, работающих одновременно; в сетевой обстановке, протоколы должны оставаться безопасным, даже если доверенные участники работают с другими протоколами (или копией того же протокола) одновременно. Протоколы, которые безопасны в модели универсальной композиции (UC)[16], безопасны в произвольной сетевой области, но UC-безопасности невозможно добиться во многих областях. Наши вклады могут быть разбиты следующим образом:

Классические аргументы нулевого разглашения о знании безопасности против квантовых злоумышленников. Построим классический протокол аргумента нулевого разглашения знаний (ZKAoK), который безопасен в нашей модели. В частности это означает, что наша конструкция "свидетеле-расширяема" [17], в том смысле, что можно имитировать взаимодействие с вредоносный доказывателем и одновременно извлекая свидетельство о заявлении, когда этот доказыватель успешн. Наша конструкция преодолевает ограничение доказательств знаний, недавно проанализированных Унру [18], где симуляция доказывающего не представлена, и, таким образом неясно, как анализировать безопасность при использовании его доказательств знаний как подпротокола. Как и в классическом случае, наш протокол ZKAoK является важным для построения блока в разработке общих протоколов SFE.

Основная идея нашей конструкции в том, чтобы иметь доказывающего и проверяющего выполняющих слабый протокол переворота монеты, чтобы сгенерировать открытый ключ для особого типа схемы шифрования. Доказывающий шифрует своего свидетеля по отношению к публичному ключу и доказывает согласованность его зашифрованного текста с оператором х с использованием протоколов ZK, проанализированых Ватроузом[7]. Симуляция, играющая роль проверяющего, может фазой переворота монеты для генерации открытого ключа, для которого она знает секретный ключ, что позволяет ей извлечь свидетеля без необходимости перемотки доказывающего. Симуляция, играющая роль доказующего, с другой стороны, не может контролировать переворот монеты, но может гарантировать, что открытый ключ почти случаен. Если схема шифрования удовлетворяет дополнительным, нестандартным свойствам (которые могут быть реализованы при широко используемых допущениях в виде решетки), мы показываем, что мнение проверяющего может быть верно смоделировано. Лунеман и Нильсен[19] независимо дали похожие конструкции ZKAoK для квантовых злоумышленников; см "Связанная работа".

(Подробнее) Основное моделирование автономной безопасности с квантовыми злоумышленниками. Опишем модель безопасности для двухсторонних протоколов с квантовыми злоумышленниками. Доказательство безопасности в этой модели состоит в показывании того, что протокол для вычисления функции ведет себя неразличимо от «идеального» протокола, в котором вычисляется доверенной третьей стороной, которую мы называем идеальной функциональностью . Наша модель это квантовый аналог модели автономной безопасности, разработанной Канетти[20] в классической области. Она немного обобщает существующую модель Дамгарда[15] по двум путям. Во-первых, наша модель позволяет протоколы, в которых идеальные функциональности обрабатывают квантовую информацию (а не только классические функциональности). Во-вторых она позволяет злоумышленникам, которые принимают произвольное квантовое суждение, и для любой связи между входными данными доверенных и вредоносных участников.

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

Классические UC протоколы в квантовом контексте: на пути к гипотезе Унру. Покажем, что большой класс протоколов, которые являются UC-безопасными против вычислительно-ограниченных классических злоумышленников также UC-безопасны от квантовых злоумышленников. В недавней работе, Унру[13] показал, что любой классический протокол, который UC-безопасен от неограниченных классических злоумышленников также UC-безопасен от неограниченных квантовых злоумышленников. Он предположил, (см[13] для точного описания), что классические аргументы вычислительной UC безопасности также должны пройти до тех пор, как основные вычислительные примитивы не легко поддаются взлому на квантовых компьютерах.

Мы поддерживаем эту гипотезу, описывая семью классических аргументов безопасности, которые проходят стеганографию с квантовыми злоумышленниками. Мы называем эти аргументы "Простые гибридные аргументы". Они не используют перемотки ни в моделировании, ни в каком-либо из шагов, которые показывают верность моделирования.[прим. 1]

Наши наблюдения позволяют нам перенести основные выводы Канетти, Линделла, Островского и Сахаи[21] в квантовую область. Получаем следующее: в -гибридной модели, где идеальная функциональность доступна с помощью ZKAoK, существуют классические протоколы оценки любых полиномиальных функций , которые являются UC-безопасными против квантовых злоумышленников под разумными вычислительными предположениями.

Как немедленное следствие, мы получаем классический протокол, который квантово UC-эмулирует идеальную функциональность для переворота монетки. Адаптируя идей из[17], мы также даем прямую конструкцию переворота монетки от ZK. Что более интересно, мы можем развить обратное суждение, описывая простой классический протокол для ZKAoK, который UC-безопасен против квантовых злоумышленников в -гибридной модели(извесная как строка общих ссылок, где все участники имеют доступ к единой, равномерно распределенной последовательности битов). “Простые гибридные аргументы”, упомянутые выше, не являются достаточными для доказательства безопасности UC-безопасного ZKAoK протокола. В частности, одним из составляющих нашего протокола, конструкция неразличимых свидетелей как системы доказательства, нуждается в новом доказательстве безопасности. Основная стратегия это все еще гибридный аргумент, но ее анализ требует разбиения пространства возможных исходов на части (классически, оно включает обусловленность взаимодополняющих мероприятий; квантово, оно предполагает проецирование на ортогональные подпространства) и утверждая, что (а) злоумышленник не может иметь значительное преимущество в любой части и (б) в исходное состояние была сочетанием, а не суперпозицией из двух частей. Это доказывает эквивалентность между и в UC модели, которые могут представлять самостоятельный интерес, например, в упрощении конструкции протоколов.

Вывод. Теорема модульной композиции в нашей автономной модели позволяет получить основную осуществимость результата ниже объединив нашу автономную модель ZKAoK протокола и UC-безопасных протоколов в -гибридной модели: В рамках стандартных предположений, существуют классические SFE протоколы на плоской модели (без общих случайных строк), которые являются автономно-защищенными от статических квантовых злоумышленников. Они сходны с классическими выводами Голдерича, Микали и Виджерсона[1].

Эквивалентность функционалов нулевого разглашения и переворота монетки в UC модели также дает интересные последствия. Во-первых, наличия общей строки ссылок достаточно для реализации квантовых UC-защищенных протоколов. Во-вторых, учитывая наш автономный ZKAoK протокол, мы получаем квантовую автономный протокол переворота монетки в связи с вышеупомянутой эквивалентности. Независимо от нашей работы, Лунеманом и Нильсеном[19] были получены аналогичные нашим результаты. См. обсуждение в конце “Связанная работа”.

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

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

Состав структуры квантовых протоколов. Систематические исследования свойств состава квантовых протоколов являются относительно недавними. UC система Канетти и тесно связанная система реактивной финкциональности Фицмана и Ваиднера были расширены до мира квантовых протоколов и злоумышленников Бен-Ора, и Мэйерса,[22] и Унру[23][13]. Эти системы (которые разделяют сходную семантику) обеспечивают стойкие гарантии безопасности в произвольных сетевых средах. Они были использованы для анализа ряда безусловно безопасных квантовых протоколов (обмен ключами[24] и многопартийные вычисления с доверенным большинством[11]). Тем не менее, многие протоколы не являются универсально составными, и Канетти[16] показал, что классические протоколы не могут UC-надежно реализовать даже базовые задачи, такие как передача и доказательства с нулевым разглашением без дополнительных допущений, таких как CRS или инфраструктура c открытыv ключом.

Дамгард[15], опираясь на работы Фера и Шафнера[12] предложил общий состав системы, которая применяется только к квантовым протоколам безопасности конкретной формы (там, где квантовое общение появляется только на низких уровнях модульной композиции). Как отмечалось ранее, наша модель является более общей и охватывает и классические, и квантовые протоколы. При этом, понимание конкретной взаимосвязи между моделями является непростым, и связано с основными вопросами теории сложности такими как мощность квантового сообщения (BQP/poly против BQP/qpoly). Мы отложим дальнейшее обсуждение этого отношения до полной версии.

Анализ квантовых протоколов. Первые точные доказательства безопасности квантовых протоколов были для обмена ключами (Майерс[25], Ло и Чау[26], Шор и Прескиль[27], Бивер[28]). Исследования по квантовым протоколам для двухсторонних задач, таких как переворот монетки, битовая передача и безразличная передача пойдет дальше[29][30] но многие изначально предложенные протоколы были небезопасны[25]. Первые доказательства безопасности таких протоколов были на основе вычислительных допущений[31][14]. Они были весьма протоколо-зависимыми и было неизвестно, насколько хорошо протокол составлен. Первые доказательства безопасности с использованием парадигмы моделирования были для теоретически-безопасных протоколов для многосторонних вычислений в предположении строгого большинства доверенных участников[10][32][11]. Впоследствии, работа над ограниченным квантовым хранилищем[33][34][12][35] создала инструменты для рассуждений о конкретных типах композиции двухсторонних протоколов, по допущениям на размер квантового хранилища злоумышленника. Работа по UC безопасности Унру, упомянутая выше, была первой откуда мы узнали о достаточно общей и охватывающей классические и квантовые протоколы композиции.

Прямолинейное моделирование и игры основанные на кодах. Как уже упоминалось выше, мы вводим “простые гибридные аргументы” для охвата класса прямого анализа системы безопасности, который идет против квантовых злоумышленников. Несколько формализмов были введены ранее, чтобы охватить класс “простых” соображений "безопасности". По нашим сведениям, ни один из их автоматически несовместим с квантовыми злоумышленниками. Например, прямолинейное моделирование черного ящика[36] не перематывает злоумышленника, ни использует явное описание его случайных монет; Однако, это может быть случай того, что перемотка нужна для доказательства того, что прямолинейное моделирование корректно. В другом ключе, игры основанные на кодах Беллара и Рогвейя[37] охватывают класс гибридных аргументов, которые могут быть закодированы на чисто формальном языке; однако снова, аргументы относительно каждого шага гибрида по-прежнему могут требовать перемотки.

Независимая работа: Лунеман и Нильсен[19]. Лунеман и Нильсен[19] независимо получили результаты, аналогичные описанным здесь, несколько иным путем. В частности, они начинают с создания автономных протоколов переворота монеты, полностью моделируемых против квантовый полиномиальных злоумышленников. Затем они используют протокол переворота монеты для построения автономных ZKAoK протоколов, и наконец, включив в конструкцию GWM, они также получают квантовый автономный двухсторонний SFE протокол. Вычислительная допущения в обоих работах похожи и на круговая сложность автономного SFE протокола в обоих случаях полиномиальна в параметре безопасности. Наш подход к композиции является более общим, однако, приводит к результатам, которые также применяются (в частности) к UC модели.

Организация. Остальная часть статьи организована следующим образом: в разделе 2 рассматриваются основные обозначения и определения. В разделе 3 мы представляем нашу модель автономной квантовой безопасности. Квантовый автономно-безопасный протокол ZKAoK разработан в разделе 4. Раздел 5 изучает семью классического анализа, проходящего в квантовой UC модели, а затем в разделе 6 рассмотрены вопросы эквивалентности и . Наконец, в разделе 7, мы получаем, среди прочих последствий, классическую SFE, которая являются квантово автономно-безопасной без допущений. Мы сделаем выводы о будущих направлениях.

Предварительные замечания

Для , обозначает множество . Мы используем для обозначения параметра безопасности. Параметр безопасности, представленный унарным, это безусловный вход для всех криптографических алгоритмов; мы его опускаем если он понятен из контекста. Величина полученная из протоколов или алгоритмов (вероятности, текущее время, и т. д.) должны рассматриваться как функции от , если не указано иное. Функции называется ничтожно малой, если для любой константы , а используется для обозначения неопределенной функции, которая пренебрежимо мала в . Мы также используем для обозначения неопределенной функции для некоторой константы . Пусть и два множества двоичных случайных величин. Мы называем и неразличимыми, обозначаем , если . Мы предполагаем, что читатель знаком с основными понятиями теории квантовой информации (см., например,[38]). Мы используем заглавную букву (например, ) для обозначения квантового регистра и для каждого , мы используем рукописную букву (например, ) для обозначения соответствующего Гильбертова пространства. Пусть множество операторов плотности, действующих на пространстве . Пусть множество смешанных состояний, где и является -кубитовым пространством.

Модель квантовой машины. Мы адаптируем машины модель Унру из[13] с незначительными изменениями. Квантовая интерактивная машина (КИМ) это множество цепей , для каждого значения параметра безопасности. работает на трех регистрах: регистр состояния используется для ввода и рабочей области; регистр выхода ; и сетевой регистр для общения с другими машинами. Мы говорим, что размер (или рабочее время) - , если существует детерминированная классическая машина Тьюринга, которая вычисляет характеристику за время на входе . Мы говорим, что машина полиномиальна, если .

Когда две КИМ и взаимодействуют друг с другом, они разделяют регистр . Цепи и выполняются поочередно. Когда между собой взаимодействуют три и более машин, они могут делить разные части своих сетевых регистров (например, закрытый канал состоит из регистра разделенного только между двумя машинами; широковещательный канал - общий регистр для всех машин). Порядок в котором машины активируются может быть либо определен заранее (как в синхронной сети) или же может быть контролируемым противоборством.

Неинтерактивная квантовая машина (называемая далее НКМ) это КИМ без сетевого регистра, который работает только один цикл (для всех ). Это эквивалентно модели квантовой машины Тьюринга (см.[39]). Классическая интерактивная машина это особый случай КИМ, где регистры хранят только классические строки и все циклы классические. Классические полиномиальные КИМ эквивалентны полиномиальным интерактивным машинам Тьюринга.

Неразличимость квантовых состояний. Напомним понятие неразличимости квантовых состояний Ватроуза.

Определение 1. ( - неразличимые квантовые состояния.[[7], определение 2]) Два квантовых множества состояний и - квантово неразличимы, обозначаются , если для любого -времени НКМ и любое смешенное состояние -кубитная вспомогательная система,

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

Неразличимость квантовых машин. Далее определим неразличимость квантовых интерактивных машин. Пусть две КИМ, обозначаем как процесс, при котором с помощью вспомогательного ввода , взаимодействует с и, наконец, выводит один классический бит 1 или 0.

Определение 2 (-неразличимые КИМ). Две КИМ и интерактивно неразличимы, обозначаются если для любой квантовой -временной интерактивной машины и любого смешанного состояния на кубитах, , где для . КИМ и называются интерактивно неразличимыми, обозначаются , если для любого существует незначительная такая как и -интерактивно независима.

И наконец, мы формулируем вычислительные допущения, которые используем в своей работе.

Предположение 1 Существует классический генератор псевдослучайных чисел, безопасный относительно квантовых различий.

Основываясь на этом предположении и конструкции в [40], мы можем получить статистически связанную и квантово вычисляемую схему скрытой передачи(comm,decomm). Все схемы передачи, которые мы будем использовать далее относятся к этой. Этого предположения также достаточно для системы ZK-доказательства Ватроуза для любого NP-языка против квантовых атак.

Предположение 2 Существует непрозрачная классическая криптосистема с открытым ключом, которая IND-CPA(атака по открытому тексту) безопасна относительно квантовых различий. Криптосистема с открытым ключом непрозрачна, если действительный открытый ключ неразличим в квантовой полиномиальной форме равномерной случайной строки той же длины.

Хотя вполне вероятно, что стандартные сокращения будут показывать, что Предположение 2 применяет Предположение 1, мы решили держать предположения отдельно, потому что экземпляра одного обычно использует генератор псевдослучайных чисел не будет связано с системой с открытым ключем(вместо этого, оно, как правило, основано на симметричном ключе блочном или поточном шифровании). Оба предположения содержат в себе, например, проблему сложности обучения с ошибками(LWE)[41]. В одной из наших конструкций (автономные ZKAoK), нам нужна схема шифрования, которая имеет еще одно дополнительное свойство, чем то, что в Предположении 2.

Предположение 3 Cуществует классическая криптосистема с открытым ключом, которая IND-CPA безопасна относительно квантовых различий. Кроме того, шифры двух сообщений по равномерной случайной строке статистически неразличимы.

Обратите внимание, что свойство непрозрачности уже подразумевает, что шифры по случайной строке квантово вычислительно неразличимы. Предположение 3 укрепляет требование статистической неразличимости. Это позволяет "обман" в том смысле, что если зашифрованный текст генерируется по равномерной случайной строке, мы можем утверждать, что это будет шифрование произвольного сообщения. Этот тип схемы шифрования иногда называется Значимым/Незначительным шифрованием (например,[42]). Опять же, предположение LWE подразумевает предположение 3.

Квантовая автономная безопасность и модульная композиция

В этом разделе мы предлагаем модель автономной безопасности для двухсторонних протоколов с присутствием квантовых атак и покажем, что в нашей модели имеет место модульная композиция. Наше определение можно рассматривать в двух направлениях: либо как квантовый аналог классической автономной модели Канетти[20] или как упрощенное понятие варианта квантовой UC безопасности Унру[13].

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

Двухсторонний протокол состоит из двух квантовых интерактивных машин и . Два игрока Алиса и Боб, которые выполняют называются доверенными, если они работают с машинами и соответственно. Злоумышленник в является объектом, который искажает какого-либо игрока и управляет его поведением. Мы считаем и полу-доверенных (также известных как доверенных, но любопытных) и вредоносных злоумышленников. В квантовой обстановке, полу-доверенный злоумышленник использует доверенный протокол когерентно, то есть, заменяет измерения и классические операции унитарными эквивалентами.

Мы будем рассматривать только статических злоумышленников, которые искажают набор игроков перед выполнением протокола , но не выполняющих дальнейшие искажения во время выполнения протокола. Для простоты изложения, мы сливаем личность злоумышленника и часть, которую он искажает. Машины под управлением злоумышленника обозначаем символом ^ (например, ).

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

Более конкретно, в реальном мире мы инициализируем и вспомогательный регистр с квантовым состоянием . Тогда и взаимодействуют, и в останавливаются в состоянии . Наконец НКМ , которую мы называем средой, принимает в качестве входа и выводит один классический бит. Абстрактно, мы рассматриваем и в совокупности, как неинтерактивную машину с пространством состояний и выходное пространство . Аналогично, для каждого злоумышленника в идеальном мире, мы можем смоделировать и как одну НКМ с пространством состояний и выходным пространством . Тогда пусть и - двоичный дистрибутив множеств выходов находится в выполнении в реальном мире и в идеальном мире идеального соответственно. См рис.1 для иллюстрации реального и идеального мира.

Рис.1 Выполнение в реальном и идеальном мирах.

Определение 3 (Квантовая автономная эмуляция безопасности). Пусть - двухсторонняя функциональность, а - двухсторонний протокол. Мы называем квантово автономно эмулирует , если для любой полиномиальной КИМ , существует полиномиальная КИМ , такая что для любой полиномиальной НКМ и для любого .

Примечание. (I) Эквивалентно, определение можно сформулировать так: для любого существует такое, что НКМ и неразличимы по определению 2 ограничиваясь до неинтерактивные машин. (II) Мы сосредоточены на вычислительной безопасности в этой работе, и модель распространяется напрямую на теоретико-информационную обстановку. (III), Мы подчеркиваем, что не только кодирует входные данные игроков, но и содержит вспомогательную систему , которая может быть связанна с входами и, кроме того служит как квантовый совет для дальнейшей помощи в различении двух миров. Есть другие возможные варианты определения, например, запрещая вспомогательную систему и только передавая классический совет, который может увеличить варианты, которые совпадают или входят в существующие модели. Смотрите полную версию для тщательного обсуждения. (IV) По техническим причинам, мы требуем, чтобы быть функциональности были хорошо сформированы и протоколы были нетривиальны, которые удовлетворяют всем функционалам и протоколам в нашей работе. (См[21], Раздел 3] для подробной информации.) Кроме того, может быть также случайной, реактивной и оценивающей квантовые схемы, хотя в этой работе мы концентрируемся на SFE классических функциях.

Модульная композиция

Обычной практикой при проектировании крупных протоколов является разбиение данной задачи на подзадачи, решение этих подзадач, а затем использование этих модулей в качестве строительных блоков(подпрограммы) в решении начальной задачи. Мы формализуем эту парадигму гибридными моделями[прим. 2]. Протокол в G-гибридной модели, обозначается имеет доступ к доверенной стороне, которая реализует идеальную функциональность G. Как и прежде, для каждого злоумышленника (индекс указывает объекты в гибридной модели) в G-гибридной модели, мы можем определить и . Тогда мы говорим, что квантово автономно эмулирует идеальную функциональность в G-гибридной модели, если для любой НКМ и всех .

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

Теорема 1 (Теорема модульной композиции) Пусть - двусторонний протокол, который квантово автономно эмулирует в G-гибридной модели и пусть - двухсторонний протокол, который квантово автономно эмулирует G. Тогда состовной протокол квантово автономно эмулирует .

Примечание. Смотрите полную версию для доказательства. Легко расширить наш анализ до более общего случая, когда может вызвать G несколько раз, а так же иметь доступ к полиномиальным идеальным функциональностям . Однако, мы подчеркиваем что в каждом цикле, может быть вызвана только одна функциональность.

Квантовые автономно-безопасные ZK аргументы знаний

Очень важный строительный блок в криптографический протоколах - Аргументы знаний нулевого разглашения(ZKAoK) для NP, сформулированные ниже как идеальная функциональность . В этом разделе мы предоставим конструкцию, которая квантово автономно эмулирует . Пусть и свидетель . Считаем, что длина свидетеля ограниченна сверху полиномом .

TemplateDifinitionIcon.svg Определение «Идеальная функциональность : доказывающий ; проверяющий ; NP-отношение »
  • При получении от проверяет . Если да, то отправляет ; иначе останавливается.

Заметьте что это действительно аргумент знаний, поскольку доказывающий явно показывает действительного свидетеля доверенной части. Пусть криптосистема как в предположении 3.

TemplateDifinitionIcon.svg Определение «ZKAoK протокол »
Фаза 1
  1. выбирает случайно и пересылает .
  2. пересылает .
  3. пересылает строку .
  4. доказывает , что действительно передача используя ZK протокол Ватроуза.
  5. и устанавливают и интерпретируют его как публичный ключ.

Фаза 2

  1. , содержащий в себе экземпляр и свидетеля , шифрует с помощью . Пусть отправляет .
  2. доказывает , что шифрует свидетеля используя ZK протокол Ватроуз. выводит , если принимает это в ZK протоколе. Иначе останавливается.

Теорема 2 Протокол квантово автономно эмулирует . Основная идея заключается в присущей мощности симулятора S в протоколе ZK Ватроуз. А именно, мы можем использовать S для создания фиктивных доказательств того, что неотличимо от реального ZK доказательства проводимого доказующим и проверяющим, когда мы не знаем свидетеля заявления, или даже когда он не один, то есть, утверждение неверно. В частности, в идеальном мире , получив истинное утверждение из , должно убедить о действительности не зная свидетеля. Мы знаем, что в реальных случаях, т.е. зашифрованный текст действительно кодирует свидетеля , S успешно имитирует доказательство по определению. Проблема сводится к генерации шифрования , не зная . Это может показаться противоречивым, но на самом деле это очень естественно. Например, предположим, что функция отображает все строки до 0, то генерация , без знания тривиально - просто вывести 0! Наша ситуация более сложна, но разделяет тот же дух. Нас интересует факт того, что шифрование под единой строкой статистически закрыто. Это означает, в частности, что шифрование любой строки под единой строкой , будут совпадать с с высокой вероятностью. Кроме того, если мы позволим играть доверенного игрока в Фазе 1, исходный гарантированно будет случайным. Это показывает, как мы обращаемся с искаженными проверяющими.

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

Классические протоколы с квантовой UC-безопасностью

В этом разделе мы исследуем классические протоколы квантовой модели универсальной компонуемости(UC). Мы предлагаем систему, простых гибридных аргументы, чтобы охватить большой класс классического анализа безопасности, который проходит через квантовых злоумышленников(при разумных вычислительных допущениях). Применяя нашу систему для классических выводов Канетти[21], мы получаем классические протоколы, которые квантово UC-безопасно реализуют двухсторонней SFE в -гибридной модели.

Универсально компонуемая (UC) безопасность, предложенная в классическом контексте Канетти[16], отличается от определения автономной безопасности тем, что окружающая среда позволяеи интерактивность: во время исполнения протокола, окружающая среда может предоставлять входные данные и получить выходные данные доверенных игроков, и обмениваться произвольными сообщениями со злоумышленником. В противоположность этому, окружающая среда, в автономной модели работает только в конце выполнения протокола (и, неявно, перед началом протокола, чтобы подготовить материалы для всех сторон). UC-безопасные протоколы обладают свойством, называемым основная(или универсальная) композиция[прим. 3](Смотрите[43][44].): грубо говоря, протокол остается в безопасности, даже если он выполняется одновременно с неограниченным числом других произвольных протоколов (в то время как доказательства безопасности в автономной модели гарантируют безопасность только при выполнении одного протокола одновременно).

Ранняя работа по определению UC безопасности и доказательство универсальной композиции в квантовой области появляется в[22][23]. Мы адаптируем простую формализацию Унру[13]. Модульное небольшое изменение в модели Унру (квантовый совет, обсуждаемый ниже), наша автономная модель - именно ограничение модели Унру для неинтерактивной окружающей среда, то есть, которая находится в режиме ожидания от начала до конца протокола.[прим. 4].

Сделаем еще одно изменение в модели Унру для того, чтобы соответствовать с нашими определениями и работой Ватроуз о нулевых знанях[7]: мы позволяем среде принять квантовый совет, а не только классический совет. Смотрите полную версию для деталей. Эта изменение определения Унру не меняет доказательства теоремы универсальной композиции:

Теорема 3 (Квантовая UC теорема композиции[[13],Теорема 11]) Пусть и - квантовые полиномиальные протоколвы. Предположим, что квантово UC эмулирует . Тогда квантово UC эмулирует .

Классические доказательства для квантовых злоумышленников: Простые гибридные аргументы

Цель этого раздела проанализировать класс протоколов, включая протокол Канетти[21] для двух- и много-сторонних вычислений(далее CLOS). Эти классические протоколы, доказали безопасность в классической UC модели. Мы покажем, что эти протоколы остаются безопасными в присутствии квантовых злоумышленников до тех пор пока лежащие в основе примитивы (генераторы псевдослучайных чисел и особые схемы шифрования с открытым ключом) являются безопасными в отношении квантовых злоумышленников. В частности, мы показываем:

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

Для доказательства теоремы 4, мы предлагаем абстракцию, которая охватывает семью классических аргументов безопасности в модели UC, которая остается в силе и в квантовом обстановке (до тех пор пока основные примитивы защищены от квантовых злоумышленников).

Мы используем термин эксперимент, чтобы описать четкую вероятность эксперимента, которая приводит либо к 0, либо 1. Аргументы, описанные здесь, могут выступать в более жесткой формализации на играх основанных на кодах[37];однако, так как эксперименты которые мы используем, в конечном счете, довольно просты, мы выбрали менее формальную экспозицию.

Мы будем использовать следующий факт о UC-безопасных протоколах, классический [[16], п.10] и квантовый [[13], лемма 10]: злоумышленник может быть воспринят как "макет" злоумышленника, который просто передает сообщения в и из окружающей среды, не проводя какую-либо обработку. Так как мы будем обсуждать только протоколы классической связи, мы можем предположить, не теряя общий смысл, что злоумышленник в наших экспериментах известен, классическая машина; в частности, вся квантовая обработка может производиться средой. Заметьте, что злоумышленники идеального мира также будут классическими. Следовательно, мы можем рассматривать процесс внешние по отношению к окружающей среде в целом, и рассмотреть его как классическую интерактивную машину . А именно, мы позволяем описывать процесс (мир,манекен-злоумышленника) или (мир,симулятор) где мир - идеальный мир, реальный мир или выполнение в гибридной модели. (Напомним, что обозначает взаимодействие между и . И само по себе является интерактивной машиной, чьи входы являются входами, ожидаемыми от и вместе с сообщениями, ожидаемыми и от других лиц. Выходы являются выходами и вместе с любыми сообщениями, отправленными ими другим субъектам). Таким образом, все эксперименты (выполнение в реальном мире, выполнение в идеальном мире с симуляторами или без, выполнение в гибридных моделях, и т.д.), мы будем анализировать в данном разделе форму , где классическая интерактивная машина, которая зависит только от описания протокола, как описано выше, а представляет собой состязательность среды.

Определение 4 (Просто связанные машины). Две КИМ и -просто связаны, если существует машина классического времени-t и пара классических дистирбутивов таких что:

  1. (для двух КИМ и , мы говорим что , если они ведут себя одинаково при всех входных данных, то есть, если они могут быть описаны одними и теми же схемами),
  2. , и
  3. .

Определение 5 (Простые гибридные аргументы). Две машины и связанны -простым гибридным аргументом длины , если существует последовательность промежуточных машин , таких что каждая смежная пара машин -просто связанны.

Лемма 1. Для любых и , если две машины связаны -простым гибридным аргументом длины , то машины - -интерактивно неразличимы.

Доказательство всех утверждений из этого раздела приведено в полной версии.

Замечание 5 (структура CLOS доказательства) За исключением доказательства безопасности протокола передачи от полу-доверенных вредоносных злоумышленников, все доказательства безопасности для статических злоумышленников в CLOS состоят либо из (а) простые гибридные аргументы с и , или (б) применении теоремы UC композиции.

Кроме того, основа неразличимых распределений в аргументах CLOS состоит или из (I) переключеня между реальным открытым ключом и равномерной случайной строкой, (II) изменение открытого текста шифра, или (III) изменение сообщения в фазе передачи протокола передачи.

Из этого замечания, мы получаем следствие ниже, где обозначает функцию "передачи-и-доказательства" Канетти[[21],рисунок 8].

Следствие 6 (CLOS - простые гибриды) По предположениям 1 и 2,

  1. В -гибридной модели, существует нетривиальный протокол, который UC эмулирует в присутствии полиномиальных вредоносных статических квантовых злоумышленников.
  2. Пусть хорошо сформированная двухсторонняя функциональность. В простой модели, существует протокол, который UC эмулирует в присутствии полиномиальных полу-доверенных статических квантовых злоумышленников.

Осталось обсудить доказательство безопасности компилятора полу-доверенных вредоносных злоумышленников в модели . Структура доказательства лишь немного отличается от гибридных доказательств выше. Пусть протокол, предназначенный для полу-доверенной модели и пусть результат применения компилятора CLOS к , для получения протокола в (вредоносной) -гибридной модели.Мы использовать следующий вывод Канетти[21]:

Предположение 7 (Канетти[21], предположение 8.1]) Пусть - любой реальный протокол, предназначенный для полу-доверенной модели. Для каждого классического злоумышленника , существует классический полиномиальный злоумышленник такой, что взаимодействие с доверенными игроками, используя в -гибридной модели идентична взаимодействию с в полу-доверенной модели; то есть, .

Комбинируя предыдущее предположение с простыми аргументами CLOS(Следствие 6,выше) мы можем доказать Теорему 4. Смотрите полную версию для детального описания.

Эквивалентность между и Эквивалентность между G Z K {\displaystyle G {ZK}} и G C F {\displaystyle G {CF}}

В этом разделе мы сделаем набросок UC эквивалентности между нулевым знанием и переворотом монетки в квантовой области. Тот факт, что переворот монетки может быть реализован в гибридной модели следует из общего вывода CLOS, рассмотренного в предыдущем разделе. В полной версии, мы даем прямую конструкцию переворота монетки из ZK соображений параллельного протокола переворота монетки Линделла[17]. Прямая конструкция опирается только на предположение о квантовой безопасной PRG. Мы приведем конструкцию в -гибридной модели, которая сопротивляется атакам квантовых злоумышленников.

Предположение 8

  1. По предположению 1, существует зацикленный протокол , который квантово UC эмулирует в -гибридной модели.
  2. По предположениям 1 и 2, существует зацикленный протокол , который квантово UC эмулирует в -гибридной модели.

Это означает, что в автономная модель достаточно построить безопасный (моделируемый) протокол переворота монетки, чтобы получить безопасные протоколы SFE для произвольных функций. Это дает другое средство построения безопасных протоколов, которые могли бы производить протоколы, которые полагаются на предположения меньше (или несравнимо) с теми, что мы используем в нашей работе, или те, что используют меньшее количество циклов. Связанная работа Лунемана и Нильсена[19] начинается с построения протокола переворота монетки, а не ZKAoK, хотя они полагаются на предположения очень похожие на наши, и имеют аналогичную циклическую сложность.

Наш протокол использует стандартное преобразование, для получения ZKAoK из свидетельно-неразличимой(WI) системы доказательств в CRS модели. Основной технический шаг в нашем анализе показывает,что 3-цикловой ZK протокол Блюма для гамильтонова цикла, на самом деле, является WI против вредоносных квантовых злоумышленников. Наше доказательство избегает перемотки и напоминает доказательства того, что некоторые протоколы WI могут быть параллельны. Детали можно найти в полной версии.

Применение и обсуждения

Для начала обобщим результаты, которые мы получили и получим пару простых но важных следствий о двухсторонней SFE в присутствии квантовых атак.

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

Применяя теорему модульной композиции в автономной модели к пунктам 1 и 3 мы имеем:

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

Заметьте, что пункт 2 немедленно применяет эквивалентность и в квантовой автономной модели. Совмещая с пунктом 3 получаем:

Следствие 10 Существует классический протокол , который квантово автономно эмулирует без предустановленных допущений.

Обсуждение. Наша работа предполагает ряд простых гипотез. Например, вполне вероятно, что наши методы на самом деле применяется для всех результатов в CLOS (многопартийность, адаптивные злоумышленники), а также соответствующие результаты в «обобщенной» модели UC[45]. Практически все протоколы в полу-доверенной модели вписывается в рамки простых гибридов, в частности протоколов, основанных на искаженныех схемах Яо(например,[46]). Также вероятно, что существующие доказательства в модели безопасности, которые позволяют супер-полиномиальное моделирование (например, [47][48][49]) будут осуществляться с помощью аналогичной линии аргументов.

Тем не менее, наша работа оставляет открытыми некоторые основные вопросы: например, можем ли мы построить зацикленный ZK с незначительной полнотой и состоятельности ошибок против квантовых проверяющих? Техника Ватроуз не сразу отвечает на это, так как последовательное повторения необходимо в его конструкции, для уменьшения ошибки устойчивости. Беглый взгляд на классическую зацикленную ZK(например,[50]) предполагает, что свидетеле-неотличимые доказательства знаний полезны. Можно ли построить зацикленные свидетеле-расширяемые WI доказательства знаний? Применим ли наш анализ в UC системе, такой как основная система UC Канетти[45]? Наконец, в более общем смысле, какие другие виды использования перемотки могут быть адаптированы к квантовым злоумышленникам? Помимо оригинальных работ Ватроуз[7], Дамгарда и Лунемана[8] и Унру[18] показаных примеров такой адаптации.

Контакты авторов материала

  1. Partially supported by National Science Foundation award CCF-0747274 and by the National Security Agency (NSA) under Army Research Office (ARO) contract number W911NF-08-1-0298.
  2. Partially supported by National Science Foundation award CCF-0747294

Примечания

  1. В общем, трудно четко определить, что означает "не использовать перемотку" для доказательства безопасности. Этого не достаточно для того, чтобы иметь протокол прямолинейного моделирования, так как доказательства правильности моделирования все еще может использовать перемотку. Простые гибридные аргументы обеспечивают чистый, безопасный подкласс аргументов, которые проходят через квантовых злоумышленников.
  2. В отличие от этого, мы называем это простой моделью если в ней нет надежных участников и нет доверенных настроек допущений таких, как общяя строка ссылок или инфраструктура с открытым ключом и т.д.
  3. Существует различие между UC безопасностью (определение, которое может быть выполнено с помощью специального протокола и идеальной функциональности) и универсальной композицией (свойство класса протоколов, которые удовлетворяют определению безопасности). Не все определения, которые допускают теорему универсальных композиций эквивалентны UC безопасности.
  4. Единственное явное различие в моделях в том, что в модели UC, окружающая среда работает в течение некоторого времени, прежде чем протокол начинает готовить входы, в то время как в разделе 3.1 мы просто проходим над всеми совместными состояниями с доверенных игроков и входов злоумышленника и дополнительного входа W к различителю.

Литература

  1. 1,0 1,1 O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In STOC, pages 218–229. ACM, 1987.
  2. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18:186–208, 1989.
  3. O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity for all languages in np have zero-knowledge proof systems. J. ACM, 38(3):691–729, 1991.
  4. P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997.
  5. S. Hallgren. Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. J. ACM, 54(1):1–19, 2007.
  6. C. Cr´epeau, L. Salvail, J.-R. Simard, and A. Tapp. Classical and quantum strategies for twoprover bit commitments. In Quantum Information Processing (QIP), 2006. Online available at http://crypto.cs.mcgill.ca/˜crepeau/PDF/CSST06.pdf.
  7. 7,0 7,1 7,2 7,3 7,4 J. Watrous. Zero-knowledge against quantum attacks. SIAM J. Comput., 39(1):25–58, 2009. Preliminary version in STOC 2006.
  8. 8,0 8,1 I. Damg°ard and C. Lunemann. Quantum-secure coin-flipping and applications. In ASIACRYPT, pages 52–69. Springer, 2009.
  9. S. Hallgren, A. Kolla, P. Sen, and S. Zhang. Making classical honest verifier zero knowledge protocols secure against quantum attacks. In ICALP, pages 592–603. Springer, 2008.
  10. 10,0 10,1 C. Cr´epeau, D. Gottesman, and A. Smith. Secure multi-party quantum computation. In STOC, pages 643–652. ACM, 2002.
  11. 11,0 11,1 11,2 M. Ben-Or, C. Cr´epeau, D. Gottesman, A. Hassidim, and A. Smith. Secure multiparty quantum computation with (only) a strict honest majority. In FOCS, pages 249–260. IEEE, 2006.
  12. 12,0 12,1 12,2 S. Fehr and C. Schaffner. Composing quantum protocols in a classical environment. In TCC, pages 350–367. Springer, 2009.
  13. 13,0 13,1 13,2 13,3 13,4 13,5 13,6 13,7 13,8 D. Unruh. Universally composable quantum multi-party computation. In EUROCRYPT, pages 486–505. Springer, 2010. arXiv:0910.2912v1.
  14. 14,0 14,1 C. Cr´epeau, P. Dumais, D. Mayers, and L. Salvail. Computational collapse of quantum state with application to oblivious transfer. In TCC, pages 374–393. Springer, 2004.
  15. 15,0 15,1 15,2 I. Damg°ard, S. Fehr, C. Lunemann, L. Salvail, and C. Schaffner. Improving the security of quantum protocols via commit-and-open. In CRYPTO, pages 408–427. Springer, 2009. Full version at arXiv:0902.3918v4.
  16. 16,0 16,1 16,2 16,3 R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In FOCS, pages 136–145. IEEE, 2001.
  17. 17,0 17,1 17,2 Y. Lindell. Parallel coin-tossing and constant-round secure two-party computation. J. Cryptology, 16(3):143–184, 2003.
  18. 18,0 18,1 D. Unruh. Quantum proofs of knowledge, April 2010. IACR ePrint 2010/212.
  19. 19,0 19,1 19,2 19,3 19,4 C. Lunemann and J. B. Nielsen. Fully simulatable quantum-secure coin-flipping and applications. In Africacrypt, February 2011. arXiv:1102.0887.
  20. 20,0 20,1 R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143–202, 2000.
  21. 21,0 21,1 21,2 21,3 21,4 21,5 21,6 R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In STOC, pages 494–503. ACM, 2002.
  22. 22,0 22,1 M. Ben-Or and D. Mayers. General security definition and composability for quantum and classical protocols, September 2004. arxiv:quant-ph/0409062v2.
  23. 23,0 23,1 D. Unruh. Simulatable security for quantum protocols, 2004. arXiv:quant-ph/0409125v2.
  24. M. Ben-Or, M. Horodecki, D. W. Leung, D. Mayers, and J. Oppenheim. The universal composable security of quantum key distribution. In TCC, pages 386–406. Springer, 2005.
  25. 25,0 25,1 D. Mayers. Unconditional security in quantum cryptography. J. ACM, 48(3):351–406, 2001.
  26. H.-K. Lo and H. F. Chau. Unconditional security of quantum key distribution over arbitrarily long distances. Science, 283(5410):2050–2056, 1999.
  27. P. W. Shor and J. Preskill. Simple proof of security of the BB84 quantum key distribution protocol. Phys. Rev. Lett., 85(2):441–444, Jul 2000.
  28. D. Beaver. On deniability in quantum key exchange. In EUROCRYPT, pages 352–367. Springer, 2002.
  29. G. Brassard and C. Cr´epeau. Quantum bit commitment and coin tossing protocols. In CRYPTO, pages 49–61. Springer, 1990.
  30. C. H. Bennett, G. Brassard, C. Cr´epeau, and M.-H. Skubiszewska. Practical quantum oblivious transfer. In CRYPTO, pages 351–366. Springer, 1991.
  31. P. Dumais, D. Mayers, and L. Salvail. Perfectly concealing quantum bit commitment from any quantum one-way permutation. In EUROCRYPT, pages 300–315. Springer, 2000.
  32. C. Cr´epeau, D. Gottesman, and A. Smith. Approximate quantum error-correcting codes and secret sharing schemes. In EUROCRYPT, pages 285–301. Springer, 2005.
  33. I. Damg°ard, S. Fehr, L. Salvail, and C. Schaffner. Cryptography in the bounded-quantumstorage model. SIAM J. Comput., 37(6):1865–1890, 2008.
  34. I. Damg°ard, S. Fehr, L. Salvail, and C. Schaffner. Secure identification and qkd in the bounded-quantum-storage model. In CRYPTO, pages 342–359. Springer, 2007.
  35. D. Unruh. Concurrent composition in the bounded quantum storage model. In EUROCRYPT, pages 467–486. Springer, 2011.
  36. E. Kushilevitz, Y. Lindell, and T. Rabin. Information-theoretically secure protocols and security under composition. SIAM J. Comput., 39(5):2090–2112, 2010.
  37. 37,0 37,1 M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In EUROCRYPT, pages 409–426. Springer, 2006.
  38. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
  39. A. C.-C. Yao. Quantum circuit complexity. In FOCS, pages 352–361. IEEE, 1993.
  40. M. Naor. Bit commitment using pseudorandomness. J. Cryptology, 4(2):151–158, 1991.
  41. O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Preliminary version in STOC 2005.
  42. G. Kol and M. Naor. Games for exchanging information. In STOC, pages 423–432. ACM, 2008.
  43. D. Hofheinz and D. Unruh. Simulatable security and polynomially bounded concurrent composability. In Symposium on Security and Privacy, pages 169–183. IEEE, 2006.
  44. Y. Lindell. General composition and universal composability in secure multiparty computation. J. Cryptology, 22(3):395–428, 2009.
  45. 45,0 45,1 R. Canetti, Y. Dodis, R. Pass, and S. Walfish. Universally composable security with global setup. In TCC, pages 61–85. Springer, 2007.
  46. D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols. In STOC, pages 503–513. ACM, 1990.
  47. R. Pass. Simulation in quasi-polynomial time, and its application to protocol composition. In EUROCRYPT, pages 160–176. Springer, 2003.
  48. M. Prabhakaran and A. Sahai. New notions of security: achieving universal composability without trusted setup. In STOC, pages 242–251. ACM, 2004.
  49. B. Barak and A. Sahai. How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In FOCS, pages 543–552. IEEE, 2005.
  50. U. Feige and A. Shamir. Zero knowledge proofs of knowledge in two rounds. In CRYPTO, pages 526–544. Springer, 1990.