倭算数理研究所

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

Go で量子鍵配送 (Quantum Key Distribution) BB84 プロトコル

Go で量子コンピューティングシリーズ(目次)。 今回は量子鍵配送 (Quantum Key Distribution) の BB84 プロトコルの実装をしていきます。

【この記事の内容】

量子鍵配送 BB84 プロトコル

BB84 プロトコルの概要を見ておきましょう(文章で書くと分かりにくい...)。

  1. アリスがランダムなビット列(bool 値のスライス) bits, bases を生成し、bases を使って bits を qubit 列(qubit.Qubit のスライス)にエンコード(下記参照)し、量子チャネルを介してこの qubit 列をボブに送る。
  2. ボブはランダムなビット列 bases' を生成し、bases' を使って受け取った qubit 列をビット列 bits' にデコード(下記参照)する。
  3. (以下、基底情報のやりとりはいくつか種類があるようです*1)ボブは古典チャネルを介して bases' をアリスに送る
  4. アリスは受け取った bases' とエンコードに使った bases を比べて、真偽値が一致している位置の bits の値を鍵のビット列に追加する。 また、一致しているビット位置の情報*2を含む matches を生成し、古典チャネルを介してボブに送る。
  5. ボブは受け取った matches を使って、bits' のうち basesbases' の真偽値が一致したビットを鍵のビット列に追加する。
  6. 鍵のビット列が必要な長さになるまでこれを繰り返す。

古典チャネルで bitsbits' を直接送らないので鍵の安全性が保障されます。

アリスがビット列を qubit 列にエンコードする仕方は、bits, bases の各ビットに対して

bits \ bases 0 1
0  { \mid0\rangle }  { \mid+\rangle }
1  { \mid1\rangle }  { \mid-\rangle }

とします。 bases の値が0なら標準基底で、1ならアダマール基底でエンコードしていることになります。

ボブが qubit 列をビット列にデコードする仕方は、bases' の値が0, 1に対してそれぞれ標準基底、アダマール基底を用いて、受信した Qubit 列に対して量子力学的測定を行います。 得られた状態に対して、以下のビット値を割り当てます:

  •  { |0\rangle,\,|+\rangle \longrightarrow 0}
  •  { |1\rangle,\,|-\rangle \longrightarrow 1}

当然のことながら、エンコードとデコードで用いた基底が一致していれば同じビット値が得られます。

Go での実装

では Go での実装を見ていきましょう。 Alice と Bob の EstablishKey メソッド以外は機械的なコードです(import 文は省略):

package bb84

// NewAlice 関数は BB84 プロトコルのアリスを生成します。 n は鍵のビット数です。
func NewAlice(n int) *Alice { return &Alice{n, nil} }

type Alice struct{
  n int
  key qkd.Key
}

func (alice *Alice) Key() qkd.Key { return alice.key }

// NewBob は BB84 プロトコルのボブを生成します。 n は鍵のビット数です。
func NewBob(n int) *Bob { return &Bob{n, nil} }

type Bob struct{
  n int
  key qkd.Key
}

func (bob *Bob) Key() qkd.Key { return bob.key }

bb84.Alice の EstablishKey メソッド
では bb84.Alice の EstablishKey メソッドを実装しましょう。 引数の qkd.ChannelOnAlice は

  • Qch() chan<- []qubit.Qubit : Qubit の送信専用チャネル
  • ToBob() chan<- []bool : 古典ビットの送信専用チャネル
  • FromBob() <-chan []bool : 古典ビットの受信専用チャネル

の3つのチャネルが使用できます。 これを踏まえて上記の手順を Go コードとして実装すると以下のようになります(1回のやりとりで alice.n 個の Qubit、ビットを扱っていますが、これは実際には非効率です):

func (alice *Alice) EstablishKey(ch qkd.ChannelOnAlice){
  for len(alice.key) < alice.n {  // 鍵の長さが必要な長さになるまで繰り返す
    bits  := qkd.NewRandomBits(alice.n)
    bases := qkd.NewRandomBits(alice.n)

    ch.Qch() <- encode(bits, bases)

    bobBases := <- ch.FromBob()
    matches := matchBases(bases, bobBases)
    ch.ToBob() <- matches
    alice.key = qkd.AppendMatchingBit(alice.key, bits, matches, alice.n)
  }
}

