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

Квантовое подбрасывание монеты использует принципы квантовой механики для шифрования сообщений для безопасной связи. В отличие от других типов квантовой криптографии, квантовое подбрасывание монеты — это протокол, используемый между двумя пользователями, которые не доверяют друг другу. Из-за этого оба пользователя (или игроки) хотят выиграть в подбрасывании монеты и будут пытаться обмануть различными способами. Будем рассматривать двух удаленных игроков, соединенных каналом, которые не доверяют друг другу. Проблема согласования ими случайного бита путем обмена сообщениями по этому каналу, не полагаясь на какую-либо доверенную третью сторону, называется проблемой подбрасывания монеты в криптографии^[1]. Квантовое подбрасывание монеты использует принципы из квантовой механики для шифрования сообщений, чтобы обеспечить безопасную связь. Сама идея является криптографическим примитивом, который может быть использован для построения более сложных и полезных криптографических протоколов^[2], например, квантового византийского соглашения.

Важно отметить, что в данном случае пользователи не доверяют друг другу^[2]. Пользователи будут стремиться выиграть. Поэтому в процессе возможно даже жульничество.

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

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

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

Случай, когда каждый игрок знает предпочтительный бит другого является более слабым вариантом задачи (weak coin flipping — WCF). Имея классический канал связи в этом случае улучшения не будет. С другой стороны, было доказано, что протоколы WCF со сколь угодно малыми смещениями действительно существуют. Но самый известный явный протокол WCF имеет предвзятость. ${\displaystyle 1/6\approx 0.1667}$ .

Тем не менее, на данный момент квантовый подход реализовать оказалось гораздо сложнее, чем классический аналог.

История

Теория

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

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

Получается, что главная проблема Алисы и Боба в том, что они не доверяют друг другу. Единственный ресурс, который у них есть, — это телефонный канал связи, третья сторона повлиять никак не может. Следовательно, Алиса и Боб должны либо поверить и согласиться на значение, которое им говорят. Либо считать, что другой обманывает.^[7]

В 1984 году Чарльз Беннетт и Джайлс Брассард своей статьей положили начало квантовой криптографии.

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

Эксперимент

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

Определение

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

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

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

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

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

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

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

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

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

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

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

Расширения

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

Мошенничество

Главная проблема данного протокола в том, что стороны не доверяют друг другу^[12] Эти две стороны общаются по каналу связи на некотором расстоянии, и они должны договориться о том, кто выиграет, а кто проиграет, причем победа каждого будет равновероятна.^[12] Однако, поскольку они не доверяют друг к другу, вероятно, произойдет обман. Обман может происходить несколькими способами, например, игрок может заявить, что потерял часть сообщения, когда результат его не устраивает, или увеличивая среднее количество фотонов, содержащееся в каждом из импульсов.^[8]

Для того, чтобы смошенничать, Бобу нужно угадать базис Алисы с вероятностью большей ½.^[12] Чтобы добиться этого, Боб должен уметь отличать последовательность фотонов, поляризованных случайным образом в одном базисе, от последовательности фотонов, поляризованных в другом базисе.^[12]

Примечания

1. Blum, Manuel (1983-01-01). "Coin flipping by telephone a protocol for solving impossible problems". ACM SIGACT News. 15 (1): 23—27. doi:10.1145/1008908.1008911. ISSN 0163-5700.
2. Oded., Goldreich. Foundations of cryptography. — Cambridge, UK : Cambridge University Press, 2003. — ISBN 9780521791724.
3. Cleve, R. Limits on the security of coin flips when half the processors are faulty // Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. — ACM, 1986-11-01. — P. 364–369. — ISBN 0897911938. — doi:10.1145/12130.12168.
4. A. Kitaev, Quantum Coin Flipping, Quantum Information Processing Workshop, Mathematical Sciences Research Institute, University of California, Berkeley, 2003.
5. Ambainis, A. (2004). "Multiparty quantum coin flipping". Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004. IEEE: 250—259. arXiv:quant-ph/0304112. doi:10.1109/ccc.2004.1313848. ISBN 0769521207. Архивировано 17 октября 2022. Дата обращения: 15 октября 2022.
6. Anna Pappa et al., «Experimental Plug and Play Quantum Coin Flipping» Архивная копия от 17 октября 2022 на Wayback Machine, Nature Communications, April 24, 2014
7. C. Döscher and M. Keyl, «An Introduction to Quantum Coin-Tossing», Cornell University Library, February 1, 2008
8. Stuart Mason Dambort, «Heads or tails: Experimental quantum coin flipping cryptography performs better than classical protocols» Архивная копия от 25 марта 2017 на Wayback Machine, Phys.org, March 26, 2014
9. Blum, Manuel (1983-01-01). "Coin flipping by telephone a protocol for solving impossible problems". ACM SIGACT News. 15 (1): 23—27. doi:10.1145/1008908.1008911. ISSN 0163-5700.
10. D. Aharonov, A. Ta-Shma, U. V. Vazirani, and A. C. Yao, Quantum bit escrow, in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM, New York, 2000, pp. 705—714.
11. Spekkens, R. W. (2002). "Quantum Protocol for Cheat-Sensitive Weak Coin Flipping". Physical Review Letters. 89 (22): 227901. arXiv:quant-ph/0202118. Bibcode:2002PhRvL..89v7901S. doi:10.1103/PhysRevLett.89.227901. PMID 12485105.
12. Charles H. Bennett and Giles Brassard, «Quantum cryptography: Public key distribution and coin tossing» Архивная копия от 29 ноября 2022 на Wayback Machine, Theoretical Computer Science, December 4, 2014