Позиционная квантовая криптография: невозможность и построение

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:47, 18 января 2016.
Editing Position Based Quantum Cryptography: Impossibility and Constructions
Title Position-Based Quantum Cryptography.png
Авторы Harry Buhrman[@: 1][@: 2][прим.: 1],

Nishanth Chandran[@: 3][прим.: 2],
Serge Fehr[@: 1],
Ran Gelles[@: 3][прим.: 2],
Vipul Goyal[@: 4],
Rafail Ostrovsky[@: 3][прим.: 3],
Christian Schaffner[@: 2][@: 1][прим.: 4].

Сайт Homepage of The International Association for Cryptologic Research
Перевели Nikita Stupin
Скачать оригинал


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

Введение

Предпосылки

Целью позиционной криптографии является использование географического положения участника в качестве своего единственного "удостоверения". Например, хотелось бы, чтобы отправить сообщение exfcnybrfv в географическом положении с гарантией, что участники могут расшифровать сообщение, только если он или она физически присутствует в . Общая концепция позиционной криптографии была представлена Чандраном, Гоялом, Мориарти и Островским [1]; определенные специфические задачи были рассмотрены до этого под разными именами (см. ниже в разделе 1.3).

Определенная задача в позиционной криптографии - это проблема позиционного подтверждения. У нас есть прувер в позиции , который хочет убедить множество верифаеров (в различных точках географического пространства) такие что должен быть в этой позиции pos. Прувер может запустить интерактивный протокол с верифаерами для того чтобы убедить их. Основная техника для такого протокола - это дистанционное связывание [2]. В этой технике верифаер посылает случайный одноразовый сигнал и измеряет время, которое потребовалось для ответа с этим значением. Предполагая, что скорость связи ограничена скоростью света, мы получаем верхнюю границу на дистанции от до верифаера.

Проблема безопасного позиционирования изучалась ранее, в области безопасности беспроводных сетей и было выдвинуто несколько предложений по решению этой задачи ([2], [3], [4], [5], [6], [7], [8], [9]). Однако, [1] показывает, что нет протокола для безопасной позиции, который предоставляет безопасность в условиях, когда противники объединяются. Другими словами, множество верифаеров не может отличить случай, когда они взаимодействуют с подлинным прувером в и когда они взаимодействуют с несколькими объединенными не подлинными верифаерами, никто из которых не находится в . Их невозможный результат сохраняется даже если кто-то из них сделает вычислительно сложное предположение и это так же исключает большинство других позиционных криптографических атак.

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

Это ставит перед нами вопрос: существуют ли другие предположения и окружения, в которых возможно реализовать позиционную криптографию?

Подход и результаты

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

Однако, такой подход не может быть достаточно точным. Как только злоумышленники передают энтангл состояния, они могут использовать квантовую телепортацию [10]. Хотя телепортация сама по себе не является противоречием вышеуказанному подходу, мы покажем, что основываясь на техниках Ваидмана [11], злоумышленники владеющие большим количеством энтангл состояний могут выполнить мгновенное нелокальное квантовое вычисление, которое в частности подразумевает, что они могут вычислить любую единичную операцию в их общем состоянии, используя только локальные операции и один раунд классической совместной коммуникации. Основываясь на этой технике, мы покажем как группа злоумышленников может атаковать и взломать любой алгоритм позиционного подтверждения.

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

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

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

Насколько нам известно, квантовые способы позиционного подтверждения впервые были рассмотрены Кентом в 2002 г. под именем "quantum tagging". Вместе с Мурно, Спиллером и Беаусолейлом был подан патент для лаборатории HP в 2004 г. и получен в 2006 г. [12]. Результаты их исследований не опубликовывались в научной литерауре [13]. В этой статье они описывают несколько базовых алгоритмов и как сломать их используя телепортационные атаки. Они предлагают другие вариации (алгоритмы IV—VI в [13]) не задумываясь о подобного рода атаках и тем самым оставляют брешь в безопасности.Наша основная атака показывает, что такой алгоритм также является не безопасной.

