量子暗号の基礎とその実用化に向けて
鶴丸豊広
三菱電機株式会社
＠IBIS2010, 2010/11/06

量子暗号の特徴
量子論を安全性の根拠とする「絶対に破れない」暗号技術
現代暗号 vs. 量子暗号
現代暗号 (AES, MISTY, Camellia, RSA暗号など)
高速：数百Mbps (S/W) ～ 数十Gbps (LSI)
計算量的安全性：現在の計算機を想定した解読に対しては安全だが，将来超高速な計算機が出現した時に解読される可能性あり．
量子暗号 （BB84方式, B92方式，DPSQKD方式ほか）
低速：数十kbps～1Mbps
絶対的安全性：どんなに計算機が進歩しても解読できない．
量子力学の公理から出発して、安全性を数学的に証明する• この講演ではもっぱら量子鍵配送（quantum key distribution, QKD）の、BB84方式（Bennett-Brassard 1984 protocol）についてのべる• とくに線型符号の果たす役割、および装置開発の状況を説明する。

市販の量子暗号装置• Clavris2
プロトコル：
光学系：
通信距離：
通信速度：(id Quantique社）
BB84, SARG04
Plug & Play方式>50 km
>1Kbps (@25km)

http://www.idquantique.com より• QPN 8505 (プロトコル:光学系：
通信距離:通信速度

MagiQ Technologies社)

BB84方式 with デコイ
不明～140km～100bps (?)

http://www.magiqtech.com より

三菱電機の量子暗号システム••••

プロトコル： BB84方式 with デコイ
光学系： 一方向通信
通信距離： > 50km
通信速度: >20kbps (@20km)• 携帯電話に秘密鍵を供給し、ワンタイムパッド通信を行うことが出来る• Tokyo QKD Networkでも活躍（後述）※NEC, NTT, 東芝欧州研なども試作機開発済（後述）量子暗号の無条件安全性 （イメージ）
量子暗号では、光の粒子（光子）に0,1の乱数を乗せて送る
この乱数値は 「測定すると必ず影響を受けて変化」 ← 量子論→ 盗聴があればノイズが増加し、あとで必ず露見する通信路を全て盗聴者にのっとられても安全という状況を実現するのが目的

0 1 0 0
光子
検出器

光子源

送信者

受信者
盗聴者

したがって通信路ノイズには敏感 → 通信距離と安全性に相関がある•長距離化 → 通信路ノイズ増加 → 盗聴ノイズとの区別がより困難になる•光を強める → 光子の数を増やすことに相当 → コピーが作れて盗聴が容易に•中継点での増幅も困難 …増幅には測定がともなう

「量子」に乱数ビットをのせる•

量子とは？
– この世の物質は全て量子であり、波としての性質と、粒子としての性質の両方を併せ持つ– 精密測定を行うと，量子としての性質が現れる→ 測定によって、状態が乱される•

この性質から– Eveが盗聴を行うと、Bobが受け取る信号に必ず変化がおきる– それを送信者と受信者が検出できる．

盗聴されている！

送信者

b = 01

盗聴されている！

0「量子」にデータを乗せて通信盗聴者

受信者

「量子」に乱数ビットをのせる• 通常用いる量子は「光」– 光は粒子である （これを「光子」(photon)と呼ぶ）– 我々が通常見ているのは粒々の集まり （粒子の数 ～ エネルギー）– 量子暗号では，粒子ひとつずつに０，１のデータを乗せる

通常の光通信b = 0

量子暗号通信
10
b = 0

送信者
※ １パルス辺り107個程度の光子

0

ファイバ中などを伝播

ファイバ中などを伝播
送信者

1

どうやって乱数ビットをのせるか？
符号化の方法： 偏光変調•

光は波であり，振動の方向が複数ある偏光•

この偏光を使って，光子ひとつずつに情報をのせる
b = 0

•

偏光

同様に偏光，1＋基底0偏光もある （装置を45度傾ける）

×基底ウォームアップ

通信路雑音がない場合のBB84プロトコル
量子暗号のデファクト方式は、BB84方式(Bennett-Brassard 1984 protocol)である。
まずはその簡単版として、通信路雑音がない場合をみてみる。基底をランダムにふって光子を送る
b=0

b=1＋基底受信者が正しい基底で観測してもエラーが起こる

×基底

基底をランダムに選んで光子を送る
確率

確率＝p50% ⇒ ×基底
50% ⇒ ＋基底＋基底でb = 0

盗聴者検出

確率＝1-p
確率＝１＋基底
で観測

受信者

×基底
で観測

