量子コイン投げ

チャネルで接続された、お互いを信頼していない遠隔地のプレイヤー 2 人を考えてみます。信頼できる第三者に頼ることなく、このチャネルを介してメッセージを交換することでランダム ビットに合意するという問題は、暗号学ではコイン フリップ問題と呼ばれます。^[1] 量子コイン フリップは、量子力学の原理を使用してメッセージを暗号化し、安全な通信を実現します。これは、より複雑で有用な暗号プロトコル ( ^[2]たとえば、量子ビザンチン合意)を構築するために使用できる暗号プリミティブです。

他の種類の量子暗号（特に量子鍵配送）とは異なり、量子コイン投げは、お互いを信頼していない2人のユーザー間で使われるプロトコルです。^[3]その結果、両方のユーザー（またはプレーヤー）はコイントスに勝ちたいと考え、さまざまな方法で不正行為を試みます。^[3]

古典的な設定、つまり量子通信がない場合、1人のプレイヤーは（原理的には）常にどのプロトコルに対しても不正行為を行うことができます。^[4]コミットメントスキームに基づく古典的なプロトコルもありますが、プレイヤーにはスキームを破る計算能力がないことを前提としています。対照的に、量子コイン投げプロトコルは、無制限の計算能力を持つプレイヤーによる不正行為にも抵抗できます。

コイン投げプロトコルの最も基本的な性能指数は、バイアス、つまりから の間の数値で表されます。プロトコルのバイアスとは、考えられる最善の戦略を使用する、全能の不正行為プレイヤーの成功確率を表します。バイアスのあるプロトコルとは、どのプレイヤーも不正行為ができないことを意味します。バイアスのあるプロトコルとは、少なくとも 1 人のプレイヤーが常に不正行為に成功できることを意味します。明らかに、バイアスが小さいほどプロトコルは優れています。 ${\displaystyle 0}$${\displaystyle 1/2}$${\displaystyle 0}$${\displaystyle 1/2}$

通信が量子チャネル上で行われる場合、考えられる最良のプロトコルであってもバイアスは 未満にはならないことが示されている。^{[5] [6]}${\displaystyle 1/{\sqrt {2}}-1/2\approx 0.2071}$

各プレイヤーが相手の優先ビットを知っている場合を考えてみましょう。この追加の仮定を行うコイン投げ問題は、弱いコイン投げ（WCF）と呼ばれるより弱い変種を構成します。古典的なチャネルの場合、この追加の仮定は改善をもたらしません。一方、任意の小さなバイアスを持つWCFプロトコルが存在することが証明されています。^{[7] [8]}しかし、最もよく知られている明示的なWCFプロトコルにはバイアスがあります。^[9]${\displaystyle 1/6\approx 0.1667}$

量子コイン投げは理論的には古典的なコイン投げよりも明らかに有利であるが、実際にそれを実現するのは困難であることが判明している。^{[3] [10]}

マヌエル・ブルムは1983年に計算アルゴリズムと仮定に基づいた古典的なシステムの一部としてコイン投げを導入しました。^[11]ブルムのバージョンのコイン投げは、次の暗号問題に答えます。

アリスとボブは最近離婚し、別々の都市に住んでいて、どちらが車を所有するかを決めたいと考えています。決めるために、アリスは電話でコインを投げたいと考えています。しかし、ボブはアリスに表を言うと、アリスがコインを投げて自動的に自分が負けたと告げられるのではないかと心配しています。^[12]

したがって、アリスとボブの問題は、彼らがお互いを信頼していないことです。彼らが持っている唯一のリソースは電話通信チャネルであり、コインを読み取ることができる第三者はいません。したがって、アリスとボブは、真実を語り、価値に同意するか、相手が不正行為をしていると確信する必要があります。^[12]

1984年、チャールズ・H・ベネットとジャイルズ・ブラッサードの論文から量子暗号が登場しました。この論文で、2人はコイン投げなどの従来の暗号プロトコルを強化するために量子力学を使用するというアイデアを紹介しました。 ^[3]それ以来、多くの研究者が量子力学を暗号に応用してきました。これは、量子力学が理論的に古典的な暗号よりも安全であることが証明されているためですが、実際のシステムでこれらのプロトコルを実証することは困難です。