Одновременно и независимо от нашей работы, опубликованной здесь, и работа по квантовой пометки описанной выше, подход с использованием квантовых методов для безопасного положения-проверки был предложен Маленеем [14], [15]. However, the proposed scheme is merely claimed secure, and no rigorous security analysis is provided. As pointed out in [13], алгоритм Маленея также может быть нарушена атакой на основе телепортации. Чандран предложил и доказал безопасную квантовый алгоритм позициионной поверки [16]. Тем не менее, их доказательство неявно предполагает, что противники не имеют заранее известных энтанглментов; как показано в [13], их алгоритм становится небезопасным без этого предположения.

В последующей работе [17], Лау и Ло использовать подобные идеи, как в [13], чтобы показать ненадежность алгоритма позиционной проверки, которые имеют определенный (пока в довольно ограниченном) виде, которые включают в себя алгоритмы из [14], [15] и [16]. Кроме того, они предлагают алгоритмы позиционной проверки, которые сопротивляются их атаке, и они полагают, что безопасность обеспечена. В то время как эти протоколы могут быть безопасным, если противники заранее не поделились информацией, наша атака показывает, что все из них небезопасны в целом.

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

Идея проведения "мгновенного измерения нелокальных переменных" была выдвинута на Вайдманом [11] и была исследована Кларом и другими [19]. Понятие мгновенных нелокальных квантовых вычислений, представленных здесь, является продолжением задачи Вайдмана. После появления и циркуляции нашей работы, Бейги и Коинг [20] использовал технику на основе портов телепортации, предложенной Ишизакой и Хиросимой [21], [22], чтобы уменьшить количество энтанглмента, необходимое для выполнения мгновенной нелокального квантовых вычислений (от наших двойное экспоненциальное) экспоненциальный.

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

Атака и методы ее выполнения

Позиционная поверка. Простой подход. Здесь мы будем обсуждать здесь 1-мерный случай, в котором у нас есть два испытатели и , и прувер в положение , что лежит на прямой линии между и . Теперь, чтобы проверить , с позиции посылает BB84 кубит до , и посылает соответствующий базис до . Отправка этих сообщений происходит таким образом, что и прибудет в положении в одно и то же время. , то есть для измерения кубит в безисе , чтобы получить , и сразу же отправляет до and , который проверяет правильность , и если он прибыл "вовремя".

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

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

Позиционная поверка в No-PE модели. С другой стороны, вышеуказанные рассуждения не являются правильным в случае заранее неизвестной информации (No-PE), т.е. модели, где противники у злоумышленников нет предварительно известных квантовых состояний. Хотя эта модель может быть нереальной и искусственной, анализ протоколов в ней служит ступенькой к получению протоколов, которые защищают от противников, предварительно поделившихся и поддерживающих некоторое ограниченное количество информации. Но также, строго доказательство безопасности (для противника) в ограниченной No-PE модели уже не является нетривиальным и требует тяжелой техники. Наше доказательство использует компромисс большого количества дополнительной информации (CIT) в соответствии с Ренесом и Буало [24], и это гарантирует, что для любой стратегии, вероятность успеха и ограничена примерно 0.89. Повторяя вышесказанное, простой алгоритм последовательно, мы получаем безопасный многораундовый алгоритм позиционирования с экспоненциально малой ошибкой герметичности. Отметим, что при выполнении последовательных повторений в модели No-PE, противники должны ввести каждый раунд с не энтанглмента; таким образом, они не могут генерировать энтанглмент в одном раунде, храните его, и использовать его в следующем раунде.

Позиционная аутентификация и обмен ключами в No-PE модели. На основании (последовательных повторений) нашего алгоритм позиционной проверки в No-PE модели, мы также можем построить алгоритм позиционной аутентификации и позиционного обмена ключами, и доказать их безопасность в модели No-PE. Из-за ограниченного места, этот алгоритм и их анализ появляются только в полной версии данной статьи [25].

