倭算数理研究所

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

Go で量子鍵配送 (Quantum Key Distribution)

Go で量子コンピューティングシリーズ(目次)。 次回から何回かで量子鍵配送 (qkd: quantum key distribution) を3種類ほど実装していく予定ですが、今回はそれらに共通する型などを見ていきます。 実装は直接的には量子鍵配送に関係なのでスルーします。

【この記事の内容】

qkd.Key 型

量子鍵配送で確立する鍵は単なる古典ビット列なので、Go では bool 値スライスとします。 ただし、ユーティリティメソッドを定義したいので、別名をつけておきます:

package qkd

type Key []bool

// String メソッドは Key をビット列を表す文字列("10110..." のようなもの)に変換して返します。
func (key Key) String() string { ... }

// 2つの Key のビットの一致率を返します。 Key の長さが異なるとパニックを起こします。
func (key1 Key) ConcordanceRate(key2 Key) float32 { ... }

ConcordanceRate メソッドは2つの鍵のビットの一致率を返します。 2つの鍵の長さが異なるパニックを起こします:

  key0 := Key([]bool{true, true, true, true})
  key1 := Key([]bool{true, false, false, true})

  fmt.Println(key0.ConcordanceRate(key1))  // 0.5

  key2 := Key([]bool{true, true, false})
  key0.ConcordanceRate(key2)  // パニック

qkd.Channel インターフェース

量子鍵配送ではアリス (Alice) とボブ (Bob) がチャネルを通して秘密鍵を確立することを目的とします。 Qubit はアリスからボブへという方向だけで送ることができ(アリスは送信、ボブは受信のみ可)、古典ビットは双方向で送受信ができます。 図にすると以下のようになります:

f:id:waman:20171021113447p:plain

当初、Qubit や古典ビットを送るチャネルを Go のチャネルそのままで実装しようとしたのですが、そこそこゴチャゴチャしそうなので qkd.Channel インターフェースにまとめて扱うことにします:

package qkd

type Channel interface {
  OnAlice() ChannelOnAlice
  OnBob()   ChannelOnBob
  Close()
}

// NewChannel 関数は新しい Channel を生成します。
func NewChannel() Channel { ... }

type ChannelOnAlice interface {
  Qch()     chan<- []qubit.Qubit
  ToBob()   chan<- []bool
  FromBob() <-chan []bool
}

type ChannelOnBob interface {
  Qch()       <-chan []qubit.Qubit
  ToAlice()   chan<- []bool
  FromAlice() <-chan []bool
}

qkd.Channel オブジェクトは qkd.NewChannel 関数で取得します。 ChannelOnAlice, ChannelOnBob 型は Channel の OnAlice, OnBob メソッドから取得でき、それぞれ Alice, Bob が送信または受信できる Go チャネルを取得するメソッドが定義されています。 具体的な使い方は各量子鍵配送の実装回で見ていきます。

qkd.Alice, qkd.Bob インターフェース

アリスとボブを表すインターフェースは、鍵を取得する Key メソッドと鍵を確立する EstablishKey メソッドが定義されています:

package qkd

type Alice interface {
  Key() Key
  EstablishKey(ch ChannelOnAlice)
}

type Bob interface {
  Key() Key
  EstablishKey(ch ChannelOnBob)
}

EstablishKey メソッドの引数はアリスとボブで異なります。

鍵の確立

以上の型を使って、量子鍵配送で鍵を確立する main コードを見ていきましょう。 qkd.Alice, qkd.Bob オブジェクトはそれぞれ NewAlice, NewBob 関数で生成するとします(これらの関数は通常別パッケージに定義されますが、ここではパッケージ名を省略しています。 また、引数に鍵のビット数を指定するとします)。 単純に鍵を確立するだけなら

  rand.Seed(time.Now().UnixNano())  // 乱数の種を設定

  n := 50  // 鍵のビット数
  ch := qkd.NewChannel()
  defer ch.Close()

  alice := NewAlice(n)
  go alice.EstablishKey(ch.OnAlice())

  bob := NewBob(n)
  go bob.EstablishKey(ch.OnBob())