2014年に発表されたように、パリの通信および情報処理研究所（LTCI）の科学者グループは、量子コイン投げプロトコルを実験的に実装しました。^[3]研究者は、このプロトコルは、大都市圏の光ネットワークに適した距離では、従来のシステムよりも優れたパフォーマンスを発揮すると報告しています。^[3]

暗号学では、コイン投げは、互いに不信感を抱いている遠隔地の2人のプレイヤーが第三者に頼ることなくランダムなビットに合意しようとする問題として定義されています。^[1]

量子暗号では、強いコイン投げ（SCF）は、各プレイヤーが他のプレイヤーの好みを知らないコイン投げ問題として定義されています。^[13]

量子暗号では、弱いコイン投げ（WCF）は、各プレイヤーが相手の好みを知っているコイン投げ問題として定義されています。^[14]

プレイヤーは反対の好みを持っていることになります。そうでない場合は、プレイヤーは単に望む結果を選択できるため、問題は無意味になります。

任意のコイン投げプロトコルを考えてみましょう。アリスとボブが、プロトコルを実装したい 2 人のプレイヤーであるとします。アリスが最善の戦略を使用して、プロトコルに正直に従うボブに対して不正行為をするシナリオを考えてみましょう。ボブがアリスが望んだ結果を得る確率は で与えられるものとします。逆の状況、つまり、ボブが最善の戦略を使用して、プロトコルに正直に従うアリスに対して不正行為をするシナリオを考えてみましょう。アリスがボブが望んだ結果を得る対応する確率は で与えられるものとします。 ${\displaystyle P_{A}^{*}}$${\displaystyle P_{B}^{*}}$

プロトコルのバイアスは と定義されます。 ${\textstyle \epsilon :=\max[P_{A}^{*},P_{B}^{*}]-{\frac {1}{2}}}$

半分が減算されるのは、プレイヤーが半分の確率で完全に偶然に希望の値を取得するためです。

コイン投げは、偏ったコイン、つまりビットの確率が等しくないコインに対しても定義できます。正しさの概念も形式化されており、両方のプレイヤーがプロトコルに従う場合 (誰も不正行為をしない)、プレイヤーは生成されたビットに常に同意し、ビットが一定の確率分布に従うことが必要です。

量子コイン投げやその他の種類の量子暗号は、量子ビットの送信を通じて情報を伝達する。受信側のプレイヤーは、測定を実行するまで量子ビット内の情報を知ることができない。^{[12]各量子ビットに関する情報は、単一の}光子 に保存され、光子によって運ばれる。^[10]受信側のプレイヤーが光子を測定すると、光子は変更され、再度測定しても同じ出力は生成されない。^[10]光子は同じ方法で一度しか読み取ることができないため、メッセージを傍受しようとする第三者は簡単に検出できる。^[10]

量子コイン投げとは、コイン投げで勝ちたいがためにお互いを信頼していない2人のプレイヤーの間でランダムな量子ビットが生成されることです。これにより、さまざまな方法で不正行為を行うことができます。^[3]コイン投げの本質は、2人のプレイヤーが通信チャネルを介して一連の命令を発行し、最終的に出力を生成することです。^[10]

基本的な量子コイン投げプロトコルには、アリスとボブの2人が関与します。^[11]

1. アリスはボブに量子状態にある Κ 個の光子パルスを送信します。これらの光子パルスはそれぞれ、アリスがi = 1、2、3...Κの基底 α _iとビット c _{i を}ランダムに選択して独立して準備されます。${\displaystyle |\phi _{\alpha _{i}c_{i}}\rangle }$
2. _{次にボブは、ランダム基底 β i を}識別してアリスからのパルスを測定します。ボブはこれらの光子を記録し、最初に正常に測定された光子j をランダムビットbとともにアリスに報告します。
3. アリスはボブが彼女に与えた基底で、自分が使用した基底とビットを明らかにします。2 つの基底とビットが一致した場合、両者は誠実であり、情報を交換できます。ボブが報告したビットがアリスのものと異なる場合、どちらかが誠実ではありません。

上記のプロトコルのより一般的な説明は以下のとおりです。^[15]