Терминология и обозначения

Мы предполагаем знакомство с основными понятиями квантовой теории информации и относятся к [26]; здесь мы введем некоторые новые обозначения.

Кубиты. Кубит это квантовая система с пространством размерности 2. Вычислительный базис (for a qubit) представлен и , Хадамард базис - , где обозначает Хадамардову матрицу размерности 2, с картами в и в . Состояние простанства n-кубитной системы задано двух n-мерным пространством .

Так как в основном мы используем два вышеуказанных базиса, мы можем упростить терминологию и обозначения, идентифицируя вычислительный базис с битом 0 и Хадамардов базис с битом 1 1. Следовательно, когда мы говорим, что n-кубитное состояние представлено в базисе , мы имеем в виду состояние измеренное в базисе используется для i-ого кубита. В результате измерения строка обозревается с вероятностью , где and .

Важным примером 2-кубитного состояния является EPR пара, которая задана и имеет следующие свойства: если кубит </math>A</math> измерен в вычисляемом базисе, то случайный бит обозревается и кубит замыкается на . Аналогично, если кубит измерен в Хардамардовом базисе, то случайный бит обозревается и кубит замыкается на .

Телепортация. Цель телепортации передать квантовое состояние из одной локации в другую с помощью обычной информации. Телепортация требует заранее установленную связь между двумя локациями. Чтобы телепортировать кубит в произвольное неизвестное состояние от Алисы к Бобу, Алиса выполняет Белл-измерение над и ее половину EPR-пары, владея выходом измерения . В то же время, другая половина EPR пары, находящаяся у Боба, переходит в состояние , где описывает четыре Паули-связи соответственно, и описывает сложное сопряжение транспозиции . Классическая информация затем передается Бобу, который может восстановить состояние выполняя над его частью EPR пары. Стоит отметить, что оператор является Хермитиановым, таким образом .

Задача позиционного подтверждения

Модель безопасности

Мы неформально опишем модель, которую мы используем для последующих разделах, которая является квантовой версией стандартной модели, введенной в [1] (см. там для полного описания). Мы также описываем нашу ограниченную модель, используемую для нашего доказательства безопасности, которую мы называем (No-PE) модель. Мы рассматриваем сущности , называемые верификаторами и пруверами. Кроме того, мы считаем, коалицию злоумышленников . Все лица могут выполнять произвольный квант операций и могут общаться с помощью квантовых (и классических) сообщений.

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

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

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

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

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

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

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

Безопасное позиционное подтверждение

Алгоритм позиционного подтверждения должна позволить пруверу в положение (in d-dimensional space) to convince a set of verifiers , которые находятся в соответствующих положениях , что он действительно в положении . Мы предполагаем, что замкнута на . Мы требуем, чтобы верификаторы совместно приняли, если прувер находится в положении , и мы требуем, чтобы верификаторы отклонили с "высокой" вероятностью в случае взаимодействия со злоумышленником, который не находится в . Последнее следует проводить, даже если злоумышленник не один, является группой сотрудничающих злоумышленников в произвольных позициях с for all . Мы ссылаемся на [1] для общего формального определения полноты и безопасности алгоритма позиционного подтверждения. В этой статье мы в основном описываем алгоритмы позиционных подтверждений следующего вида:


Определение 1. Алгоритм 1-раундового позиционного подтверждения состоит из следующих трех частей. Задача генератора , который выводит список челленджеров и вспомогательную информация ; алгоритм ответа , который на входе списка вызовов выводит список ответов ; и алгоритм проверки состоящий из .
, как говорят, является полным, если с вероятностью 1 для и генерируется с помощью и с помощью на входе .

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

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

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

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

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

Мгновенные нелокальные квантовые вычисления

