量子プログラミングで量子暗号(量子鍵配送)をシミュレーションしてみる

概要

Microsoftが公開している量子プログラミング言語であるQ#が2月くらいにMac, Linuxでも使えるようになったので,Q#を使って量子暗号(量子鍵配送)のシミュレーションを書いてみました.

シミュレートする量子暗号

Wikipediaに意外としっかりと概要が書かれています.

量子鍵配送 - Wikipedia

今回実装したのはBB84プロトコルの方になります.プロトコルについて詳しく知りたい人は元論文を読むことをおすすめします.

C.H. Bennett, G. Brassard, "Quantum Cryptography: Public Key Distribution and Coin Tossing https://core.ac.uk/download/pdf/82447194.pdf

Q#について

Q#そのものについては以下の記事が参考になると思います.簡単に言うとMicrosoftが提供している量子コンピュータの動作を記述するための言語です.

qiita.com

Q#の導入

以下の記事を参考に導入します.今回はMacを使用していますがMicrosoft提供のものなので当然Windowsでも導入できます.

qiita.com

コード

コード全体はこちらのリポジトリに置いてあります. github.com

コードの各ステップでどのようにシミュレーションしているか説明していきます.

盗聴者(Eve)がいない場合

bb84.qs

量子Bitを扱う処理を主にこのbb84.qs内に記述しています.

operation BB84でbb84プロトコルを1回実行します.BitLengthで与えられた長さの量子ビットを使用して鍵配送を行います.Eavesdroppertrueである場合には盗聴者が存在する状態でのプロトコルを実行します.返す値はプロトコルを1回実行した後のAlice, Bob, Eveがそれぞれ得る結果のビット列となります.

まず最初にAliceが鍵として送りたいビット列とそのビット列を量子ビットを用いてエンコードする際に使用する基底を表すビット列を用意します.

// Choose Alice's bits and bases
set AliceBits[idx] = (RandomInt(2) == 0);
set AliceBases[idx] = (RandomInt(2) == 0);

そのビット列を使用してAliceはBobへ送る量子ビット列を生成します.

// Prepare Qubits by using Alice's bits and bases
if (AliceBits[idx]) {
    X(register[idx]);
}
if (AliceBases[idx]) {
    H(register[idx]);
}

Bobは受け取った量子ビット列をランダムに基底を選んで測定して,選んだ基底と測定した結果をビット列として保持します.

set BobBases[idx] = (RandomInt(2) == 0);
if (BobBases[idx]) {
    H(register[idx]);
    set BobBits[idx] = M(register[idx]) == One;
} else {
    set BobBits[idx] = M(register[idx]) == One;
}

その後AliceとBobは基底の情報をやり取りして同じ基底を使用したビットの情報を得ます.

for (idx in 0..BitLength - 1) {
    set IsSameBase[idx] = (AliceBases[idx] == BobBases[idx]);
}

盗聴者がいない場合には同じ基底を使用すれば同じ結果を得ることが出来るので同じ基底だったビットを得られる鍵として使用します.

Driver.cs

1回のbb84プロトコルで得られるビット列はbb84に使用した量子ビット列のうち同じ基底を使用したビットの列になるので期待値としては使用した量子ビット列の半分となります.なので得られたビット列の長さが鍵として使用したいビット列の長さになるまでプロトコルを繰り返します.private static bool SimulateBB84で鍵として使用したい長さのビット列が得られるまでbb84を繰り返しシミュレーションします.(盗聴者がいない場合を想定しているので今はEveのものに関しては無視してください)

 // Execute BB84 protocol until earn needed length bits
while (AliceKey.Length < KeyLength + CheckLength){
    var res = BB84.Run(sim, StepBits, Eavesdropper).Result;
    var (AliceReceives, BobReceives, EveReceives) = res;
    AliceKey = AliceKey + AliceReceives;
    BobKey = BobKey + BobReceives;
    EveKey = EveKey + EveReceives;
}

最終的に得られたビット列を表示して同じビット列を得ることが出来ていることを確認します.

// 出力例
There is no eavesdropper.
AliceKey:       00010
BobKey:         00010
AliceCheckBits: 01010
BobCheckBits:   01010

盗聴者(Eve)がいる場合

量子暗号の特徴である盗聴者がいた場合にそのことを検知できる,というのを見ていきましょう.ここで盗聴者(Eve)は,AliceとBobの間でやり取りされる量子ビットと古典ビットを全て盗聴することが出来ると仮定します.古典ビットは盗聴されても状態が変わらないので盗聴に気付けませんが量子ビットは盗聴する際に必ず測定をしなくては盗聴が出来ないので,その測定により状態が変わったことでAliceとBobは盗聴を検知することが出来ます.