確率＝１/２

確率＝１/２

送信者

を観測 （b=１）

を観測 （b=0）を観測 （b=0）を観測 （b=１） エラー！

盗聴者

盗聴者Eveは基底を知らずに観測⇒ 光子の偏光を変えてしまう盗聴者がいない場合の処理の流れ

b=0

b=1＋基底
×基底

10

1

1

10

1

100

Aliceの選んだ基底＋ × ＋ × × × ＋ × ＋ ＋

Aliceが実際に送る状態

Bobの選んだ基底＋ ＋ × × × × ＋ ＋ × ＋

Bobが観測する状態
Bobが読取った乱数11

基底の一致した部分のビットはふるい鍵（篩鍵）として保持1110101

量子通信が終了してから基底の情報を公開する

Aliceの生成した乱数0

基底の一致しない箇所は乱数となるので捨てる

盗聴者Eveがいる場合 (intercept/resend attack)Bobの選んだ基底
Bobが観測する状態
Bobの生成する乱数

1101

100× × × ＋ × ＋ ＋ ＋ × ×Eveが観測する状態
Eveが読み取った乱数

1＋ × ＋ × × × ＋ × ＋ ＋

Aliceが実際に送る状態

Eveが盗聴に用いる基底

0101

1

101

1

1

1＋ ＋ × × × × ＋ ＋ × ＋
盗聴検出
1 0 1

1111111

アリスとボブの基底が一致しているにもかかわらず、乱数が一致しない

Aliceの選んだ基底

1

イブが誤った基底で測定したために、状態が変化している

Aliceの生成した乱数

安全性証明前ページまでの攻撃の話は，ある特定の例(intercept/resend 攻撃)にたよった，直感的な説明にすぎない．
実際の量子暗号の安全性証明では，攻撃者Eveが，量子力学によって許されたあらゆる攻撃を行うと想定する．
さらに現実の装置や通信路では、盗聴者がいなくとも雑音がある現実の通信路にはノイズがある
量子暗号装置は、減衰や雑音の巣窟
敵がいないときでも通信路上でエラーが起こる
50kmでビット誤り率 ＞ 1%

Bobへの光パルスの到達確率≒1/1000
光ファイバ50kmで1/10程度に減衰
パルスあたりの平均光子数 = 0.1～0.5
単一光子源

送信者Alice

ビット誤りの主因は暗計数≒10-5

検出効率≒10%

光ファイバ

光子検出器

受信者Bob※暗計数(dark count) = 信号が来ていないのに、検出器が反応する事象

安全性証明で示したいこと
このノイズを全て敵によるものであると想定する (安全サイドに倒すことに相当)

敵Eveによる攻撃(雑音・消失)完全な単一光子源

完全な単一光子検出器

確率＝１で単一光子を放出

検出効率＝１

完全な通信路情報流出

減衰無し, デコヒーレンス無し

このときビット誤り率 e = 11%以下（※）であれば、盗聴者Eveに情報が漏洩する確率を任意に小さくできる
Mayers1998; Shor-Preskill 2000;※鍵生成レートR  1  2 H 2 e   0

量子誤り訂正符号を使った仮想的プロトコル
安全性証明の考え方•

まずは、証明のしやすいシンプルなプロトコルを考える– 実はこのプロトコルは盗聴者からすれば、現実のBB84プロトコルと等価•

このプロトコルの目的は、完全なBell状態をAliceとBobで共有することBell状態とは？
• EPR状態，最大もつれあい状態などとも呼ばれる
 :



1
0 A 0 B1 A1B2



• Alice, Bobの２者間で「共有できれば」、威力を発揮する。
•Alice, Bobの純粋状態なので、盗聴者Eveと相関がない•Alice, Bobが個別に測定すると、同じ乱数が得られる得られた乱数は、完全に秘密な暗号鍵となる

量子誤り訂正符号を使った仮想的プロトコル
しかしただ普通にBell状態をAliceからBobに送っても、盗聴や雑音により劣化する
量子誤り訂正符号で修復する

Calderbank-Shor-Steane符号 （CSS符号）••

量子誤り訂正符号の一種
通常のビット誤りに加えて、位相誤り訂正も行う

•

概要：
1.

(Calderbank-Shor 1996; Steane 1996)

以下の性質をもつ線型な誤り訂正符号の組 C1 ,C2 を用意する:

C2  C1 をみたし、かつ C1 ,C2 が良い符号である
2.

以下の演算子を用いて、量子誤りのシンドロームを測定する:
ビット誤り訂正：

位相誤り訂正： :      ,rz

