倭算数理研究所

科学・数学・学習関連の記事を、「倭マン日記」とは別に書いていくのだ!

Go で量子鍵配送 (Quantum Key Distribution) もう少し B92 プロトコル

Go で量子コンピューティングシリーズ(目次)。 今回は前回見た B92 プロトコルに対して BB84 プロトコルでやったような分析をしていきます。 理論的な値は「『Quantum Computing: A Gentle Introduction』の演習問題を解く 2.11」で計算しています。

【この記事の内容】

長さ n の鍵を生成するために必要な qubit 数

理論的には、アリスとボブが n ビットの鍵を生成するには平均 4n 個の qubit が必要となります。 つまり qubit の使用効率は 25% です。 また、B92 プロトコルでは、盗聴されていると qubit の使用効率が上がる(破棄するビットが少なくなる)性質があり、この場合に n ビットの鍵を生成するのに必要な qubit の個数の平均値は 8n/3 個で、qubit の使用効率は  { 3/8 \fallingdotseq 37.5\% } となります。

前回のコードを少し修正してこれをシミュレーションしてみると確かにそうなりますが、ここではコードは省略。
github.com

盗聴に気づく確率

B92 プロトコルでは、鍵の長さが  { n } のとき盗聴に気づく確率  { P_n }

  { \displaystyle\begin{align*}
  P_n = 1 - \left(\frac{2}{3}\right)^n
\end{align*}}

で与えられます。 この確率が90%を始めて越えるのは  { n = 6 } のときです( { P_6 \fallingdotseq 0.912 })。

では、これをシミュレーションしてみましょう。 量子チャネルに送られた qubit を標準基底もしくはアダマール基底でランダムに測定するイヴは、BB84 プロトコルの分析に使ったものを使い回せます(qkd.NewObservingEve 関数でオブジェクトを取得できます)。 このイヴを使って、鍵の長さ (nKey) を1~10まで変えてアリスとボブが盗聴に気づく確率をシミュレーションすると(各鍵の長さで10000回試行)

  rand.Seed(time.Now().UnixNano())

  const nTry = 10000
  for nKey := 1; nKey <= 10; nKey++ {
    matched := 0
    for i := 0; i < nTry; i++ {
      aliceKey, bobKey, _ := qkd.EstablishKeysWithEavesdropping(
          NewAlice(nKey), NewBob(nKey), qkd.NewObservingEve())

      if aliceKey.Equals(bobKey) { matched++ }
    }
    fmt.Printf("%d: %.3f\n", nKey, 1-float64(matched)/float64(nTry))
    // 盗聴に気づく確率は 1 - (matched/nTry)
  }

(qkd.EstablishKeysWithEavesdropping 関数については『Go で量子鍵配送 (Quantum Key Distribution)』参照)結果は

1: 0.343
2: 0.552
3: 0.705
4: 0.806
5: 0.870
6: 0.912
7: 0.939
8: 0.961
9: 0.973
10: 0.982

となって、n = 6 あたりで90%になって理論値と概ね一致します。 gonum plot を使ってグラフにしておくと(少し鍵の長さを増やしてます)

f:id:waman:20171125231733p:plain

のようによく一致しているのが分かります。

イヴが正しい鍵のビット値を得る割合

次はイヴが盗聴した情報を基に鍵を生成したとき、どの程度鍵の正しいビット値を得ることができるかを見ていきます。 B92 プロトコルでは BB84 プロトコルの場合と違って、古典チャネルを盗聴した後でも各鍵ビットが確実に正しいかどうかは分からないので、鍵ビットの平均的な一致率だけを計算します。

イヴは盗聴した qubit を標準基底もしくはアダマール基底で測定し、測定結果が  { |0\rangle,\,|-\rangle } なら0、 { |1\rangle,\,|+\rangle } なら1とデコードして鍵のビット値を生成するとします(「『Quantum Computing: A Gentle Introduction』の演習問題を解く 2.11」参照)。

鍵を生成するイヴの実装は以下のようになります。 デコード方法が少し違うだけで、基本的には BB84 プロトコルの場合と同じです(鍵のビット値が確実に分かる場合をカウントしていない分だけ簡単):

// NewEve は盗聴した鍵を取得できるイヴを生成します。
func NewEve(n int) *Eve {
  return &Eve{n, nil, make(chan struct{})}
}

type Eve struct {
  n int
  key qkd.Key
  done chan struct{}
}

func (eve *Eve) Key() qkd.Key { return eve.key }
func (eve *Eve) Stop(){ eve.done <- struct{}{} }