bb84.qs

AliceからBobへ量子ビットが送られる時にEveはその量子ビットを測定することで盗聴します.この段階ではAliceがどの基底を使用してビット列をエンコードしたかという情報はまだAliceしか知らないためEveは適当に基底を選んで測定するしかないので適当に基底を選んで量子ビット列を測定します.

if (RandomInt(2) == 0) {
    H(register[idx]);
    set EveBits[idx] = M(register[idx]) == One;
    H(register[idx]);
} else {
    set EveBits[idx] = M(register[idx]) == One;
}

その後AliceからBobへ基底の情報が送られますが,この段階では既にEveは量子ビットの測定を終えてしまっているのでこの基底の情報は大した意味を持ちません. 最後にAliceとBobが同じ基底を使用したビットの位置の情報をやり取りするのでEveはその情報を盗聴することで,AliceとBobがどの位置のビットを鍵として使用するかの情報が得られるのでEveも同じ位置のビットを盗聴して得られる鍵として使用します.

Driver.cs

bb84プロトコルを繰り返してAliceとBobが必要な長さのビット列を得られた後にAliceとBobは得られたビット列のうち一部(CheckLength分の長さ)を盗聴があったかどうかを検知するために使います.

誤差を仮定しなければ,AliceとBobはbb84によって同じビット列が得られるはずなので,盗聴の検知に使用するビット列に違いがあれば盗聴があったということを検知できます.

// Checks if there is an eavesdropper
var AliceCheckBits = AliceKey.Substring(KeyLength, CheckLength);
var BobCheckBits = BobKey.Substring(KeyLength, CheckLength);
if (AliceCheckBits == BobCheckBits) {
    EavesdropMessage = "There is no eavesdropper.";
    result = false;
}
// 出力例
WARNING!! There is an eavesdropper.
AliceKey:       00000
BobKey:         00001
EveKey:         00011
AliceCheckBits: 10010
BobCheckBits:   00110

シミュレーション結果

実際にこの盗聴の検知はどれくらいの確率で検知出来るのかということについて理論値とシミュレーションした値を比較してみます.

AliceとBobが盗聴を検知出来ないパターンというのはAliceとBobが盗聴の検知に使用するビット列が一致する場合です.これがどれくらいの確率で起こるかというと,AliceとBobが盗聴の検知に使用するビットに対して,EveもAlice, Bobと同じ基底で測定していた場合+Eveが異なる基底で測定して状態が崩れたが,Bobの測定結果がAliceが元にしたビットと偶然一致する場合になります.

単一のビットに対してこれが起こる確率は

P(EveもAlice, Bobと同じ基底で測定していた場合) = 1/2

P(Eveが異なる基底で測定して状態が崩れたが,Bobの測定結果がAliceが元にしたビットと偶然一致する場合) = 1/2 * 1/2 = 1/4

なので

P(盗聴があったがAliceとBobが盗聴の検知に使用するビット) = P(EveもAlice, Bobと同じ基底で測定していた場合) + P(Eveが異なる基底で測定して状態が崩れたが,Bobの測定結果がAliceが元にしたビットと偶然一致する場合) = 3/4

となります.これがAliceとBobが盗聴の検知に使用するビット列全てのビットに対して起きるとAliceとBobは盗聴を検知出来ないのでその確率は(3/4)^CheckLengthとなります.これをCheckLength=5でやってみると,(3/4)5 = 0.2373...なので検知に使用するビットが5ビットだと2割強の確率でAliceとBobは盗聴を検知出来ないことになります.

実際にCheckLength=5で1000回シミュレーションを実行した結果は次の通りです.

Total:1000, Eavesdrop:773, NoEavesdrop:227

大体理論値に近い値が得られて正しくシミュレーション出来ているらしいことが確認できました.

終わりに

今回はQ#を使用して量子プログラミングをしてみました.シミュレーション時にC#から呼び出して使うのでC#と同じような文法かと思いきや結構違う部分も多いので割と戸惑います.調べてみるとどうやらユニットテストも書けるらしく本当に普通のプログラミングをするように量子プログラミングができるようになってきています.

まだQ#を触り始めたばかりなのでPR等あればどんどんお待ちしております.みなさんもどんどん量子プログラミングしていきましょう.