1. アリスはまずランダムな基底 (対角など) とランダムな量子ビットのシーケンスを選択します。次にアリスは選択した基底に従って選択した量子ビットを光子のシーケンスとしてエンコードします。次にアリスはこれらの量子ビットを偏光光子の列として通信チャネルを通じてボブに送信します。
2. ボブは、各光子に対してランダムに読み取り基底のシーケンスを選択します。次に、光子を読み取り、その結果を 2 つのテーブルに記録します。1 つのテーブルは、直線 (水平または垂直) で受信した光子のテーブルで、もう 1 つは斜めに受信した光子のテーブルです。ボブのテーブルには、検出器または伝送チャネルの損失により、穴がある場合があります。ボブは、アリスが使用した基底を推測し、その推測をアリスに発表します。推測が正しければボブは勝ち、正しくなければボブは負けます。
3. アリスは、ボブに自分が使用した基数を発表することで、ボブが勝ったかどうかを報告します。次に、アリスは手順 1 で使用した元の量子ビット シーケンス全体をボブに送信して、情報を確認します。
4. ボブはアリスのシーケンスを自分のテーブルと比較し、アリス側に不正行為がないことを確認します。テーブルはアリスの基数と一致している必要があり、他のテーブルとの相関関係はないはずです。

このプロトコルが適切に機能するためには、いくつかの仮定が必要です。まず、アリスはボブとは独立して、同じ確率で各状態を作成できるということです。次に、ボブが最初に測定に成功したビットについては、その基底とビットは両方ともランダムで、アリスとは完全に独立しています。最後の仮定は、ボブが状態を測定するとき、各状態を測定する確率は均一であり、他の状態よりも検出しやすい状態はないということです。この最後の仮定は特に重要です。なぜなら、アリスがボブが特定の状態を測定できないことを知っていれば、それを有利に利用できるからです。^[11]

コイン投げの主な問題は、それが不信感を持つ2つの当事者間で行われることです。^[15]これら2つの当事者は、互いに離れた通信チャネルを介して通信しており、勝者または敗者について合意する必要がありますが、勝つ可能性はそれぞれ50％です。^[15]しかし、彼らはお互いを信用していないため、不正行為が発生する可能性があります。不正行為は、結果が気に入らないときにメッセージの一部を失ったと主張したり、各パルスに含まれる光子の平均数を増やしたりするなど、さまざまな方法で発生する可能性があります。^[3]

ボブが不正行為をするには、アリスの基数を⁠以上の確率で推測できなければならない。1/2⁠ . ^[15]これを達成するためには、ボブは、ある基底でランダムに偏光した光子列を、別の基底で偏光した光子列から判別できなければなりません。^[15]

一方、アリスはいくつかの方法で不正行為をすることができますが、ボブが簡単にそれを検出できるため注意が必要です。^[15]ボブがアリスに正しい推測を送信すると、アリスはボブに、自分の光子がボブの正しい推測とは反対に偏光していると納得させることができます。^[15]アリスはボブに勝つために実際に使用したのとは異なる元のシーケンスをボブに送信することもできます。^[15]

単一光子は、あるプレイヤーから他のプレイヤー（量子ビット）に情報を渡すために使用されます。^[10]このプロトコルでは、情報は、0、45、90、135度の偏光方向を持つ単一光子、非直交量子状態でエンコードされます。^[15]第三者が送信情報を読み取ろうとしたり取得しようとすると、光子の偏光をランダムに変更しますが、これは2人の正当なユーザー間で交換されたパターンと一致しないため、2人のプレイヤーによって検出される可能性があります。^[15]

Dip Dip Boom (DDB) プロトコルは、次のゲームの量子バージョンです。^[9] 0 から 1 までの数字のリストを考えます。プレイヤーの Alice と Bob は、ラウンド で確率で交互に「Dip」または「Boom」と言います。「Boom」と言ったプレイヤーが勝ちます。明らかに、不正行為をするプレイヤーは、長いゲームには報酬がないため、単に「Boom」と言うだけで勝つことができます。たとえば、ある (大きな) に対してを設定するように終了するゲームを考えます。 ${\displaystyle {p_{i}}}$${\displaystyle p_{i}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle n}$${\displaystyle p_{i}=1}$

ラウンド について考えます。 を、をそれぞれアリスとボブが勝つ確率とします。をゲームが未決のままである確率とします。 上記の古典的なゲームに対するこれらの数値は、帰納的に評価できます。 ${\displaystyle i}$${\displaystyle P_{A}(i)}$${\displaystyle P_{B}(i)}$${\displaystyle P_{U}(i)}$