qkd.NewRandomBits 関数は、引数で指定した長さの bool スライスを生成します。 まぁ実装はいいでしょう。 ちょっと助長な気もしますが、以下でその他の関数の実装を見ていきましょう。

encode 関数は、bases を使って bits を Qubit 列へエンコードします:

func encode(bits, bases []bool) []qubit.Qubit {
  var qubits = make([]qubit.Qubit, len(bits))
  for i, bit := range bits {
    if bases[i] {  // 1 -> encoding by the Hadamard basis
      // 1 -> |->
      // 0 -> |+>
      if bit {
        qubits[i] = qubit.NewMinus()
      } else {
        qubits[i] = qubit.NewPlus()
      }

    } else {  // 0 -> encoding by the standard basis
      // 1 -> |1>
      // 0 -> |0>
      if bit {
        qubits[i] = qubit.NewOne()
      } else {
        qubits[i] = qubit.NewZero()
      }
    }
  }
  return qubits
}

matchBases 関数は、引数の2つの bool スライスで、同じ位置の bool 値を比べて同じなら true を、そうでなければ false を設定した bool スライスを返します:

func matchBases(bases, bobsBases []bool) []bool {  // bobsBases は手順説明での bases'
  var match = make([]bool, len(bases))
  for i, basis := range bases {
    match[i] = basis == bobsBases[i]
  }
  return match
}

qkd.AppendMatchingBits 関数は、AppendMatchingBits(key, bits, matches []bool, max int) というシグニチャで、matches で true になっている位置の bits のビット値を key に追加します。 ただし、key の長さが max に達すれば処理を終わります:

func AppendMatchingBits(key, bits, matches []bool, max int) []bool {
  for i, match := range matches {
    if match {
      key = append(key, bits[i])
      if len(key) == max { return key }
    }
  }
  return key
}

スライスに対する append 関数と同じように、返り値を元の変数に代入する必要があります:

    alice.key = qkd.AppendMatchingBits(alice.key, bits, matches, alice.n)

まぁ、encode 関数以外は特に実装を見る必要のなさそうな関数ですが。

bb84.Bob の EstablishKey メソッド
次は bb84.Bob の EstablishKey メソッドを実装。 引数の qkd.ChannelOnBob は

  • Qch() <-chan []qubit.Qubit : Qubit の受信専用チャネル
  • ToAlice() chan<- []bool : 古典ビットの送信専用チャネル
  • FromAlice() <-chan []bool : 古典ビットの受信専用チャネル

の3つのチャネルが使用できます。 これを踏まえて上記の手順を Go コードとして実装すると以下のようになります:

func (bob *Bob) EstablishKey(ch qkd.ChannelOnBob){
  for len(bob.key) < bob.n {
    qbts := <-ch.Qch()
    bases := qkd.NewRandomBits(len(qbts))
    bits := decode(qbts, bases)
    ch.ToAlice() <- bases

    matches := <- ch.FromAlice()
    bob.key = qkd.AppendMatchingBits(bob.key, bits, matches, bob.n)
  }
}

qkd.NewRandomBit 関数、qkd.AppendMatchingBits 関数はアリスの場合と同じものです。 decode 関数は bases を使って Qubit 列をビット列へデコードします:

func decode(qbts []qubit.Qubit, bases []bool) []bool {
  bits := make([]bool, len(qbts))
  for i, qbt := range qbts {
    if bases[i] {  // 1 -> observing by the Hadamard basis
      // |-> -> 1
      // |+> -> 0
      bits[i] = qbt.Observe(basis.Hadamard()) == ket.Minus()
    }else{  // 0 -> observing by the standard basis
      // |1> -> 1
      // |0> -> 0
      bits[i] = qbt.Observe(basis.Standard()) == ket.One()
    }
  }
  return bits
}

まぁ特に難しくありませんね。

鍵の確立
上記のアリスとボブの実装を使って鍵を確立してみましょう。 前回の qkd.EstablishKeys 関数(追記しました)を使うと(bb84 パッケージの関数はパッケージ名を省略しています)

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

  n := 50

  // 鍵の確立
  aliceKey, bobKey := qkd.EstablishKeys(NewAlice(n), NewBob(n))

  fmt.Printf("アリスの鍵:%s\n", aliceKey)
  fmt.Printf("ボブの鍵 :%s\n", bobKey)
  fmt.Println(aliceKey.Equals(bobKey))

