Подбрасывание квантовой монеты

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

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

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

Самый основной показатель качества протокола подбрасывания монеты определяется его предвзятостью, числом между $0$ и $1/2$. Предвзятость протокола отражает вероятность успеха всемогущего мошенника, который использует наилучшую возможную стратегию. Протокол с предвзятостью $0$ означает, что ни один игрок не может жульничать. Протокол с предвзятостью $1/2$ означает, что хотя бы один игрок всегда может добиться успеха в мошенничестве. Очевидно, что чем меньше смещение, тем лучше протокол.

когда связь осуществляется по квантовому каналу , даже самый лучший мыслимый протокол не может иметь смещение меньше, чем Было показано, что $1/{\sqrt {2}}-1/2\approx 0.2071$.

Рассмотрим случай, когда каждый игрок знает, что предпочитает другой игрок. Задача подбрасывания монеты, в которой делается это дополнительное предположение, представляет собой ее более слабый вариант, называемый слабым подбрасыванием монеты (WCF). В случае классических каналов это дополнительное предположение не дает улучшения. С другой стороны, было доказано, что протоколы WCF со сколь угодно малыми смещениями существуют. Однако самый известный явный протокол WCF имеет предвзятость. $1/6\approx 0.1667$.

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

История

Теория

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

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

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

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

Эксперимент

Как было опубликовано в 2014 году, группа ученых из Лаборатории связи и обработки информации (LTCI) в Париже экспериментально реализовала протоколы подбрасывания квантовых монет. Исследователи сообщили, что протокол работает лучше, чем классическая система, на подходящем расстоянии для городской оптической сети.

Определение

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

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

Сильное подбрасывание монеты

В квантовой криптографии сильное подбрасывание монеты (SCF) определяется как задача подбрасывания монеты, когда каждый игрок не обращает внимания на предпочтения другого.

Слабый подброс монеты

В квантовой криптографии слабый подбрасывание монеты (WCF) определяется как задача подбрасывания монеты, когда каждый игрок знает предпочтения другого.

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

Предвзятость

Рассмотрим любой протокол подбрасывания монеты. Пусть Алиса и Боб будут двумя игроками, желающими реализовать протокол. Рассмотрим сценарий, в котором Алиса жульничает, используя свою лучшую стратегию против Боба, который честно следует протоколу. Пусть вероятность того, что Боб получит результат, который предпочла Алиса, определяется выражением $P_{A}^{*}$. Рассмотрим обратную ситуацию: Боб жульничает, используя свою лучшую стратегию против Алисы, которая честно следует протоколу. Пусть соответствующая вероятность того, что Алиса получит результат, который Боб предпочел бы дать, равна $P_{B}^{*}$.

Смещение протокола определяется как ${\textstyle \epsilon :=\max[P_{A}^{*},P_{B}^{*}]-{\frac {1}{2}}}$.

Половина вычитается, потому что в половине случаев игрок получает желаемое значение чисто случайно.

Расширения

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

Протоколы

Использование сопряженного кодирования

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

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

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

1. Алиса посылает Бобу заданное количество К-фотонных импульсов в квантовых состояниях. $|\phi _{\alpha _{i}c_{i}}\rangle$. Каждый из этих фотонных импульсов готовится независимо после случайного выбора Алисой базиса α _i и бита c _i, где i = 1, 2, 3...K.
2. Затем Боб измеряет импульсы от Алисы, определяя случайный базис β _i . Боб записывает эти фотоны, а затем сообщает Алисе о первом успешно измеренном фотоне j вместе со случайным битом b .
3. Алиса показывает основу и фрагмент, которые она использовала в основе, которую дал ей Боб. Если две базы и биты совпадают, то обе стороны правдивы и могут обмениваться информацией. Если бит, сообщенный Бобом, отличается от бита Алисы, это неправда.

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

Более общее объяснение приведенного выше протокола выглядит следующим образом:

1. Алиса сначала выбирает случайный базис (например, по диагонали) и последовательность случайных кубитов. Затем Алиса кодирует выбранные ею кубиты как последовательность фотонов, следующих выбранному базису. Затем она отправляет эти кубиты в виде поезда поляризованных фотонов Бобу по каналу связи.
2. Боб выбирает последовательность считывания оснований случайным образом для каждого отдельного фотона. Затем он считывает фотоны и записывает результаты в две таблицы. Одна таблица содержит прямолинейные (горизонтальные или вертикальные) фотоны, полученные, и один из фотонов, полученных по диагонали. У Боба могут быть дыры в таблицах из-за потерь в детекторах или каналах передачи. Теперь Боб делает предположение о том, какой базис использовала Алиса, и объявляет свое предположение Алисе. Если он угадал правильно, он выигрывает, а если нет, то проигрывает.
3. Алиса сообщает, выиграл он или нет, сообщая Бобу, какое основание она использовала. Затем Алиса подтверждает информацию, отправляя Бобу всю исходную последовательность кубитов, которую она использовала на шаге 1.
4. Боб сравнивает последовательность Алисы со своими таблицами, чтобы убедиться, что со стороны Алисы не было мошенничества. Таблицы должны соответствовать базису Алисы, и не должно быть никакой корреляции с другой таблицей.

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

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