Для того чтобы проанализировать безопасность алгоритмов позиционного контроля, сперва мы рассмотрим более общую задачу, которая интересна и сама по себе: мгновенные нелокальные квантовые вычисления [прим.: 5]. Рассмотрим следующую задачу, с участием двух сторон Алисы и Боба. Алиса владеет и Боб соответственно трехсторонней системы , которая находится в некотором неизвестном состоянии . Цель заключается в применении известного унитарное преобразование к , но без с помощью передачи данных, т.е. по средствам локальных операций. В общем случае такая задача неразрешима, так как это нарушает нонсигналлинг принцип. Целью мгновенных нелокальных квантовых вычислений является достижение вышеуказанной цели без нарушения принципа нонсигналов. В частности, целью Алисы и Боба является вычисление без связи состояния которое совпадает с с точностью до местности и кубита операций по и , где обозначает сущность в . Кроме того, эти данные определяется исходя из классической информации, которую Алиса и Боб получают в рамках своих действий. В частности, если Алиса и Боб обменяются классической информацией, которая может быть получена из одного раунда одновременной взаимной передачи, то они могут превратить в локальными кубитовыми операциями. Следуя идеи Вайдмана [11] мы покажем ниже, что мгновенные нелокальные квантовые вычисления возможны, если Алиса и Боб имеют достаточно много EPR-пар.

Далее положим и Хилбертовыми пространствами, где второй формер состоит из кубитов и соответственно, т.е и . Также пусть - унитарная матрица над . Алиса представляет систему и Боб - систему произвольного и неизвестного состояния . В добавление ко всему, у Алисы и Боба есть произвольное и конечное число EPR пар.

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

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

Следствие 1. Для каждой унитарной матрицы и для каждого , с достаточным количеством EPR пар, существует нелокальная операция для Алисы и Боба, которая состоит из локальных операций и одного раунда передачи данных, такого что для каждого начального состояния системы , совместное выполнение переводит в , с вероятностью .

По техническим причинам, мы докажем расширение Теоремы 1, которое, как легко видеть, эквивалентно. Разница с Теоремой 1 состоит в том, что Алиса и Боб дополнительно получают классические входы: для Алисы и для Боба, и матрица зависит от и . В такой ситуации варьируется в произвольном, но конечном множестве , и варьируется в произвольном, но конечном множестве .

Теорема 2. Для каждого семейства унитарных матриц и для каждого , с достаточным количеством EPR пар, существует семейство и локальных операций, выполняемых на стороне Алисы и Боба, имеет следующее свойство. Для каждого начального состояния , каждого и , выполнение переводит состояние в и дает классический выход для Алисы и для Боба с вероятностью . Состояние совпадает с до локальных кубит операций в и , которые определены и .

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

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

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

  1. Алиса телепортирует Бобу, используя канал телепортации, который помечен ее входом . Обозначим измерение ее выхода как .
  2. Для каждого , Боб делает следующее. Он применяет матрицу к кубитам, что эквивалентно его части EPR пар полученных через канал телепортации, обозначенный . Затем он телепортирует результирующе состояние Алисе, используя канал телепортации, помеченный как . Обозначим соответствующий выход как .
  3. Алиса определяет кубитов, которые являются ее частью EPR пар, полученных по каналу телепортации, помеченному как , в состоянии .

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

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

   

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

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

Вычисления показывают, что количество EPR-пар, необходимых Алисе и Бобу в алгоритме, описанной в доказательстве, является экспонинцеальным в .

В недавней работе [20] Беиги и Кониг использовали различные виды квантовой телепортации по Ишизаке и Хиросиме [21][22], чтобы уменьшить количество необходимых энтанглментов для выполнения мгновенного нелокального квантового вычисления к экспонентеразмером кубитной системе. Остается открытым вопрос о необходимости такого экспоненциально большого количество энтанглментов.

Невозможность безусловного позиционного подтверждения

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