を実行すると

アリスの鍵:01101011111111001001000011110011110111000101000000
ボブの鍵 :01101011111111001001000011110011110111000101000000
true

などと出力され、同じ鍵が確立されていることが分かります。

盗聴

盗聴をするイヴのコードも簡単に見ておきましょう。 今回は送られてきた Qubit 列を測定するだけの簡単な盗聴です。 まずは盗聴をする Eavesdrop メソッド以外の定型的な部分:

package bb84

// NewEve は BB84 プロトコルのイヴを生成します。
func NewEve() *Eve { return &Eve{make(chan struct{})} }

type Eve struct {
  done chan struct{}
}

func (eve *Eve) Stop(){ eve.done <- struct{}{} }

Stop メソッドが呼ばれると done チャネルにメッセージを送ります。 以下の Eavesdrop メソッド内で、このメッセージを受け取ると盗聴を抜けるようにします。

イヴの Eavesdrop メソッドでは for 文と select 文でアリスとボブの通信を延々と盗聴します。 メソッドの引数である qkd.InternalOfChannel オブジェクトは

  • 量子チャネル
  • 古典チャネル(アリスからボブ)
  • 古典チャネル(ボブからアリス)

の3つに関して、From, To が付いた受信専用・送信専用のチャネルを取得できます。 各受信専用チャネルに対して case 文を書いて、必要なら何らかの処理を行った後、対応する送信専用チャネルへ結果を送ります。 以下のサンプルコードでは、Qubit 列以外は何もせずそのまま相手に送り、Qubit 列はランダムに標準基底もしくはアダマール基底で測定を行います(結果を使って鍵を取得したりはしません):

func (eve *Eve) Eavesdrop(ch *qkd.InternalOfChannel) {
  loop:
    for {
      select {
      case qubits := <-ch.QubitsFromAlice():
        // 各 Qubit を測定だけする
        bases := qkd.NewRandomBit(len(qbts))
        for i, qbt := range qbts {
          if bases[i] {
            qbt.Observe(basis.Hadamard())
          } else {
            qbt.Observe(basis.Standard())
          }
        }
        in.QubitsToBob() <- qubits

      case bits := <-ch.FromBob():
        // 何もせずにアリスに送る
        in.ToAlice() <- bits

      case bits := <-ch.FromAlice():
        // 何もせずボブに送る
        in.ToBob() <- bits

      case <-eve.done:
        // Stop メソッドが呼ばれると終了
        break loop
      }
    }
}

このイヴと前節までのアリス、ボブの実装を使って、盗聴されている場合の鍵の確立を行ってみましょう。 前回定義した qkd.EstablishKeysWithEavesdropping 関数(追記しました)を使って

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

  n := 50

  // 鍵の確立
  aliceKey, bobKey, _ := qkd.EstablishKeysWithEavesdropping(
      NewAlice(n), NewBob(n), NewEve())

  fmt.Printf("アリスの鍵:%s\n", aliceKey)
  fmt.Printf("ボブの鍵 :%s\n", bobKey)
  fmt.Println(aliceKey.Equals(bobKey))

を実行すると

アリスの鍵:01011111111110111000110011001110000010011011111100
ボブの鍵 :01011101111000101000000011011001000000011001110101
false

のように違った鍵が生成され、盗聴されていることが分かります。 もうちょっと定量的な分析は次回以降に。

【修正】

  • main コードで乱数の種を設定するようにしました。
  • イヴの盗聴で測定に使う基底を標準基底とアダマール基底からランダムに選ぶようにしました。
  • 定義済みの状態や基底の取得を変数アクセスからメソッドアクセスに変更したので、必要な箇所を修正しました。
  • 鍵を確立するコードを、前回の記事に追記した qkd.EstablishKeys, qkd.EstablishKeysWithEavesdropping 関数で書き直しました。

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

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

*1:アリスとボブがそれぞれ bases, bases' を送り合う方法などがあります。

*2:真偽が一致しているビットが true, そうでないビットが false となっているビット列。