とできますが、確立した鍵を取得して比べたりするには、それぞれのゴルーチンが終了するのを待つ必要があります:

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

  n := 50  // 鍵のビット数
  ch := qkd.NewChannel()
  defer ch.Close()
  done := make(chan struct{}, 2)

  // アリス
  alice := NewAlice(n)
  go func(){
    alice.EstablishKey(ch.OnAlice())
    done <- struct{}{}
  }()

  // ボブ
  bob := NewBob(n)
  go func(){
    bob.EstablishKey(ch.OnBob())
    done <- struct{}{}
  }()

  // 鍵を確立するゴルーチンが終了するのを待つ
  <-done
  <-done

  // 鍵を取得して比べる
  aliceKey, bobKey := alice.Key(), bob.Key()
  fmt.Printf("Alice's key: %s\n", aliceKey)
  fmt.Printf("Bob's key  : %s\n", bobKey)
  fmt.Println(aliceKey.String() == bobKey.String())

鍵の確立は定型文なので、アリスとボブを与えてそれらの確立した鍵を返す qkd.EstablishKeys 関数を定義しておきましょう:

package qkd

func EstablishKeys(alice Alice, bob Bob) (aliceKey, bobKey Key) {
  ch := NewChannel()
  defer ch.Close()
  done := make(chan struct{}, 2)

  go func(){
    alice.EstablishKey(ch.OnAlice())
    done <- struct{}{}
  }()

  go func(){
    bob.EstablishKey(ch.OnBob())
    done <- struct{}{}
  }()

  <-done
  <-done

  aliceKey = alice.Key()
  bobKey = bob.Key()
  return
}

この qkd.EstablishKeys 関数を使うと、鍵を確立して比較するコードは以下のように書けます:

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

  n := 50  // 鍵の長さ
  aliceKey, bobKey := qkd.EstablishKeys(NewAlice(n), NewBob(n))

  fmt.Printf("Alice's key: %s\n", aliceKey)
  fmt.Printf("Bob's key  : %s\n", bobKey)
  fmt.Println(aliceKey.Equals(bobKey))  // true

あとはアリスとボブの実装を作って NewAlice, NewBob 関数で返すだけです。

qkd.InsecureChannel 型と qkd.Eve インターフェースと盗聴

量子鍵配送は盗聴 (eavesdrop) されても鍵が漏れず、かつ盗聴されていることがわかるという性質があるのですが、それらをシミュレートするために盗聴可能なチャネル qkd.InsecureChannel と盗聴を行う qkd.Eve という型を定義しています。

qkd.InsecureChannel は Channel を実装し、Internal メソッドで返されるオブジェクトを介して、チャネルに送られた Qubit、古典ビットを取得することができます:

package qkd

 // InsecureChannel 型は Channel と違って構造体として定義しています。
type InsecureChannel struct { ... } 

// NewInsecureChannel 関数は InsecureChannel オブジェクトを生成します(ポインタを返す)。
func NewInsecureChannel() *InsecureChannel { ... }

// *InsecureChannel は Channel を実装します。
func (ich *InsecureChannel) OnAlice() ChannelOnAlice { ... }
func (ich *InsecureChannel) OnBob() ChannelOnBob { ... }
func (ich *InsecureChannel) Close() { ... }

// Internal メソッドは InsecureChannel 内を送られた Qubit、古典ビットを取得できる
// InternalOfChannel オブジェクト(へのポインタ)を返します
func (ich *InsecureChannel) Internal() *InternalOfChannel { ... }

// 使い方は量子鍵配送の実装回で。
type InternalOfChannel struct { ... }

盗聴を実行するのはイヴで、以下の qkd.Eve インターフェースを実装します:

package qkd

type Eve interface {
  Eavesdrop(ch *InternalOfChannel)
  Stop()
}