r1zr  r1 , , rn   Crnz13.

 :      ,sxs1x

snxs  s1 , , sn   C2

 x , z 
パウリ行列

測定したシンドロームを元に、ビット誤り、位相誤りパターンを推定し、誤り訂正を行う

量子誤り訂正符号を使った仮想的プロトコル•Modified Lo-Chau protocol （in Shor-Preskill 2000）
1. AliceはBell状態（もつれ合い状態）を複数準備する
2. Aliceはその片割れに、Hadamard変換（＋，×基底の入れ換えに相当）をランダムに施してBobに送る
3. Bobの受信後Aliceは、どのもつれ合い状態にHamadard変換を施したかを公開する
4. Bobはそれらの状態に、逆Hadamard変換を施す
5. AliceとBobは、ランダムサンプリングにより、通信路でのったビット誤り率を推定する
6. CSS符号を用いて、ビット誤り、位相誤りの両方を訂正する
7. AliceとBobは、同一の基底でEPR対を測定し、結果を秘密鍵として共有する

Bell状態
量子暗号装置

量子暗号装置

送信者 (Alice)

受信者 (Bob)

量子誤り訂正符号を使った仮想的プロトコル•

Modified Lo-Chau protocol （in Shor-Preskill 2000）
1. AliceはBell状態（もつれ合い状態）を複数準備する
2. Aliceはその片割れに、Hadamard変換（＋，×基底の入れ換えに相当）をランダムに施してBobに送る
3. Bobの受信後Aliceは、どのもつれ合い状態にHamadard変換を施したかを公開する
4. Bobはそれらの状態に、逆Hadamard変換を施す
5. AliceとBobは、ランダムサンプリングにより、通信路でのったビット誤り率を推定する
6. CSS符号を用いて、ビット誤り、位相誤りの両方を訂正する
7. AliceとBobは、同一の基底でEPR対を測定し、結果を秘密鍵として共有する

量子暗号装置
送信者 (Alice)

量子暗号装置

通信路雑音・ 受信者 (Bob)
Eveの盗聴量子誤り訂正符号を使った仮想的プロトコル•

Modified Lo-Chau protocol （in Shor-Preskill 2000）
1. AliceはBell状態（もつれ合い状態）を複数準備する
2. Aliceはその片割れに、Hadamard変換（＋，×基底の入れ換えに相当）をランダムに施してBobに送る
3. Bobの受信後Aliceは、どのもつれ合い状態にHamadard変換を施したかを公開する
4. Bobはそれらの状態に、逆Hadamard変換を施す
5. AliceとBobは、ランダムサンプリングにより、通信路でのったビット誤り率を推定する
通信路雑音だけでなく、
6. CSS符号を用いて、ビット誤り、位相誤りの両方を訂正する
Eveによる盗聴の効果
7. AliceとBobは、同一の基底でEPR対を測定し、結果を秘密鍵として共有する

もろともQECCで訂正

量子暗号装置
送信者 (Alice)

量子暗号装置

通信路雑音・ 受信者 (Bob)
Eveの盗聴量子誤り訂正符号を使った仮想的プロトコル•

Modified Lo-Chau protocol （in Shor-Preskill 2000）
1. AliceはBell状態（もつれ合い状態）を複数準備する
2. Aliceはその片割れに、Hadamard変換（＋，×基底の入れ換えに相当）をランダムに施してBobに送る
3. Bobの受信後Aliceは、どのもつれ合い状態にHamadard変換を施したかを公開する
4. Bobはそれらの状態に、逆Hadamard変換を施す
5. AliceとBobは、ランダムサンプリングにより、通信路でのったビット誤り率を推定する
6. CSS符号を用いて、ビット誤り、位相誤りの両方を訂正する
7. AliceとBobは、同一の基底でEPR対を測定し、結果を秘密鍵として共有する
秘密鍵
秘密鍵測定

完全なBell状態測定

量子暗号装置

量子暗号装置

送信者 (Alice)

受信者 (Bob)

量子誤り訂正符号を使った仮想的プロトコル
量子暗号の鍵生成レート ＝ CSS符号の符号化率であり、古典符号 C1 , C2 の性能できまる AB

Alice, Bobそれぞれn キュービットずつ

ビット誤り訂正rec AB

古典符号 C1 のシンドロームビットと同じ数のキュービットを消費 （ f b nH 2 e  とおく）n1 f b H 2 e 
キュービットずつ

位相誤り訂正ent AB

盗聴や通信路ノイズで傷ついたもつれあい状態（ビット誤り率 = 位相誤り率 = e とする）