ここで量子バージョンについて説明します。 がによって張られる 3 次元ヒルベルト空間であるとします。が によって張られる 2 次元ヒルベルト空間であるとします。 ${\displaystyle {\mathcal {A}},{\mathcal {B}}}$${\displaystyle |A\rangle ,|B\rangle ,|U\rangle }$${\displaystyle {\mathcal {M}}}$${\displaystyle |{\text{DIP}}\rangle ,|{\text{BOOM}}\rangle }$

1. 初期化: アリスはレジスタを保持し、状態を に初期化します。ボブはレジスタを保持し、それを状態 に初期化します。${\displaystyle {\mathcal {A}}\otimes {\mathcal {M}}}$${\displaystyle |U\rangle \otimes |{\text{DIP}}\rangle }$${\displaystyle {\mathcal {B}}}$${\displaystyle |U\rangle}$
2. 反復: に対して、次の操作を実行する必要があります。奇数の場合は、X=A (アリスの場合)、Y=B (ボブの場合) を設定します。偶数の場合は、X=B、Y=A を設定します。 ${\displaystyle i=1}$${\displaystyle n}$${\displaystyle i}$${\displaystyle i}$
   • X は操作を実装します。${\displaystyle R_{i}:={\text{Rot}}(|U\rangle \otimes |{\text{DIP}}\rangle ,|X\rangle \otimes |{\text{BOOM}}\rangle ,p_{i})}$
   • X はメッセージ レジスタを Y に送信します。
   • Y は操作を実装します。${\displaystyle {\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. 測定: アリスとボブはそれぞれローカル レジスタとを測定します。結果が U の場合、彼らは自分たちが勝者であると宣言します。結果が A の場合、アリスが勝者であり、結果が B の場合、ボブが勝者です。${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$

• バランスの取れたプロトコルを得るには、となるように を選択する必要があります。${\displaystyle p_{i}}$${\displaystyle P_{A}(n)={\frac {1}{2}}=P_{B}(n)}$
• 両方のプレイヤーがプロトコルに従う場合、つまりどちらのプレイヤーも不正行為をしない場合は、ステップ 2 の終了時の結果は BOOM にならず、ステップ 3 の結果も にはなりません。${\displaystyle |U\rangle}$
• このプロトコルのバイアス分析では、SDP二重性が使用されます。
• が大きい場合、プロトコルのバイアスは に任意に近くなる可能性があります。${\displaystyle n}$${\displaystyle 1/6}$

任意に小さいバイアスを持つWCFプロトコルを使用することで、最適であることが知られているものに任意に近いバイアスを持つSCFプロトコルを構築できることが示されている。 ^[16]${\textstyle {\frac {1}{\sqrt {2}}}-{\frac {1}{2}}}$

歴史のセクションで述べたように、パリのLTCIの科学者たちは量子コイン投げプロトコルを実験的に実行しました。以前のプロトコルでは、安全を確保するために単一光子源またはエンタングルド源が必要でした。しかし、これらの源が量子コイン投げの実装を困難にしている理由です。代わりに、LTCIの研究者は単一光子源ではなく量子重ね合わせの効果を使用しました。これにより、利用可能な標準的な光子源で実装が容易になると主張しています。^[3]

研究者たちは、プロトコルに IdQuantique が開発した Clavis2 プラットフォームを使用しましたが、コイン投げプロトコルで動作するように Clavis2 システムを変更する必要がありました。Clavis2 システムで使用した実験セットアップには、双方向のアプローチが含まれています。1550 ナノメートルでパルス化された光がボブからアリスに送信されます。次に、アリスは位相変調器を使用して情報を暗号化します。暗号化後、彼女はファラデーミラーを使用して、選択したレベルでパルスを反射および減衰させ、ボブに送り返します。ボブは、2 つの高品質の単一光子検出器を使用して、位相変調器の測定基準を選択し、アリスからのパルスを検出します。^[11]

以前の検出器の検出効率が低かったため、研究者らはボブ側の検​​出器を交換しました。検出器を交換すると、15キロメートル (9.3 マイル) 以上のチャネルで量子優位性を示すことができました。グループが直面した他のいくつかの課題は、光子源の減衰が高かったためシステムを再プログラムすることと、システム コンポーネントの損失とエラーを特定するためのシステム分析を実行することでした。これらの修正により、科学者らは、プロトコルの最後に 2 人の正直な参加者がコイン投げを得ることができない確率である小さな正直な中止確率を導入することで、コイン投げプロトコルを実装することができました。ただし、通信距離は短いです。^[3]