func (eve *Eve) Eavesdrop(ch *qkd.InternalOfChannel) {
  var keyBits []bool
  loop:
    for {
      select {
      case qbts := <-ch.QubitsFromAlice():
        keyBits = make([]bool, len(qbts))
        bits := qkd.NewRandomBits(len(qbts))

        // 盗聴した qubit 列のデコード
        for i, qbt := range qbts {
          if bits[i] {
            keyBits[i] = qbt.ObserveInStandardBasis() == ket.One()
          } else {
            keyBits[i] = qbt.ObserveInHadamardBasis() == ket.Plus()
          }
        }
        ch.QubitsToBob() <- qbts

      case resultBits := <-ch.FromBob():
        // ボブが送った「結果ビット」が1の位置のビットのみを鍵ビットとして使用
        eve.key = qkd.AppendMatchingBits(eve.key, keyBits, resultBits, eve.n)
        ch.ToAlice() <- resultBits

      case bits := <-ch.FromAlice():
        ch.ToBob() <- bits

      case <-eve.done:
        break loop
      }
    }
}

このイヴの実装を用いて、次の2つの場合で盗聴した鍵ビットの一致率を見ていきます。

盗聴に気づいていない場合
まずは、アリスとボブの鍵が一致してイヴが盗聴していることに気づかない場合(BB84 プロトコルの場合ではこちらを後でシミュレーションしていたので注意)。 鍵の長さを10として100000回の試行を行うことにします(盗聴に気づかれない確率は10%以下なので、試行回数は実質10000回以下ですが):

  rand.Seed(time.Now().UnixNano())

  nTry := 100000
  nKey := 10
  n, conc := 0, 0  // n:試行回数、conc:鍵ビットの一致数
    for i := 0; i < nTry; i++ {
      aliceKey, bobKey, eveKey := qkd.EstablishKeysWithEavesdropping(
          NewAlice(nKey), NewBob(nKey), NewEve(nKey))

      if aliceKey.Equals(bobKey) {
      n++
      conc += aliceKey.Concordance(eveKey)
    }
  }

  fmt.Printf("アリスとイヴの鍵の一致率:%.3f\n", float32(conc)/float32(n*nKey))

これを実行すると

アリスとイヴの鍵の一致率:1.000

となって、盗聴されていない場合に限れば確実に正しい鍵が生成されることが分かります。 また、これは理論値と一致します。

盗聴に気づいているときも含む場合
次はアリスとボブの生成した鍵が異なっていて盗聴に気づくときも含めた場合。 今の場合は長さ100000の鍵を生成してアリス、ボブ、イブの鍵の一致率を比べれば充分です:

  rand.Seed(time.Now().UnixNano())

  nKey := 100000
  aliceKey, bobKey, eveKey := qkd.EstablishKeysWithEavesdropping(
      NewAlice(nKey), NewBob(nKey), NewEve(nKey))

  fmt.Printf("アリスとボブの鍵の一致率: %.3f\n", aliceKey.ConcordanceRate(bobKey))
  fmt.Printf("アリスとイヴの鍵の一致率: %.3f\n", aliceKey.ConcordanceRate(eveKey))
  fmt.Printf("ボブとイヴの鍵の一致率: %.3f\n", bobKey.ConcordanceRate(eveKey))

盗聴に気づく場合も含めるとアリスとボブの鍵も異なる(場合がある)ので、これらの一致率も表示するようにしています。 これを実行すると

アリスとボブの鍵の一致率: 0.670  // 理論値は 66.7%
アリスとイヴの鍵の一致率: 0.835  // 理論値は 5/6 ~ 83.3%
ボブとイヴの鍵の一致率: 0.835

となり、理論値をうまく再現していますね(アリスとイヴの鍵の一致率の理論値は「『Quantum Computing: A Gentle Introduction』の演習問題を解く 2.11」では導いていませんが)。

さて、これで量子鍵配送 B92 プロトコルの特徴がある程度数値的に分かりました。 古典チャネルでのやり取りが少ない分、コード的には BB84 プロトコルより B92 プロトコルの方が短く簡単ですが、B92 プロトコルでは qubit の使用効率が悪いので、どちらのプロトコルがいいかはパフォーマンス的な比較も必要かも知れませんね(やりませんが)。

Quantum Computing: A Gentle Introduction (Scientific and Engineering Computation)

Quantum Computing: A Gentle Introduction (Scientific and Engineering Computation)