Eavesdrop メソッドの引数は InsecureChannel 型の Internal() メソッドの返り値です。 Stop メソッドは盗聴(しているゴルーチン)を止めます。

これらを踏まえて、NewEve 関数(パッケージ省略)で生成された qkd.Eve オブジェクトを用いて量子鍵配送を盗聴する main コードは以下のようになります:

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

  n := 50
  ch := qkd.NewInsecureChannel()  // 安全でないチャネルを生成
  defer ch.Close()
  done := make(chan struct{}, 2)

  // イヴを生成して盗聴開始
  eve := NewEve()  // 引数がある場合もある
  go eve.Eavesdrop(ch.Internal())

  // アリス
  alice := NewAlice(n)
  go func(){
    alice.EstablishKey(ch.OnAlice())
    done <- struct{}{}
  }()

  // ボブ
  bob := NewBob(n)
  go func(){
    bob.EstablishKey(ch.OnBob())
    done <- struct{}{}
  }()

  <-done
  <-done
  eve.Stop()  // イヴを停止

  aliceKey, bobKey := alice.Key(), bob.Key()
  fmt.Printf("Alice's key: %s\n", aliceKey)
  fmt.Printf("Bob's key  : %s\n", bobKey)
  fmt.Println(aliceKey.String() == bobKey.String())

アリスとボブに関連するコードは盗聴がない場合から変更されていません。 このコードも定型文なので、qkd.EstablishKeysWithEavesdropping 関数としてまとめておきましょう:

package qkd

type KeyContainer interface{
  Key() Key
}

func EstablishKeysWithEavesdropping(
    alice Alice, bob Bob, eve Eve) (aliceKey, bobKey, eveKey Key) {

  ch := NewInsecureChannel()
  defer ch.Close()
  done := make(chan struct{}, 2)

  // イヴ
  go eve.Eavesdrop(ch.Internal())

  // アリス
  go func(){
    alice.EstablishKey(ch.OnAlice())
    done <- struct{}{}
  }()

  // ボブ
  go func(){
    bob.EstablishKey(ch.OnBob())
    done <- struct{}{}
  }()

  <-done
  <-done
  eve.Stop()

  aliceKey = alice.Key()
  bobKey = bob.Key()
  if e, ok := eve.(KeyContainer); ok { eveKey = e.Key() }
  return
}

イヴが Key メソッドを持っていれば(KeyContainer インターフェースを実装していれば)、第3返り値でその鍵を返します。 そうでなければ nil が返されます。 この関数を使って、イヴが盗聴をしている中でアリスとボブが鍵を確立するコードは以下のようになります:

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

  n := 50  // 鍵の長さ
  aliceKey, bobKey, _ := qkd.EstablishKeysWithEavesdropping(
      NewAlice(n), NewBob(n), NewEve())

  fmt.Printf("Alice's key: %s\n", aliceKey)
  fmt.Printf("Bob's key  : %s\n", bobKey)
  fmt.Printf("Concordance rate: %f\n", aliceKey.ConcordanceRate(bobKey))
  fmt.Println(aliceKey.Equals(bobKey))  // (高確率で)false

あとはアリスとボブに加えて、qkd.Eve インターフェースの実装を作って NewEve 関数で返すだけです。

これで量子鍵配送の周辺部分の準備は完了。 あとはアリスとボブの量子鍵配送アルゴリズム、イヴの盗聴のアルゴリズムを書けばいいだけです。 これらは次回以降に。

【修正】

  • Eavesdrop のスペルが間違っていたので修正しました(確認したつもりでしたが ^^;)。
  • main コードの最初で乱数の種を設定するようにしました。
  • Key 型に ConcordanceRate メソッドを追加しました。
  • Alice, Bob, Eve のインスタンスを渡して鍵を確立して返す qkd.EstablishKeys 関数と qkd.EstablishKeysWithEavesdropping 関数を追加しました(qkd.EstablishKey 関数は削除しました)。

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

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