Рассмотрим произвольный алгоритм позиционного подтверждения в нашей модели (как указано в п. 3.1). Напомним, что в этой модели, верификаторы должны основывать свои решения исключительно на ответах прувера и задержке этих ответов. Прувер не имеет никаких преимуществ перед злоумышленниками, находясь на установленной позиции [прим.: 6]. Такой алгоритм позиционной проверки может быть в форме, указанной на рис. 1, но также может быть составлена из нескольких раундов взаимодействия прувера и верифаеров.

Для прувера , подобная общий алгоритм состоит из следующих шагов. имеет локальный квантовый регистр , который установлен на некоторое стандартное значение в начале алгоритма. На каждом шаге, получает систему от и систему от , и вместе создают систему . Положим состояние четырехразрядной системы , что определено алгоритмом и шагом алгоритма внутри алгоритма, на которой мы фокусируемся. Затем применяет фиксированное [прим.: 7] известное унитарное преобразование к , и посылает системы и обратно в и (сохраняя ). Заметим, что после преобразования состояние системы задано , где сущность, действующая в . По некоторым соображениям, как и в разделе 4, будет удобно разделить классические и квантовые входы, и, таким образом, мы положим матрицу зависящую от классической информации и , где было отправлено вместе с , и было отправлено вместе .

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

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

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

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

Безопасное позиционное подтверждение в No-PE модели

В этом разделе мы показываем возможность безопасного позиционного подтверждения в модели No-PE. Рассмотрим следующую основную однораундовый алгоритм позиционного подтверждения в модели No-PE, приведенную в алгоритме 2, основанную на кодировании BB84.

   Алгоритм 2:
   0.  выбирает два случайных бита  и тайно отправляет их .
   1.  подготавливает кубит  и отправляет его , а  отправляет бит  так, что  и  приходит в  одновременно.
   2. Когда  и  получены,  вычисляет  в базисе  для обозревания  и отправляет  к  и .
   3.  и  принимаются, если на обеих сторонах  приходит одновременно и .

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

Теорема 3. Однораундовый алгоритм позиционного подтверждения BB84 из алгоритма 2 представляет собой -sound with , в No-PE модели.

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

Доказательство. Доказательство использует несколько концепций квантовой информационной теории, которая более объяснена более подробно в полной версии статьи [25]. A key idea in this proof is the use of the complementary information trade-off (CIT) [24] (см. также [27]). В форме, удобной для на, CIT утверждает, что для любого тройного состояния с , выполняется следующее. Если равномерно распределена в и результат вычисления в базисе , тогда , где энтропия Неумана.

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

   Алгоритм 3:
   0.  и  тайно выбирают случайный бит .
   1.  подготавливает EPR пару , сохраняет кубит  и посылает  в .
   2. Когда  и  получены,  вычисляет  в базисе , чтобы обозревать  и отправляет  к  и .
   3. И только сейчас, когда  получен,  вычисляет  в базисе  для обозревания  и тайно отправляет  к .  и  принимаются, если на обоих концах    прибыл вовремя и .

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

Так как и не принимаются, если не получено вовремя и злоумышленники не используют заранее известный энтанглмент в No-PE модели, все потенциально успешные стратегии и должны выглядеть следующим образом. Так как получает бит от , он передает его . Так же, как только получает кубит , он применяет произвольную квантовую операцию к полученному кубиту , которая переводит его в двустороннее состояние (с произвольным состоянием системы ), и сохраняет и отправляет к . Затем, как только получает , он производит некоторые вычисления (которые зависят от ) к для получения , и как только получает , он выполняет некоторые вычисления (которые зависят от ) к , чтобы получить , и оба отправляют и немедленно к и , соответственно. Теперь мы покажем, что and является верхней границей как и утверждалось.

Положим состоянию тройной сисеты после применения квантовых операций к кубиту . Важно осознавать, что состояние не зависит от . Так происходит потому, что должен применить квантовокую операцию к до того как он узнает .[прим.: 8] назовем полученным в в вычислении или Хадамардовом базисе . Запишем , как случайные переменные , , что следует из CIT, где . Положим и обозначение классической информации, полученной и в результате вычисления и соответственно, с базисами, которые зависят от . Из вышесказанного следует, что

   

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

   