Обман

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

Чтобы Боб мог обмануть, он должен быть в состоянии угадать базис Алисы с вероятностью, большей, чем 1 / 2 . Чтобы добиться этого, Боб должен был бы уметь отличать последовательность фотонов, случайно поляризованных в одном базисе, из последовательности фотонов, поляризованных в другом базисе.

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

Обнаружение стороннего

Одиночные фотоны используются для передачи информации от одного игрока к другому (кубиты). В этом протоколе информация кодируется в одиночных фотонах с направлениями поляризации 0, 45, 90 и 135 градусов, неортогональных квантовых состояниях. Когда третья сторона пытается прочитать или получить информацию о передаче, она изменяет поляризацию фотона случайным образом, который, вероятно, обнаруживается двумя игроками, поскольку он не соответствует шаблону, которым обмениваются два законных пользователя.

Протокол Dip Dip Boom (слабое подбрасывание монеты с уклоном ${\textstyle 1/6}$)

Протокол Dip Dip Boom (DDB) — это квантовая версия следующей игры. Рассмотрим список чисел ${p_{i}}$, каждый от 0 до 1. Игроки, Алиса и Боб, по очереди произносят «Падение» или «Бум» с вероятностью. $p_{i}$ в раунде $i$. Побеждает игрок, сказавший «Бум». Очевидно, что мошенник может просто сказать «Бум» и выиграть, поскольку за более длительные игры наград нет. Мы будем рассматривать игры, которые завершаются так, что для некоторых (больших) $i$, сказать $n$, мы установили $p_{i}=1$.

Рассмотрим раунд $i$. Обозначим через $P_{A}(i)$ и $P_{B}(i)$ вероятность победы Алисы и Боба соответственно. Позволять $P_{U}(i)$ — вероятность того, что игра останется нерешенной. Эти числа для описанной выше классической игры можно вычислить индуктивно.

Теперь мы опишем квантовую версию. Позволять ${\mathcal {A}},{\mathcal {B}}$ быть трехмерным гильбертовым пространством, натянутым на $|A\rangle ,|B\rangle ,|U\rangle$. Позволять ${\mathcal {M}}$ быть двумерным гильбертовым пространством, натянутым на $|{\text{DIP}}\rangle ,|{\text{BOOM}}\rangle$.

1. Инициализация : Алиса держит ${\mathcal {A}}\otimes {\mathcal {M}}$ регистрирует и инициализирует состояние для $|U\rangle \otimes |{\text{DIP}}\rangle$. Боб держит регистр ${\mathcal {B}}$ и инициализирует его в состояние $|U\rangle$.
2. Итерация : Для $i=1$ к $n$ необходимо выполнить следующее. Для нечетных $i$ мы устанавливаем X=A (для Алисы) и Y=B (для Боба); даже для $i$ мы устанавливаем X=B и Y=A.
   • X реализует операцию $R_{i}:={\text{Rot}}(|U\rangle \otimes |{\text{DIP}}\rangle ,|X\rangle \otimes |{\text{BOOM}}\rangle ,p_{i})$.
   • X отправляет регистр сообщений Y.
   • Y реализует операцию ${\tilde {R}}_{i}:={\text{Rot}}\left(|U\rangle \otimes |{\text{BOOM}}\rangle ,|X\rangle \otimes |{\text{DIP}}\rangle ,{\frac {p_{i}P_{U}(i-1)}{P_{X}(i)}}\right)$.
   • Y измеряет регистр сообщений в вычислительной основе. Если результат BOOM, Y прерывает игру и объявляет себя победителем.
3. Измерение : Алиса и Боб измеряют свой локальный регистр. ${\mathcal {A}}$ и ${\mathcal {B}}$ соответственно. Если результат U, то они объявляют себя победителями. Если результат A, то победителем становится Алиса, а в случае B — Боб.

Замечания

• Для получения сбалансированного протокола необходимо выбрать $p_{i}$такое, что $P_{A}(n)={\frac {1}{2}}=P_{B}(n)$.
• Если оба игрока следуют протоколу, т. е. ни один игрок не жульничает, то результат в конце второго шага никогда не будет БУМ, как и результат шага 3 не будет таким же. $|U\rangle$.
• Анализ смещения этого протокола использует двойственность SDP .
• Для больших $n$ смещение протокола можно сделать сколь угодно близким к $1/6$.

монеты

Было показано, что, используя протокол WCF со сколь угодно малой погрешностью, можно построить протокол SCF со сколь угодно близкой к ${\textstyle {\frac {1}{\sqrt {2}}}-{\frac {1}{2}}}$ который, как известно, является оптимальным.

Экспериментальная реализация

Использование сопряженного кодирования

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

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

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