Одновременная композиция в модели ограниченного квантового хранения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:40, 13 декабря 2015.
Concurrent composition in the bounded quantum storage model
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Авторы Dominique Unruh
Опубликован 2010 г.
Сайт []
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать [ оригинал]

__NUMBEREDHEADINGS__

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


Ключевые слова: Ограниченное квантовое хранилище, компонуемость, двух-партийное вычисление.

Введение

С момента создания квантового распределения ключей Беннетта и Брассарда [1], было известно, что квантовая коммуникация позволяет добиться протокола задач, который невозможно предоставить только классическим каналом. К примеру, схема [1] распределения квантовых ключей позволяет договорится о секретном ключе, который статистически секретен, используя только аутентификацию, но не секретный канал. (Под статистически безопасным мы имеем ввиду защиту против противников неограниченных вычислительно, также известных как информационно-теоритическая безопасность.) В противоположность этому, при использовании только классической связи, легко увидеть, что такой секретный ключ всегда может быть извлечен вычислительно достаточно мощным противником. В свете этого результата, можно надеяться, что квантовая криптография позволяет обойти другие классические невозможные результаты, возможно даже с учетом статистически безопасных многопартийных протоколов вычислений. Еще, Майерс [2] показал, что в квантовой настройке, даже статистически безопасные схемы невозможны, не говоря уже об основном многопартийном вычислении. Это печально, потому что из схемы обязательств можно построить OT (Bennett, Brassard, Crépeau, and Skubiszewska [3]), и от ОТ основное многопартийное вычисление (Kilian [4]). Способ обойти эту неосуществимость был найден Damgård, Fehr, Salvail, and Schaffner [5]. Они показали что если мы предположим, что квантовая память доступна для противника ограниченна (мы говорим о BQS), мы можем построить статистически безопасную передачу и ОТ схему. Хотя такой результат не является подлинно безусловным, он позволяет избежать тяжелого для оправдания комплексно-теоритического допущения. Кроме того, достигается долгосрочная безопасность: даже если противник может превзойти связывание памяти после извлечения протокола, это не позволит ему взломать протокол задним числом.

Тем не менее, мы еще не достигли цели, статистически безопасного многопартийного вычисления. Хотя у нас есть протоколы обязательств и ОТ, мы не можем просто подключите их к протоколам Bennett [3] и соавт. и Kilian [4]. Причина в том, что пока не ясно, при каких обстоятельствах протоколы в BQS модели могут быть составлены. К примеру, Dziembowski и Maurer [6] построили протокол, который является безопасным в классической ограниченной модели хранения, но теряет безопасность в композиции с вычислительно безопасным протоколом. Чтобы преодолеть эту трудность остальные, произведения Wehner и Wullschleger [7] и by Fehr and Schaffner [8] дают определения безопасности в BQS модели, обеспечивающие безопасность последовательной композиции. Обе работы также представляют безопасные OT протоколы в их соответствующих настройках. Основываясь на этом мы можем построить безопасные многопартийные вычислительные протоколы в BSQ модели. Есть, однако, несколько ограничений. Во-первых, потому что только последовательная композиция поддерживается, все экземпляры OT протокола используются многопартийным вычислением должны быть выполнены один за другим, приводит к высокой круговой сложности. Во-вторых, интерактивные функции, такие как обязанность трудно использовать: ограничение на последовательное вычисление требует, что мы должны совершить, и тут же открыть обязательства перед будет разрешено выполнять следующие обязательства. В-третьих, безопасность доказательство их OT протоколов использует вычислительно неограниченный симулятор. Как отмечалось в [9], протокол с неограниченным симулятором не может быть составлен с вычислительно защищенным протоколом. В-четвертых, поскольку у нас нет одновременных вычислений, это не ясно, что произойдет, если протоколы выполняются в среде, где мы не имеем полного контроля, о протоколах которые выполняются во время.

Для преодоления ограничений последовательной композиции в классической постановке, Канетти [10] ввел модель Универсальной компонуемости (UC). В этой модели протоколы могут быть сколь угодно составлены, даже одновременно с другими протоколами и копии самих себя. Модель UC была адаптирована к квантовой настройке, Бен-Ор и Майерс [11] и Унру [12] [9]. В свете успеха модели UC, кажется естественным, объедининение идеи модели UC с BQS моделью для того, чтобы обеспечить одновременные композиции.

Наш вклад

Мы определяем понятие BQS-UC-безопасность, которое является расширением квантовой-UC-безопасности [9]. Мы обладаем компонуемостью в следующем смысле: Если это безопасная реализация функциональности , и безопасно реализует с использованием одного образца , тогда , результат замены на , до сих пор надежно реализует . В отличие от квантовой-UC-безопасности, однако, BQS-UC-безопасность не допускает одновременного самостоятельного состава: если безопасна, это автоматически не означает что оба образца безопасны [прим. 1].

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

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

Наконец, используя теорему композиции и , для любой двух-партийной функциональности , мы получаем a статистически защищенный протокол реализующий в BQS модели [прим. 2]. Протокол защищен даже кода запущено одновременных образцов протокола. Протокол постоянной всесторонней. Он не использует любой квантовой памяти или квантовых вычислений и, следовательно, находится в недоступном для современных технологий.