古典符号 C2 のシンドロームビットと同じ数のキュービットを消費 （ f p nH 2 e  とおく）
（一般に f b , f p  1, 理想的には f b  f p  1 ）n1  f b H 2 e   f p H 2 e  個のBell状態 （＝秘密鍵ビット数）現実のBB84プロトコル
議論の詳細は省くが、いままでの仮想プロトコルを盗聴者からみた場合、現実のBB84プロトコルと区別がつかない （Shor-Preskill 2000）
BB84プロトコル （通信路雑音あり）
1.
2.
3.
4.
5.

※ ここまでは通信路雑音
AliceはBobに、基底をランダムに選んで光を送るなしの場合
Bobは基底をランダムに選んで光を測定し、結果を記録 （ふるい鍵）と同じサンプルビットをランダムに選び、位相誤り率を推定する。
誤り率が高すぎたら(約11%以上)、プロトコルを中止する。
Alice, Bobは符号C1を用いてビット誤り訂正を行う （訂正鍵）
Alice, Bobは符号C2による同値類C1/C2をとる （秘密鍵）

量子暗号装置
送信者 (Alice)

Eveによる攻撃

量子暗号装置
受信者 (Bob)

再掲

b=0

b=1＋基底ふるい鍵生成までの流れ

×基底

101

1

101

100

Aliceの選んだ基底＋ × ＋ × × × ＋ × ＋ ＋

Aliceが実際に送る状態

Bobの選んだ基底＋ ＋ × × × × ＋ ＋ × ＋

Bobが観測する状態
Bobが読取った乱数

111110101

量子通信が終了してから基底の情報を公開する

Aliceの生成した乱数0

このビット列をPCや回路でデータ処理する
基底の一致した部分のビットは基底の一致しない箇所は（誤り訂正、秘匿性増強）
ふるい鍵（篩鍵）として保持乱数となるので捨てる現実のBB84プロトコル
鍵蒸留処理： ふるい鍵に対し、以下のデータ処理をPCやFPGA上で行う
100110100101

ふるい鍵 ： 検出器から出てきたままのビット列，( e = ビット誤り率)
n ビット①誤り訂正符号 C1によるビット誤り訂正
100101011

訂正鍵： 一部の情報がまだ盗聴者に漏洩している,n1 f p H 2 e  ビット② 得られた符号語 x∈C1に対し、符号C2で同値類をとる

この操作を「秘匿性増強」(privacy amplification)とよぶ（敵に漏れた情報量 NH 2 e  ビット分を除去していると解釈）
1001010

秘密鍵： 実際に暗号通信に使う鍵，最終鍵ともよぶ



 ビット

同値類C1/C2の元， n 1  f b H 2 e   f p H 2 e 

量子暗号における古典CSS符号•

以下、量子CSS符号の構成にもちいる線型符号の組C1, C2を、「古典CSS符号」と呼ぶことにする•

量子CSS符号の要請から、C1, C2には以下の条件が必要– C2 ⊂C1– C1およびC2⊥が良い符号である （符号化率が高い）•

ただし量子暗号に利用するときは、位相誤り訂正用のC2⊥にさらに「注釈」がいくつか加わる– 有利な注釈： ランダム符号が本当に使える– 不利な注釈： 符号のビット長が巨大でないとならない （有限長効果）

量子暗号における古典CSS符号
C2⊥に対する有利な注釈
– C2 を用いた位相誤り訂正は実際には行わず、C2の同値類をとるのみ。

– したがって効率的な復号アルゴリズムは不要。
情報理論的に C2 が復号可能でありさえすればよい。
– ゆえにランダム符号でもOK （符号C1内に符号C2を毎回ランダムにとる）
このとき符号 C2 のシンドローム長を、最小の値 nH 2 e にできる。
（ fp = 1に相当 ）量子暗号における古典CSS符号
C2⊥に対する有利な注釈 (つづき)•

C1で復号した情報ベクトルに、線型なuniversal hash functionをかければ安全(Renner 2005)

Universal Hash Function• 以下の条件を満たす関数の集合 F   f r r  I , f r : A  B をε-almost universal2 hash functionとよぶAx  y, Pr f r x   f r  y   B
• 1-almost …を単にuniversal hash functionと呼ぶ。例：Toeplitz行列演算。

•