и вероятность и допускают, что действительно верхняя граница как и утверждалось. Полное доказательство [25].

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

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

Другие задачи позиционной криптографии

В полной версии этой статьи [25] показаны следующие результаты. Используя общий алгоритм позиционного подтверждения, мы построим алгоритм позиционной аутентификации, которые гарантируют, что переданное сообщение происходит из , который в некотором специальной локации. В комбинации с алгоритмом квантового распределения ключей, результатов данной статьи в позиционном распределении ключей, которое позволяет верификаторам обмениваться криптографическим ключом с прувером, гарантирующую что только прувер в локации получает , а злоумышленник, находящийся не в локации не знает . Используя данный алгоритм позиционного подтверждения в No-PE модели, мы получили алгоритмы защиты позиционной криптографии и позиционного распределения ключей в No-PE модели.

Заключение

Мы доказали невозможность получения результата для позиционной квантовой криптографии, We have proven a general impossibility result for position-based quantum cryptography, тем самым показывая уязвимость некоторых недавно предложенных алгоритмов [13][14][15][16][17]. Результаты нашей работы уже повели за собой появление новых работ [20] о количестве энтанглментов, необходимых для нарушения работы алгоритма позиционного подтверждения. needed to break general position-verification schemes.

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

Благодарности. Мы благодарим Чарльза Бнетта, Фредерика Дюпуиса и Луисса Сальвали за интересные дискуссии. HB благодарит Санду Попенсу за предоставленное объяснение алгоритма Ваидмана [19].

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

  1. 1,0 1,1 1,2 Centrum Wiskunde & Informatica (CWI), The Netherlands
  2. 2,0 2,1 University of Amsterdam, The Netherlands
  3. 3,0 3,1 3,2 University of Amsterdam, The Netherlands
  4. Microsoft Research, Bangalore, India