Полная версия этого документа с доказательствами и деталями может быть найдена в [13].

Ограниченное квантовое хранилище UC

Модель BQS-UC (Ограниченное квантовое хранилище UC)

Для понимания определения BQS-UC-безопасность, мы сначала поймем идею лежащей в основе UC безопасности. В UC модели, протокол эмулирует другой протокол если любая атака на также может случится и с . Таким образом, если защищен по определению (потому что он содержит только одну доверенную машину, так называемую идеальную функциональность), также должен быть защищен. Чтобы формализовать это, мы введем концепт противника и симулятора. Нам необходимо это для любого противника атакующего , симулятора атакующего (идеальная модель) в связи с этим реальная и идеальная модели неразличимы. Для определения неразличимости, мы вводим другую машину, окружение. Её задача старатся найти отличия между реальной и идеальной моделями. Окружение обеспечивает входы в протокольные группы, получает их выходы, и может говорить с противником\симулятором. После этого мы получим следующее определение: UC-эмуляции если для любого противника есть симулятор такой что для любого окружения , вероятность того что выход 1 это приблизительно тоже самое в сетях и .

Для перехода к квантовой настройке, нам необходимо только изменить модель машины, чтобы позволить квантовую машину вместо классических машин. Данные сети , квантовых машин с , , мы утверждаем что и -близки если где вероятность выходов 1 в исполнении , и определенны аналогично. Сети незначительно близки если незначительно мало, и совершенно близко если . Мы называемм машиной a-память связной, если она держит не более кубитов квантовой памяти между активациями. Мы не налагаем никаких ограничений на вычислительное время или использование памяти во время единичной активации . Мы пишем для временной связи с (т.е., мало как M).Протокол сеть не содержащая противника, симулятор, или окружение. Установка устаревших групп протокола обозначается группами . Данная , мы обозначаем протокол где все группы в переставлены испорченными группами которые контролируются противником. Для подробностей на машине и в сетевой модели, мы ссылаемся на полную версию [9] или к [13].

Мы сейчас можем сформулировать BQS-UC-безопасность. Для формулирования этого, нам необходимо явно параметризовать определение связанной памяти а. Далее мы рекомендуем что полное квантовое использование памяти окружением и портивником связанно . Причина почему мы включили память окружения, то что последние могут быть вовлечены в реальные атаки: Если только память противника будет ограниченна, противник может использовать окружение как внешнее хранилище для создания атаки (смотри также рассуждение на странице 471 [прим. 3]).


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

Определение 1 (BQS-UC-безопасность) Исправить протоколы и . Возмем (зависит от параметров безопасности). Мы говорим - BQS-UC-эмулирует [прим. 4] для каждой установленной и для любого противника есть симулятор с для каждого окружения с (называется идеальной моделью ) незначительно близко. Кроме того, мы требуем, что если является квантово-полиномиальный по времени, то это .


В большинстве случаев поведение идеального протокола описывается одной машиной , так называемая идеальная функциональность. Мы можем думать об этом функциональности в качестве доверенной третьей стороны, которая идеально реализует нужный протокол поведения. Для того чтобы применить определение 1 к идеальной функциональности (например, BQS-UC-эмулирует ) мы должны иметь возможность рассматривать идеальную функциональность протокола. Следующий [10] [9], мы делаем это путем введения фиктивных сторонам. То есть, протокол содержит функциональные возможности вместе с манекеном стороной для каждой партии . Манекен-сторона только вперед входы / выходы между функциональностью и окружающей среды. Они, однако, могут быть повреждены противником / симулятором. Это позволяет противнику / симулятору для контроля входа / выхода из этой партии. Когда мы пишем BQS-UC-эмулирует , мы всегда будем предполагать наличие dummyparties В идеальной модели. Для получения дополнительной информации мы обращаемся к полной версии [13] или [9].

Ограниченная память окружения. В определении 1, положим память связана с обеими противниками и окружающей среды. В этом мы отличаемся от моделирования Венер и Wullschleger [7]. По их определению, окружающую среду (которая подразумевается в определении неразличимости квантовых каналов) обеспечивает ввод государства протокола и противник, затем получает выходы протокол и противника, и, наконец, среда должен гадать, относится ли он взаимодействует с реальной или идеальной модели. Во время взаимодействие протокола, окружающей среде не позволено общаться с любой другой машиной. Между двумя активациями, охрана окружающей среды имеет право держать сколь угодно больших квантовых состояний[прим. 5]. Интересным моментом здесь является то, что в отличие от наших определений 1, Венер и Wullschleger не навязывают памяти ограничение на окружающую среду, только на противника. Они мотивируют неограниченное средах, указывая на то, что это более реалистично предположить, что особенности память оценка (скажем, 100 кубитов) относится к определенному противнику (например, смарт-карты), чем на всю окружающую среду (то есть, все компьютеры по всему миру). Мы считаем, однако, что это рассуждение должно применяться с осторожностью: только когда у нас есть гарантии того, что противник (например, смарт-карта) не могут общаться с любой другой машины можно предположить, смарт-карта не должна превышать 100 кубитов. В противном случае, мы должны предположить, что смарт-карты фактически имеет (в худшем случае) доступ ко всем квантовой памяти окружающей среды. Таким образом, за исключением очень конкретных случаях, память связана предположить, должно быть достаточно большим, чтобы охватывают памяти среды в целом. Таким образом, связаны предположить, не быть превзойден памяти противника должна быть достаточно большой, что он Логично предположить, что окружающая среда не превышает эту границу либо. Но в данном случае, мы можем с уверенностью предположить, в определении 1, что окружающая среда ограничены, что память связана.

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