これをCSS符号の言葉でいうと：– C2をC1内に1-almost universal2符号族としてとることに相当– そのとき、その双対符号C2⊥の集合は、2-almost universal2符号族となる– ε-almost universal2符号族は、ランダム符号と類似の復号性能を持つ
ε-almost universal2符号族• 符号 C1  F2n に含まれる符号の集合 C 2  C2 r  C1 r  I , dim C2 r  t が以下を満たすとき、C 2 を(C1の部分）ε-almost universal2符号族とよぶx  F2n  C1 , Prx  C2 r   2t n 

• このとき, 写像C1→C1/C2はε-almost universal2 hash functionとなる.
(M. Hayashi 2007; T.T. and M. Hayashi, in preparation)量子暗号における古典CSS符号C2⊥に対する不利な注釈•

有限長効果 (M. Hayashi 2007)– 位相誤り訂正を実行しないので、復号失敗を直接検証できない– 位相誤り率epは、実はサンプルビットの誤り率psmpから推定するもの– 推定の統計誤差を抑えるためには、C2⊥のビット長を大きく取る必要がある
数値例
サンプルビットはランダムな非復元抽出であり、超幾何分布に従う
 n  l  Pk c   kc c n  l k

仮にC1のブロック長n, サンプルビット数 l をともに1000とすると，本来の誤り率ep=5%に対し，確率6%以上で推定誤差1%以上

Pr psmp  4%  6%

– 鍵生成レートを無限大と遜色ないレベルにするためには、
C2⊥のビット長 n を1Mbit以上にとる必要があるとされる(Scarani-Renner 2008)

高速秘匿性増強アルゴリズム（FFTによるToeplitz行列演算）
As a solution to the finite size effect† of key distillation,
we developed a new efficient algorithm for privacy amplification†Due to statistical fluctuations of phase error, block lengths of privacy
amplification must exceed 106 (Hayashi 2007; Scarani and Renner 2008)
1e+7Sifted KeyError Correction
Key Distillation
Privacy Amp.
Secret Key

Running TimeQKD Device（msec）

1e+6Naïve AlgorithmO(n2)100000
10000
1000
100
10
1
0.1
0.01

FFT-based AlgorithmO(n*log(n))

0.001
0.0001
10Efficient multiplication algorithm of Toeplitz matrices via FFT,
with an almost constant running time per bit⇒ Privacy amplification on software for block size n>106

100

1000

10000

510610Block Size n(bit)Running time of PA on software

Tokyo QKD Network•

国内外各社の量子暗号装置を接続し、東京都内の既設光ファイバ上に、量子暗号ネットワークを構築– 情報通信研究機構（NICT）の呼びかけにより、以下の機関が参加
国内： NEC、三菱電機、ＮＴＴ、
海外： 東芝欧州研（英）、id Quantique社（スイス）、All Vienna（オーストリア）– ４拠点： 大手町、白山、本郷、小金井– 古典中継（※）により、総延長200km以上
参考：
UQCCホームページ
http://www.uqcc2010.org/※各ノードは信頼できるとし秘密鍵をリレーした

Tokyo QKD Network•

量子暗号で共有した鍵で暗号化し、動画配信（テレビ会議）を実施– 記者発表（10月14日）、および国際会議UQCCでのデモ（18日）•

通信速度： 数kbps～300kbps （通信路により異なる）

UQCCホームページ
http://www.uqcc2010.org/ より

通信デモの様子
UQCC 2010 メイン会場

通信デモの様子
UQCC 2010 メイン会場

通信デモの様子
各社装置の状況を動画中継

NEC

三菱電機

NTT

NICT(超伝導検出器)

通信デモの様子
各社装置の状況を動画中継

東芝欧州研(イギリス)

id Quantique（スイス）

All Vienna（オーストリア）

Tokyo QKD Network
実際の装置の様子 （大手町）

東芝欧州研
Alice

NEC
Alice
三菱Alice

三菱Bob

まとめ•

量子暗号は「絶対に破られない暗号」であり、なおかつすでに実用化レベルに達している– 量子暗号≠量子計算機– 海外ベンチャー企業による市販品、内外各社による試作品– Tokyo QKD Networkにおける接続デモ•

その安全性証明において、誤り訂正符号が重要である– 量子誤り符号（量子CSS符号）のコンポーネントとして、従来型の誤り訂正符号（古典CSS符号）がある（C2⊂C1かつC1,C2⊥がよい符号）– 古典CSS符号の性能が量子暗号装置の性能を左右する•

一方で、量子暗号装置において古典CSS符号を実際に使う必要はない– 量子暗号においては、C2⊥による位相誤り訂正を実行しないので、ランダム符号やユニバーサルハッシュ関数で置き換えられる– 結果として、通常のビット誤り訂正を行った後に、ユニバーサルハッシュ関数による秘匿性増強を行うことと等価になった