Примечание

  1. Supported by a NWO VICI grant and the EU 7th framework grant QCS.
  2. 2,0 2,1 Supported in part by NSF grants 0716835, 0716389, 0830803, and 0916574.
  3. Supported in part by IBM Faculty Award, Xerox Innovation Group Award, the Okawa Foundation Award, Intel, Teradata, DARPA, BSF grant 2008411, NSF grants 0716835, 0716389, 0830803, 0916574 and U.C. MICRO grant.
  4. Supported by a NWO VENI grant.
  5. Это расширение задачи "мгновенного вычисления нелокальных переменных", представленное Ваидманом [11].
  6. В частности, прувер не обменивается никакой секретной информацией с верифаерами, обособляя нашу модель от моделей, описанных выше в примере [18].
  7. фиксировано для конкретного алгоритма, но может различаться для различных алгоритмов.
  8. Мы подчеркиваем, что эта независимость нарушается, если и могут начинать с энтанг состоянием, потому что в таком случае может действовать на своей стороне энтангл состояния в -зависимом варианте, что приводит все состояние в зависимость от .

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 Chandran, N., Goyal, V., Moriarty, R., Ostrovsky, R.: Position based cryptography. In: CRYPTO 2009, Springer (2009) 391—407
  2. 2,0 2,1 Brands, S., Chaum, D.: Distance-bounding protocols. In: EUROCRYPT'93, Springer (1994) 344—359
  3. Sastry, N., Shankar, U., Wagner, D.: Secure verification of location claims. In: WiSe'03. (2003) 1—10
  4. Vora, A., Nesterenko, M.: Secure location verification using radio broadcast. In: OPODIS'04. (2004) 369—383
  5. Bussard, L.: Trust Establishment Protocols for Communicating Devices. PhD thesis, Eurecom-ENST (2004)
  6. Capkun, S., Hubaux, J.P.: Secure positioning of wireless devices with application to sensor networks. In: IEEE INFOCOM. (2005) 1917—1928
  7. Singelee, D., Preneel, B.: Location verification using secure distance bounding protocols. In: IEEE MASS'10. (2005)
  8. Zhang, Y., Liu, W., Fang, Y., Wu, D.: Secure localization and authentication in ultra-wideband sensor networks. IEEE Journal on Selected Areas in Communications 24 (2006) 829—835
  9. Capkun, S., Cagalj, M., Srivastava, M.: Secure localization with hidden and mobile base stations. In: IEEE INFOCOM. (2006)
  10. Bennett, C.H., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., Wootters, W.K.: Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels. Phys. Rev. Lett. 70(13) (1993) 1895—1899
  11. 11,0 11,1 11,2 11,3 11,4 Vaidman, L.: Instantaneous measurement of nonlocal variables. Phys. Rev. Lett. 90(1) (2003) 010402
  12. Kent, A., Munro, W., Spiller, T., Beausoleil, R.: Tagging systems (2006) US patent nr 2006/0022832.
  13. 13,0 13,1 13,2 13,3 13,4 13,5 13,6 Kent, A., Munro, B., Spiller, T.: Quantum tagging: Authenticating location via quantum information and relativistic signalling constraints. arXiv/quant-ph:1008.2147 (2010)
  14. 14,0 14,1 14,2 Malaney, R.A.: Location-dependent communications using quantum entanglement. Phys. Rev. A 81(4) (2010) 042319
  15. 15,0 15,1 15,2 Malaney, R.A.: Quantum location verification in noisy channels (2010) arXiv/quant-ph:1004.2689.
  16. 16,0 16,1 16,2 Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R.: Position-based quan- tum cryptography. arXiv/quant-ph:1005.1750 (2010)
  17. 17,0 17,1 Lau, H.K., Lo, H.K.: Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Phys. Rev. A 83(1) (2011) 012322
  18. Kent, A.: Quantum tagging with cryptographically secure tags. arXiv/quant-ph:1008.5380 (2010)
  19. 19,0 19,1 Clark, S.R., Connor, A.J., Jaksch, D., Popescu, S.: Entanglement consumption of instantaneous nonlocal quantum measurements. New Journal of Physics 12(8) (2010) 083034
  20. 20,0 20,1 20,2 Beigi, S., Koenig, R.: Simplified instantaneous non-local quantum computation with applications to position-based cryptography. arXiv/quant-ph:1101.1065 (2011)
  21. 21,0 21,1 Ishizaka, S., Hiroshima, T.: Asymptotic teleportation scheme as a universal programmable quantum processor. Phys. Rev. Lett. 101(24) (2008) 240501
  22. 22,0 22,1 Ishizaka, S., Hiroshima, T.: Quantum teleportation scheme by selecting one of multiple output ports. Phys. Rev. A 79(4) (2009) 042306
  23. Giovannetti, V., Lloyd, S., Maccone, L.: Quantum cryptographic ranging. Journal of Optics B 4(4) (2002) 042319
  24. 24,0 24,1 Renes, J., Boileau, J.: Conjectured strong complementary information tradeoff. Phys. Rev. Let. 103(2) (2009) 020402
  25. 25,0 25,1 25,2 25,3 Buhrman, H., Chandran, N., Fehr, S., Gelles, R., Goyal, V., Ostrovsky, R., Schaffner, C.: Position-Based Quantum Cryptography: Impossibility and Constructions (2010) Full version of this paper, http://arxiv.org/abs/1009.2490.
  26. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge university press (2000)
  27. Berta, M., Christandl, M., Colbeck, R., Renes, J.M., Renner, R.: The uncertainty principle in the presence of quantum memory. Nature Physics (2010)
  28. Damgard, I., Fehr, S., Salvail, L., Schaffner, C.: Cryptography in the bounded quantum-storage model. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE (2005) 449—458