Мы получаем, однако, интересный вариант нашей модели, если мы будем следовать подходу из Венер и Wullschleger следующим образом. Мы называем машину памяти-ограниченного [прим. 6], если его состояние между активации состоит из двух регистров и . Регистрации содержит не более кубитов, и зарегистрировать не ограничено, но только доступ первый и последний активация В. Обозначим через -памятиграница Z. Определим (BQS-UC-эмуляцию как (, з)-BQS-UC-эмуляции (Определение 1), за исключением того, что мы используем , а не . (Но мы все еще используем QM (Adv) и КМ (Sim).) Мы подчеркиваем, что наши методы работают для этого определение. Все результаты этого параграфа остаются в силе с практически неизмененной доказательств (кроме того, что мы всегда должны обращаться к памяти связаны окружающей среды вместо того, чтобы память оценка).Результаты Раздел 3 (BQS-UC обязательств) основаны на существование определенных схем обязательства, которые скрываются с по отношению к памяти ограниченной противников. Мы используем приверженность схемы из [14] (см. теорему 6). Чтобы расширить результаты раздела 3 до BQS-UC, мы необходимости схемы, которые прячутся по отношению к памяти ограниченной противников вместо этого. Кроме того, доказательства результатов в разделе 3 лет по существу же (за исключением использования памяти границ, а не памяти границ).

Композиция

Для протокола , а некоторые протокол , по обозначим протокол, в котором вызывает (до полиномиально много) экземпляров . То есть, в машин от и от работать вместе в одной сети, а машины из доступа Входы и выходы . (То есть, играет роль окружающей среды от точки зрения . В частности, , то переговоры только и не под протокол напрямую). типичной ситуации будет то, что некоторые протокол, который использует некоторый идеал F функциональность, скажем приверженность функциональности и Затем бы протокол в результате реализации этой функциональности с некоторыми протокол , скажем приверженность протоколу. Можно было бы надеяться, что такие Итоги реализации в безопасный протокол . То есть, мы надеемся, что если BQS-UC-F и эмулирует BQS-UC-эмулирует , то BQS-UC-эмулирует . К счастью, дело обстоит именно так, до тех пор, как мы выбираем память границы в правильном направлении:

Теорема 2 (Теорема Композиции) Пусть квантово-полиномиальными временными протоколыми и и будут квантово-полиномиальными по времени функциями. Предположим, что вызывает не более одного под протокола мнгновенно. Предположим, что -BQS-UC эмулирует и что -BQS-UC-эмулирует . Тогда -BQS-UC-эмулирует .


Доказательство этой теоремы очень похоже, что в [15], за исключением того, что мы должны отслеживать квантовой памяти, используемой различными машинами построеных в доказательстве.


Обратите внимание, что в этой теореме о композиции, внешний протокол допускается только для вызова одного экземпляра подпротокол . Это резко контрастирует с универсальной теоремы композиции для классического UC [4] и для квантово-UC [15], где любой полиномиально-ограниченного числа одновременных экземпляров не допускается. На самом деле, это не просто ограничение техники нашего доказательства. Например, предположим, что протокол (a,s)-BQS-UC-эмулирует приверженность функциональность с отправителем A и получателем B. Предположим далее, что не использует функциональные как настройка. Как мы увидим далее, такой протокол существует. Теперь быть протокол, результаты обмена ролями A и B. Тогда (a, s)-BQS-UC-эмулирует . Рассмотрим параллельный состав и . В этом протоколе поврежден Боб может перенаправить все сообщения между Алиса в первый протокол и Алиса в стране второй протокол. Таким образом, если Алиса обязуется случайных V значение в первом протоколе, Боб обязуется же V значение во втором протоколе, не зная об этом. Легко видеть, что в одновременных состав и , это невозможно. Таким образом, состав и не -BQS-UC-эмулировать состав и (для каких-либо параметров ). Чтобы преобразовать его в пример протокола, который даже не составляют с самим собой, просто рассмотреть протокол , в котором Боб может выбрать, будет ли или должен быть исполнен. Можно было бы сделать самостоятельно компонуемых, добавляя подходящие теги в сообщениях, но определение BQS-UC-безопасности не требует этого.

Хотя BQS-UC-безопасность не гарантируется для одновременной самокомпонуемости, отдельные протоколы могут обладать этим свойством. Для того чтобы сформулировать это, мы вводим понятие мульти-сессии вариант протокола. Учитывая протокол и полиномиально-ограниченным , определим тгп будет протокол, который выполняет экземпляров одновременно.

Тогда из теоремы 2, мы сразу получаем следующее следствие:

Следствие 3. Допустим и будут квантово-полиномиальными протоколами и и будут квантово-полиномиальными по времени функциями. Пусть целые числа (в зависимости от параметров безопасности). Предположим, что вызывает не более чем экземпляров подпротокола. Предположим, что -BQS-UC-эмулирует и что -BQS-UC-эмулирует . Тогда - BQS-UC-эмулирует .

Обязательства

Испoлняемые обязательства

В этом разделе мы приводим понятие интернет-извлекаемые обязательств в модели BQS. Они будут использованы в качестве строительных блоков для построения BQS-UC обязательств в следующем разделе.

Определение 4 ( -BQS-скрытие Учитывая приверженность протоколу с отправителем Алисой и получателем Бобом, и противник искажающий Боба, мы обозначим выход в взаимодействия между Алисой и , где Алиса обязуется . Мы называем -BQS-скрытие, если для всех a-памяти ограниченное , и все мы получаем, что . Здесь сообщения схемы обязательств.


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

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


Теорема 6 (онлайн-извлекаемые обязательства) Для любого полиномиально ограниченного целого и есть постоянная всесторонняя 0-память ограниченная -BQS скрытие -онлайн-извлекаемые приверженность схеме для некоторых экспоненциально малый и некоторые полиномиально-ограниченного . Сообщение пространства это .


Протокол со свойствами из теоремы 6 был построен в [12]. Они, однако, не показывают, он онлайн-извлекаем. В полной версии [16] мы показываем, как их доказательство обязательным собственности может быть распространено на онлайн-экстрагируемость.

BQS-UC Обязательства

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

Определение 7 (Обязательство). Пусть А и В две стороны. Функциональность ведет себя следующим образом: после (первого) входа с из A, хранить и отправлять . После (первый) вход открыт с отправки , к B (х, если до сих пор не определено). Все коммуникации / ввода / вывода является классическим. Мы называем отправителя и получателя .

Обратите внимание, что это определение также определяется поведением функции в случае, когда А и В повреждены. В этом случае противнику (или симулятору) разрешается отправлять / получать входы / выходы на имя или В, соответственно. Например, если А повреждена, противник может решить, когда взять на себя обязательство, какое сообщение и когда открывать.

Интуиция. Протокол изображен на рисунке 1. Прежде чем доказывать свою безопасность, мы сначала объяснить, лежащий в основе интуиции. Для того чтобы доказать BQS-UCsecurity из , необходимо построить тренажер (которые могут использовать больше памяти, чем квантовая противника), что позволяет достичь следующего: Находясь в роли получателя, симулятор в состоянии извлекать обязательства после фаза фиксации. Находясь в роли отправителя, симулятор должен быть в состоянии открыть приверженность любое значение по своему выбору (неопределенность). Первое требование, могут быть легко достигнуты с помощью онлайн-извлекаемые приверженность схему из теоремы 6. Это схема, однако, не является двусмысленным. Для того чтобы сделать наш протокол двусмысленным, мы намеренно ослабить обязательным свойством обязательства. Вместо привязки к одному значению , отправитель совершает использованием приверженности схеме случайные значения . Затем он отправляет с является универсальным хэш-функции и отправляет синдром от по отношению к подходящим линейным кодом. В открытую фазу, отправитель не открывает все обязательства, , но вместо этого просто посылает R получателю. Получатель выбирает набор тестов T, и отправитель открывает для для . Изменение схемы по-прежнему обязательным: Предположим, что отправитель хочет быть в состоянии открыть обязательства с двумя разными значениями. Затем он должен найти значения , что и передать получателям чеков в открытую фазу. Если отличается от во многих


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

Фаза фиксации:

С1. Боб выбирает случайное с . Затем Боб фиксирует использованием C1. (Мы считаем, некоторые кодирования Т множеств, не позволяет кодировать наборы с .)

C2. Алиса выбирает Для каждого Алиса фиксирует используя C2. (Обязательства могут быть выполнены одновременно.)

C3. Алиса выбирает хэш-функцию , вычисляет , вычисляет синдром , и посылает Бобу. (Это может быть сделано одновременно с обязательствами по ).

C4. Выходы Боба

Открытая фаза:

O1. Алиса посылает Бобу.

O2. Боб открывает T используя

O3. Для любого Алиса открывает используя (Открытой фазы могут выполняться одновременно.)

O4. Боб проверяет, что значения присланные Алисой соответствуют значениям открытыми Алисой для всех , и что .

O5. Боб вычисляет и выходы . (То есть, Боб принимает открытое значение .)

Рис 1. Наш обязательный протокол


блоках , с высокой вероятностью верификатор будет требовать, чтобы один из этих открылся и отправитель будет пойман. Если и отличается только несколько блоков, то имеет низкий вес Хэмминга и не в коде. Следовательно, синдром не равен нулю, и, поскольку код является линейным, синдромы и может не равные . Таким образом отправителя поймали, тоже. Кроме того, наша схема онлайн-извлекаема если онлайн-извлекаемые с симулятором может извлекать совершенные значения . Однако, мы еще не достигли неопределенность. Для того чтобы открыть приверженность другое значение, отправителю необходимо знать , прежде чем отправить . Чтобы добиться этого, получатель фиксирует до фазы фиксации (с помощью онлайн-извлекаемые приверженность схеме). Симулятор, желающий изменить значение приверженности просто извлекает . Затем он знает, какие может быть изменено без обнаружения и может таким образом изменить в любое значение, которое он желает.


Трудности с Параллельная композицией. Основная трудность в показе BQC-UC-безопасности заключается в борьбе с тем, что ряд (скажем ) экземпляров могут работать одновременно. Рассмотрим для примера случай, что Алиса поврежден. В этом случае противник может привести к -обязательства по в экземпляров Алисы. Тренажер должен работать экстракторы для извлечения этих обязательств. Каждый из этих экстракторов нуждается в некоторой квантовой памяти . Таким образом, наш симулятор потребности бита квантовой памяти. С другой стороны, мы должны убедиться, что C1-обязательства по T, выпускаемые симулятор, прячутся. необходимо скрывать от a1-ограниченным противников с (поскольку мы не можем быть уверены, что память, используемая симулятор не злоупотребляют противника). Но тогда экстрактор для должен использовать кубитов, в противном случае противник может работать экстрактор нарушить протокол. Точно так же мы можем видеть, что, когда Боб поврежден, необходимо скрывать от -памяти ограниченное противников с и . Таким образом нам нужно что невозможно.

Решение трудности. Выход в том, чтобы тщательно отслеживать памяти, используемой тренажеров; оказывается, что в доказательстве защиты от повреждения Алиса, мы можем убедиться, что противник не в состоянии "злоупотребление" память тренажера. Когда Алиса поврежден, нам нужно построить тренажер, который извлекает значения одновременных обязательств производится Алисой, в то время как быть неотличимы от исполнения честным получателя Боб. Точнее, мы показываем, что тренажер неразличим, если -BQS скрытие и это -онлайн-экстрагируемых и окружающей среды и противником являются -memorybounded. Мы не требуем, что , тем самым прорвав вышеупомянутый круг в выборе .

Зададим определить, как честный Боб, за исключением того, что вместо того, чтобы честно работающий код получатель для - работает исполнитель для извлекать совершенные значения в -обязательств. От вычисляет догадаться за совершенные значения . нет, однако, использовать эту догадку в любой момент.

Во-первых, обратите внимание, что - ничем не отличается от честного Боб: Это следует из того, что экстрактор для ничем не отличается от получателя. Кроме того, как обсуждалось в разделе Интуиция выше, извлечение будет успешным до тех пор, как Алиса не узнает что-нибудь о Т, т. е. до тех пор, как скрывается. Но C1 только a1-BQS-скрываться. И использует кубитов, чтобы запустить экстракторы для , так что общий объем памяти, используемых в сети , что за пределами памяти связаны переносится . К счастью, однако, честный Боб работает получатель после окончания фаза фиксации и до начала открытой фазы . Таким образом, с точки зрения , экстракторы выполняются в одной атомной вычислений. И мы определили BQS-укрытий, чтобы провести, даже если противник использует неограниченным объемом памяти в пределах одной активации. Таким образом кубитов используется экстракторы не ломаются скрывает имущество, и мы получаем, что догадки правильного с подавляющей вероятностью.

Этот аргумент, однако, работают только при одном экземпляре выполняется. Если несколько экземпляров выполняются один экземпляр может работать совершения или открытую фазу одновременно с экстракторы другого экземпляра. Две вещи показывают, что одновременных экземпляров Экстракт успешно, мы используем следующий аргумент: для каждого , у нас есть, что если только у Боба-й экземпляр заменены , то экстракты правильно. Кроме того, Боб и неразличимы, таким образом, если мы заменим все другие экземпляры Боба на , -й экземпляр до сих пор экстракты правильно. Таким образом, для любого , если Есть н экземпляров , то -й экземпляр экстракты правильно. Таким образом, все экземпляры Экстракт правильно. И экземпляров ничем не отличаются от экземпляров Боба.

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

Итак, мы показали, что может быть выбрана независимо от . Это позволяет разорвать круг в выборе : Сначала мы начнем с произвольного . Затем мы выбираем произвольную -BQS скрытие и -онлайн-извлекаемые , а затем произвольных -BQS скрытие и -онлайн-извлекаемые приверженность . В случае повреждения Боба, мы затем построить тренажер, который использует кубитов и защищены от памяти ограниченной среде и противников. И в случае повреждения Алисы, используя аргумент и выше, получаем, что симулятор использует кубитов и защищены от -ограниченных средах и противников.

Анализ. Перейдем к формальному анализу . Рассмотрим сначала случай, когда получатель поврежден.

Лемма 8. Предположим, что незначительны, полиномиально-ограничены, причем является сверхлогарифмичным (в безопасности, параметр ). Предположим, что это -онлайн-экстрагируемых и это -BQS-скрыто. Считаем, что является семейством аффинных сильно универсальных хэш-функций. Тогда BQS-UC-эмуляция для поврежденного получателя B.

Доказательство. Во-первых, мы описываем структуру реальной и идеальной модели в случае, если сторона B (Боб) повреждена:

В реальной модели, у нас есть среда , противник Adv, честный участник (Алиса), поврежденная группа. Противник контролирует поврежденную группу , так эффективно он управляет связями между Алисой и Бобом. Среда обеспечивает входы Алисы и . См. рисунок 2 (a).

В идеальной модели, мы среду , симулятор Сим (будет определено ниже), манекен стороной , поврежденная участник , и приверженность функциональность. Входов и предоставляются фиктивные стороной и, следовательно, эффективно среды . симулятор Сим контролирует поврежденная участник , следовательно, получает выходы , и . См. рисунок 2 (б).

Исправить противника Adv. Чтобы показать, лемму 8, мы должны найти симулятор Сим с такое, что для любой среды с , реальной модели и идеальная модель незначительны-близко. Этот симулятор описан на рисунке 3. Мы используем сокращение и .


Чтобы показать, что реальная и идеальная модели незначительно-близки, мы начинаем с реальной модели, а также изменим машину в реальной модели шаг за шагом, пока мы в конечном итоге с идеальной моделью. На каждом шаге мы покажем, что сети до и после этого шага можно пренебрежительно близки.

Игра 1. Мы измененили машину следующим образом: Вместо выполнения программы честного получателя , выполняет экстрактор .

Обозначим через извлекаемое значение. Измененная не использует . Поскольку eсть до копий , а -онлайн-извлекаемые, реальная модель и игра 1, -близки.


Игра 2. Мы измененили машину чтобы отменять если открытие успешно и показывает значение

Так как С1 -онлайн-извлекаемые, в каждом случае, это произойдет с вероятностью не более , тем самым игра 1 и 2, игры -близко. Обратите внимание, что только машины, которые используют квантовую память в игре 2, , и копий . Поскольку является s1-памятью ограничен, и имеем, что общий объем квантовой памяти, используемый в игре 2 ограничен .

Игра 3. Мы изменяем машину чтобы взять на себя фиксированную вместо для каждого

Чтобы увидеть, что Игра 2 и Игра 3 незначительно-близко, введем промежуточные гибридные игры, , в которой только первая от обязательств по , заменены на обязательства по . Так как на наиболее кубитов квантовой памяти используются в игре 2 и, следовательно, также в , а с С2-обязательства по никогда не открываются, из того, что С2 -BQS скрыто следует, что и являются -близкими. Обратите внимание, что есть, в целом игра, до копий и таким образом до -обязательства по некоторым . Таким образом, и -близки.


Игра 4. Мы изменяем чтобы установить и послать вместо Бобу в шаге .

Данная модификация предназначена только для обозначения целей, игры 3 и 4 совершенно близко.

Игра 5. Мы изменили способ которым выбирал : в игре 4 у нас был . (Мы назовем это распределением ) В игре 5 мы используем (Мы назовем это распределением )

Чтобы показать что Игра 4 и Игра 5 очень близки, мы используем следующее утверждение:

Утверждение 1. Допустим . Для любого статистическая дистанция между выбирается в зависимости от и выбирается в зависимости от это не более .

Доказательство этого утверждения использует тот факт, что является результатом применения к случайной величины с высокой мин-энтропии. Из-за оставшейся-хеш-лемма [9], неотличима от случайности. Речь идет о полной версии [16] для доказательства. Использование утверждения 1 и того, что мы имеем экземпляров, мы немедленно получим, что игры 4 и 5, -близки, потому что значения никогда не используется (за исключением косвенно, через ).

Наконец, обратите внимание, что по построению Сим, Игра 5 и идеальная модель идеально близки. Таким образом, реальные и идеальные модели -близко с . С незначительны, и являются полиномиально ограниченными и является сверхлогарифмичными, имеем, что незначительна. Таким образом -BQS-UC-эмулирует в случае повреждения Боба.


Лемма 9. Предположим, что можно пренебречь, полиномиально-ограничена, и пренебрежимо мала (в параметре безопасности ). Предположим, что С1 - BQS скрыто и С2 -онлайн-извлекаемо. Предположим, что код с синдромом имеет эффективные коррекции ошибок.


Тогда -BQS-UC-эмулировано для поврежденного отправителя A.

Доказательство. Во-первых, мы описываем структуру реальной и идеальной модели в случае, если группа (Алиса) повреждена:

В реальной модели, у нас есть среда , противник Adv, поврежденная группа и честным участником B (Боб). Противник контролирует повреждение группы , так он эффективно управляет связью между Алисой и Бобом. Среда получает выходы Боба , и . См. рисунок 4 (а).

В идеальной модели, у нас есть среда , симулятор Sim, поврежденная группа , манекен группа и фиксированная функциональность . Входы и для предоставляется поврежденная группа и тем самым эффективно для симулятора Sim. Среда контролирует манекен группу и, следовательно, получает выходы , и для . См. рисунок 4 (б).

Исправим противника Adv. Чтобы показать, лемму 9, мы должны найти квантовый полиномиальный симулятор симулятор времени с такое, что для любой среды с , реальная модель и идеальная модель незначительно близко. Этот симулятор описан на рисунке 5. Обратите внимание, что квантово полиномиальное время: экстрактор является квантовым полиномиальным времем по определению, и вычислительние возможно за полиномиальное время, так как код с синдромом имеет эффективную коррекцию ошибок. С С2 -онлайн извлекаемо и используется экземпляров за экземпляр , . Мы используем сокращения и аналогично для и .


Прежде чем мы приступим, введем два варианта честного получателя . Машина ведет себя, как , но когда Алиса фиксирует используя С2, работает выполняя для C2, а не программа честного отправителя. Вызовите исполняемые значения . Кроме того, вычисляет с и , а затем вычисляет . В открытую фазу, - ведет себя, как . В частности, выходы , а не . То есть, вычисляется, но никогда не используется.

Машина ведет себя как , но выходы вместо .


По определению онлайн-экстрагируемости, а с не использует значение извлеченное , имеем, что и неразличимы. Точнее, для любой сети S, имеем, что и являются -близкими. Так как онлайн экстрагируемость была определена по отношению к не-памяти ограниченных противников, это справедливо, даже если не ограничена памятью.

В лемме 8, мы проведем расследование последовательности игр.

Игра 8. В игре , -й экземпляр заменяется экземпляром . (Примечание: Только один экземпляр заменяется, а не первый -ый экземпляр )

Мы используем следующее утверждение:

Утверждение 2. Пусть S будет памятью ограниченной сети. В исполнении , пусть обозначают значения вычисляется . Тогда .


Мы докажем это утверждение ниже. Поскольку C1 и C2 0-памяти ограничены, мы имеем, что машина является 0-памяти ограниченой. . Таким образом, мы можем применить утверждение 2 к . Таким образом, в , где являются значения вычисляется . Мы пишем если открытая фаза не может или не происходит (и, следовательно, не вычисляются ).

Игра 2. Эта игра определяется как реальная модель, за исключением того, что мы используем экземпляров вместо случаях экземпляров .

Пользуясь тем, что и неразличимы, получаем, что реальные модели и игра 2, -близко.

Снова используя, что и являются -неразличимы, мы получаем, что . Тогда

Так как это справедливо для всех , получим:

Игра 3. Эта игра определяется как реальная модель, за исключением того, что мы используем экземпляров вместо случая экземпляров .

Обратите внимание, что Game 2 и Game 3 отличаются только тем, что в игре 2 мы используем экземпляров и в игре 3 экземпляров . По определению, и отличаются только в значении, которое они вывыдят: выходы и выходы . Согласно (1), вероятность того, что значения различны в некоторых экземплярах ограничено . Следовательно, игра 2 и игра 3 являются -близкими.

Наконец, обратите внимание, что по построению Сим, игра 3 и идеальная модель идеально близки. Таким образом, реальные и идеальные модели -близко с . Так как можно пренебречь, полиномиально-ограничен, a незначительно, мы имеем, что является незначительным.

Тогда BQS-UC-эмулированно в случае повреждения Алисы.

Доказательство Утверждения 2. Зададим обозначим соответствующие значения, вычисленные . Мы сокращаем и . По Bad обозначим событие, и и . Конструкция подразумевает и . И подразумевает . Тогда подразумевает Bad. Однако, что бы показать утверждение 2, необходимо показать в . Чтобы показать это, мы снова продолженаем работы с последовательностью игры:

Игра 4. Исполнение .

Игра 5. Изменим , чтобы остановить после получения от Алисы.

Тогда .

Игра 6. Мы изменяем для совершения некоторой (произвольной) фиксированного значения вместо привязки к .


Мы хотим применить -BQS скрытия свойство C1, чтобы показать, что . Пусть обозначает отправителя в схеме С1 обязательств. По определению, взять на себя обязательство T (или ), внутренне работает . Построим противника , взаимодействующий с B1. Противник имитирует как в игре 5), за исключением машины B1 внутри . Обратите внимание, что в игре 5, только фаза фиксации С1 выполняется. Положим выход если Bad происходит.

Мы определяем , как , кроме того, что игнорирует свой ​​вход и фиксирует . Пусть Р -вероятность того, что выходы при работе с . В строительстве, . Таким образом, нам нужно только показать, что . Чтобы применить -BQS скрытия свойство C1, мы должны проверить, что a-памяти ограниченa. имитирует , Adv, и . Мы имеем по предположению. Но содержит экстрактор для C2, которая использует дополнительную кубитов квантовой памяти. Тем не менее, . выполняется после окончания фиксации фазы С1. То есть, BВ € - выполняется в пределах одного активации 1 (так как B1 не активирована больше после того, фаза фиксации). Обратите внимание, что, хотя один может использовать более кубитов во время активации, в котором моделируется, он сохраняет не более кубитов между активаций. Таким образом 1 является ограниченной памятью (помните, что наше определение из а-памяти ограниченной на стр. 470 требует только, чтобы оценка памяти была справедлива между активациями).

Следовательно, и таким образом .

Игра 7. Мы изменяем чтобы изменить только после получения .

С тех пор как не используется раньше . Изменяя значения и c . Мы скрываем два случая в зависимости от существования с и . Случай  : с синдромом Б-блока -линейным кодом, следовательно кодовое слово. Следовательно или Используя неравенство треугольника и мы получаем что или . Случай  : с тех пор как нет с и существует и до тех пор , мы имеем что следовательно .

Таким образом для любого фиксированного выбора мы имеем или или .

Если или если событие Bad не выполниться по определению. Если мы ограничим вероятность Bad происходит следующее: Зададим . Тогда для случайного с мы имеем .

Таким образом для любого фиксированного мы имеем . Усредняя выбор мы получаем .

Подводя итоги, мы имеем

Это показывает Утверждение 2.


Использование кодов Рида-Соломона для S, и извлекаемых обязательств из теоремы 6 для C1 и C2, мы можем подтвердить параметры чтобы удовлетворить условиям лемм 8 и 9. Таким образом, мы получаем следующую теорему:

Теорема 10. Пусть будут полиномиально-ограничены. Тогда есть выбор параметров и полиномиально-ограниченное целое такое, что полиномиальное время, постоянное всестороннее и BQS-UC-эмулирует .

Основные двух-группные вычисления. Комбинируя известные результаты [19,10,15], мы получаем постоянный всесторонний протокол, который квантово-UC эмулирует любой двухпартийной функциональностью и использует только обязательства от Алисы к Бобу. Комбинируя наш протокол, мы получим окончательный результат (подробнее см. полную версию [16]):

Теорема 11 (BQS двух групповое вычисление). Пусть классическая правильно сформированная вероятностная полиномиальная по временная функциональность. Пусть полиномиально-ограничены. Тогда существует полиномиально-ограниченное постоянной памяти, ограниченные протоколом без привлечения каких-либо функций, таких, что BQS UC-эмулирует .


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

Примечания

  1. Читатель может задаться вопросом, как это может быть то, что и может составить в целом в то время как и нет. Может быть не и быть тот же протокол?Причина кроется в точные условия теоремы о композиции: Для того чтобы сочинять, должна быть защищена от противников с более высокой квантовой памяти связаны, чем терпит. Таким образом и не может быть тот же протокол.
  2. Мы ограничены двухпартийной функциональностью, потому что наша конструкция использует подпротокол Вольфом и Wullschleger, чтобы изменить направление OT; этот протокол имеет смысл только в двухпартийной обстановке.
  3. Эта идея отражена более формально в силу полноты так называемого фиктивного противника, который показывает, что можно даже сдвиг полной атаки в окружающую среду.
  4. Так как мы рассматриваем только статистическую безопасность в этой работе, мы будем опускать квалификатор "статистическая". Аналогичным образом, когда мы говорим о классической-UC-безопасности и квантовой-UC-безопасности, мы имеем в виду статистический вариант этого понятия.
  5. Обратите внимание, что, строго говоря, формализм не модель среды с квантовой памяти: Для квантовых каналов они определяют , если для всех квантовых состояний, следов расстояние между и не более чем . Для моделирования сред с квантовой памяти, мы должны вместо этого требуют, чтобы для всех гильбертовых пространств H и все ПЃ квантовых состояний, следов расстояние между и находится на наиболее . Мы считаем, что последняя была предназначена смысл в .
  6. Мы используем символ , потому что память, ограниченной среде по существу модель неразличимости по отношению к так называемой норме.

Литература

  1. 1,0 1,1 Bennett, C.H., Brassard, G.: Quantum cryptography: Public-key distribution and coin tossing. In: IEEE International Conference on Computers, Systems and Signal Processing 1984, pp. 175–179. IEEE Computer Society, Los Alamitos (1984)
  2. Mayers, D.: Unconditionally Secure Quantum Bit Commitment is Impossible. Physical Review Letters 78(17), 3414–3417 (1997), http://arxiv.org/abs/quant-ph/ 9605044
  3. 3,0 3,1 Bennett, C.H., Brassard, G., Crépeau, C., Skubiszewska, M.H.: Practical quantum oblivious transfer. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 351–366. Springer, Heidelberg (1992)
  4. 4,0 4,1 Kilian, J.: Founding cryptography on oblivious transfer. In: STOC 1988, pp. 20–31. ACM, New York (1988)
  5. Damgård, I., Fehr, S., Salvail, L., Schaffner, C.: Cryptography in the bounded quantum-storage model. In: FOCS 2005, pp. 449–458 (2005), a full version http: //arxiv.org/abs/quant-ph/0508222
  6. Dziembowski, S., Maurer, U.: On generating the initial key in the bounded-storage model. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 126–137. Springer, Heidelberg (2004), ftp://ftp.inf.ethz.ch/pub/crypto/ publications/DziMau04b.pdf
  7. 7,0 7,1 Wehner, S.,Wullschleger, J.: Composable security in the bounded-quantum-storage model. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 604–615. Springer, Heidelberg (2008), http://arxiv.org/abs/0709.0492v1
  8. Fehr, S., Schaffner, C.: Composing quantum protocols in a classical environment. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 350–367. Springer, Heidelberg (2009)
  9. 9,0 9,1 9,2 9,3 9,4 9,5 Unruh, D.: Universally composable quantum multi-party computation. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 486–505. Springer, Heidelberg (2010), preprint on arXiv:0910.2912 [quant-ph]
  10. 10,0 10,1 Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS 2001, pp. 136–145. IEEE Computer Society, Los Alamitos (2001), full and revised version is [5]
  11. Ben-Or, M., Mayers, D.: General security definition and composability for quantum & classical protocols (September 2004), http://xxx.lanl.gov/abs/quant-ph/ 0409062
  12. Unruh, D.: Simulatable security for quantum protocols (September 2004), http://arxiv.org/ps/quant-ph/0409125
  13. 13,0 13,1 13,2 Unruh, D.: Concurrent composition in the bounded quantum storage model. IACR ePrint 2010/229 (February 2011), full version of this paper
  14. König, R.,Wehner, S.,Wullschleger, J.: Unconditional security from noisy quantum storage. arXiv:0906.1030v2 [quant-ph] (June 2009)