PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

えのみつだ
5 years ago
Views:

1 量子暗号の基礎とその実用化に向けて 2010/11/06

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

3 市販の量子暗号装置 Clavris 2 ( id Quantique 社 ) プロトコル : 光学系 : 通信距離 : 通信速度 : BB84, SARG04 Plug & Play 方式 >50 km >1Kbps (@25km) より QPN 8505 ( MagiQ Technologies 社 ) プロトコル : BB84 方式 with デコイ光学系 : 不明通信距離 : ~140km 通信速度 ~100bps (?) より

4 三菱電機の量子暗号システムプロトコル : BB84 方式 with デコイ光学系 : 一方向通信通信距離 : > 50km 通信速度 : >20kbps (@20km) 携帯電話に秘密鍵を供給しワンタイムパッド通信を行うことが出来る Tokyo QKD Network でも活躍 ( 後述 ) NEC, NTT, 東芝欧州研なども試作機開発済 ( 後述 )

5 量子暗号の無条件安全性 ( イメージ ) 量子暗号では光の粒子 ( 光子 ) に0,1の乱数を乗せて送るこの乱数値は測定すると必ず影響を受けて変化量子論盗聴があればノイズが増加しあとで必ず露見する通信路を全て盗聴者にのっとられても安全という状況を実現するのが目的送信者光子源光子検出器受信者盗聴者したがって通信路ノイズには敏感通信距離と安全性に相関がある長距離化通信路ノイズ増加盗聴ノイズとの区別がより困難になる光を強める光子の数を増やすことに相当コピーが作れて盗聴が容易に中継点での増幅も困難増幅には測定がともなう

6 量子に乱数ビットをのせる量子とは? この世の物質は全て量子であり波としての性質と粒子としての性質の両方を併せ持つ精密測定を行うと, 量子としての性質が現れる測定によって状態が乱されるこの性質から Eve が盗聴を行うと Bob が受け取る信号に必ず変化がおきるそれを送信者と受信者が検出できる. 盗聴されている! 盗聴されている! b = 送信者量子にデータを乗せて通信盗聴者受信者

7 量子に乱数ビットをのせる通常用いる量子は光光は粒子である ( これを光子 (photon) と呼ぶ ) 我々が通常見ているのは粒々の集まり ( 粒子の数 ~ エネルギー ) 量子暗号では, 粒子ひとつずつに 0,1 のデータを乗せる通常の光通信 b = 量子暗号通信 b = 送信者ファイバ中などを伝播送信者ファイバ中などを伝播 1 パルス辺り 10 7 個程度の光子

8 どうやって乱数ビットをのせるか? 符号化の方法 : 偏光変調光は波であり, 振動の方向が複数ある偏光この偏光を使って, 光子ひとつずつに情報をのせる b = 偏光 + 基底同様に偏光, 偏光もある ( 装置を 45 度傾ける ) 基底

9 ウォームアップ通信路雑音がない場合の BB84 プロトコル量子暗号のデファクト方式は BB84 方式 (Bennett-Brassard 1984 protocol) であるまずはその簡単版として通信路雑音がない場合をみてみる

10 基底をランダムにふって光子を送る b=0 b=1 + 基底基底基底をランダムに選んで光子を送る確率 50% 基底 50% + 基底受信者が正しい基底で観測してもエラーが起こる確率 =p 盗聴者検出を観測 (b=1) + 基底で b = 0 + 基底で観測確率 =1-p =1 を観測 (b=0) 受信者基底で観測確率 =1/2 を観測 (b=0) 確率 =1/2 送信者を観測 (b=1) エラー! 盗聴者盗聴者 Eveは基底を知らずに観測光子の偏光を変えてしまう

11 量子通信が終了してから基底の情報を公開する盗聴者がいない場合の処理の流れ + 基底基底 b=0 b=1 Alice の生成した乱数 Aliceの選んだ基底 Aliceが実際に送る状態 Bobの選んだ基底 Bobが観測する状態 Bobが読取った乱数基底の一致した部分のビットはふるい鍵 ( 篩鍵 ) として保持基底の一致しない箇所は乱数となるので捨てる

12 アリスとボブの基底が一致している盗聴者 Eve がいる場合 (intercept/resend attack) Aliceの生成した乱数た1 め0 ブ Aliceの選んだ基底にが誤状っ態たが基変底化でEveが観測する状態し測て定1 い0 しるたBobの選んだ基底 Bobが観測する状態盗聴検出イBobの生成する乱数 Alice が実際に送る状態 Eve が盗聴に用いる基底 Eve が読み取った乱数かわら乱数ないにもかずが一致し

13 安全性証明前ページまでの攻撃の話は, ある特定の例 (intercept/resend 攻撃 ) にたよった, 直感的な説明にすぎない. 実際の量子暗号の安全性証明では, 攻撃者 Eve が, 量子力学によって許されたあらゆる攻撃を行うと想定する. さらに現実の装置や通信路では盗聴者がいなくとも雑音がある

14 現実の通信路にはノイズがある量子暗号装置は減衰や雑音の巣窟敵がいないときでも通信路上でエラーが起こる Bob への光パルスの到達確率 1/1000 光ファイバ 50km で 1/10 程度に減衰パルスあたりの平均光子数 = 0.1~0.5 検出効率 10% 50km でビット誤り率 > 1% ビット誤りの主因は暗計数 10-5 単一光子源送信者 Alice 光ファイバ光子検出器受信者 Bob 暗計数 (dark count) = 信号が来ていないのに検出器が反応する事象

15 安全性証明で示したいことこのノイズを全て敵によるものであると想定する ( 安全サイドに倒すことに相当 ) 完全な単一光子源確率 =1 で単一光子を放出情報流出敵 Eve による攻撃 ( 雑音消失 ) 完全な通信路完全な単一光子検出器減衰無し, デコヒーレンス無し検出効率 =1 このときビット誤り率 e = 11% 以下 ( ) であれば盗聴者 Eve に情報が漏洩する確率を任意に小さくできる Mayers1998; Shor-Preskill 2000; 鍵生成レート R 1 2H 2e 0

16 量子誤り訂正符号を使った安全性証明の考え方仮想的プロトコルまずは証明のしやすいシンプルなプロトコルを考える実はこのプロトコルは盗聴者からすれば現実の BB84 プロトコルと等価このプロトコルの目的は完全な Bell 状態を Alice と Bob で共有すること Bell 状態とは? EPR 状態, 最大もつれあい状態などとも呼ばれる 1 : A B A B 2 Alice, Bobの2 者間で共有できれば威力を発揮する Alice, Bob の純粋状態なので盗聴者 Eve と相関がない Alice, Bob が個別に測定すると同じ乱数が得られる得られた乱数は完全に秘密な暗号鍵となる

17 量子誤り訂正符号を使った仮想的プロトコルしかしただ普通に Bell 状態を Alice から Bob に送っても盗聴や雑音により劣化する Calderbank-Shor-Steane 符号 (CSS 符号 ) 量子誤り訂正符号の一種通常のビット誤りに加えて位相誤り訂正も行う概要 : C 1,C 2 1. 以下の性質をもつ線型な誤り訂正符号の組を用意する : 2. 以下の演算子を用いて量子誤りのシンドロームを測定する : r z r 量子誤り訂正符号で修復する C2 C 1 をみたしかつ 1 n : r r z z 1, n 1 r, r C, C 1,C 2 が良い符号であるビット誤り訂正 : 位相誤り訂正 : (Calderbank-Shor 1996; Steane 1996) s s x x s n 1 sn : s1,, s C2 3. 測定したシンドロームを元にビット誤り位相誤りパターンを推定し誤り訂正を行う x, x, z パウリ行列

18 量子誤り訂正符号を使った仮想的プロトコル 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)

19 量子誤り訂正符号を使った仮想的プロトコル 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) 通信路雑音 Eve の盗聴量子暗号装置受信者 (Bob)

20 量子誤り訂正符号を使った仮想的プロトコル 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による盗聴の効果もろともQECCで訂正 7. Alice と Bob は同一の基底で EPR 対を測定し結果を秘密鍵として共有する量子暗号装置送信者 (Alice) 通信路雑音 Eve の盗聴量子暗号装置受信者 (Bob)

21 量子誤り訂正符号を使った仮想的プロトコル 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)

22 量子誤り訂正符号を使った仮想的プロトコル量子暗号の鍵生成レート = CSS 符号の符号化率であり古典符号 C 1, C 2 の性能できまる AB Alice, Bob それぞれ n キュービットずつ盗聴や通信路ノイズで傷ついたもつれあい状態 ( ビット誤り率 = 位相誤り率 = e とする ) rec AB ビット誤り訂正古典符号 C 1 のシンドロームビットと同じ数のキュービットを消費 ( nh e とおく ) n 1 fbh 2 e キュービットずつ位相誤り訂正 C 2 f b 2 古典符号のシンドロームビットと同じ数のキュービットを消費 ( nh e とおく ) f p 2 ( 一般に f, 1, 理想的には f b f 1 ) b f p p e e n 1 f H f H 個のBell 状態 (= 秘密鍵ビット数 ) ent AB b 2 p 2

23 現実の BB84 プロトコル議論の詳細は省くがいままでの仮想プロトコルを盗聴者からみた場合現実の BB84 プロトコルと区別がつかない (Shor-Preskill 2000) BB84 プロトコル ( 通信路雑音あり ) 1. AliceはBobに基底をランダムに選んで光を送る 2. Bobは基底をランダムに選んで光を測定し結果を記録 ( ふるい鍵 ) ここまでは通信路雑音なしの場合と同じ 3. サンプルビットをランダムに選び位相誤り率を推定する誤り率が高すぎたら ( 約 11% 以上 ) プロトコルを中止する 4. Alice, Bobは符号 C 1 を用いてビット誤り訂正を行う ( 訂正鍵 ) 5. Alice, Bobは符号 C 2 による同値類 C 1 /C 2 をとる ( 秘密鍵 ) 量子暗号装置送信者 (Alice) Eve による攻撃量子暗号装置受信者 (Bob)

24 ふるい鍵生成までの流れ Alice の生成した乱数 Alice の選んだ基底 Alice が実際に送る状態 Bob の選んだ基底 Bob が観測する状態 Bob が読取った乱数 + 基底基底 b=0 b=1 量子通信が終了してから基底の情報を公開する再掲このビット列をPCや回路でデータ処理する基底の一致した部分のビットは ( 誤り訂正秘匿性増強基底の一致しない箇所は ) ふるい鍵 ( 篩鍵 ) として保持乱数となるので捨てる

25 現実の BB84 プロトコル鍵蒸留処理 : ふるい鍵に対し以下のデータ処理を PC や FPGA 上で行うふるい鍵 : 検出器から出てきたままのビット列, n ビット ( e = ビット誤り率 ) 1 誤り訂正符号 C 1 によるビット誤り訂正訂正鍵 : 一部の情報がまだ盗聴者に漏洩している, 1 f H e ビット n p 2 2 得られた符号語 x C 1 に対し符号 C 2 で同値類をとるこの操作を秘匿性増強 (privacy amplification) とよぶ ( 敵に漏れた情報量 NH 2 e ビット分を除去していると解釈 ) 秘密鍵 : 実際に暗号通信に使う鍵, 最終鍵ともよぶ同値類 C 1 /C 2 の元, n 1 f H e f H e b 2 p 2 ビット

26 量子暗号における古典 CSS 符号以下量子 CSS 符号の構成にもちいる線型符号の組 C 1, C 2 を古典 CSS 符号と呼ぶことにする量子 CSS 符号の要請から C 1, C 2 には以下の条件が必要 C 2 C 1 C 1 および C 2 が良い符号である ( 符号化率が高い ) ただし量子暗号に利用するときは位相誤り訂正用の C 2 にさらに注釈がいくつか加わる有利な注釈 : ランダム符号が本当に使える不利な注釈 : 符号のビット長が巨大でないとならない ( 有限長効果 )

27 量子暗号における古典 CSS 符号 C 2 に対する有利な注釈 C 2 を用いた位相誤り訂正は実際には行わず C 2 の同値類をとるのみしたがって効率的な復号アルゴリズムは不要情報理論的に C 2 が復号可能でありさえすればよいゆえにランダム符号でもOK ( 符号 C 1 内に符号 C 2 を毎回ランダムにとる ) このとき符号 C 2 のシンドローム長を最小の値 nh 2 eにできる ( f = 1に相当 p )

28 量子暗号における古典 CSS 符号 C 2 に対する有利な注釈 ( つづき ) C 1 で復号した情報ベクトルに線型な universal hash function をかければ安全 (Renner 2005) Universal Hash Function 以下の条件を満たす関数の集合 F f を r r I, fr : A B ε-almost universal2 hash functionとよぶ A x y, Prfr x fr y B 1-almost を単にuniversal hash functionと呼ぶ例 :Toeplitz 行列演算これを CSS 符号の言葉でいうと : C 2 を C 1 内に 1-almost universal2 符号族としてとることに相当そのときその双対符号 C 2 の集合は 2-almost universal2 符号族となる ε-almost universal2 符号族はランダム符号と類似の復号性能を持つ ε-almost universal2 符号族 n 符号 C1 F2 に含まれる符号の集合 C2 C2r C1 r I, dimc2r t が以下を満たすときを (C 1 の部分 )ε-almost universal2 符号族とよぶ C 2 n x F 2 C Pr r 2 t x C n 1, 2 このとき, 写像 C 1 C 1 /C 2 は ε-almost universal2 hash function となる. (M. Hayashi 2007; T.T. and M. Hayashi, in preparation)

29 量子暗号における古典 CSS 符号 C 2 に対する不利な注釈有限長効果 (M. Hayashi 2007) 位相誤り訂正を実行しないので復号失敗を直接検証できない位相誤り率 e p は実はサンプルビットの誤り率 p smp から推定するもの推定の統計誤差を抑えるためには C 2 のビット長を大きく取る必要がある数値例サンプルビットはランダムな非復元抽出であり超幾何分布に従う P k c 仮に C 1 のブロック長 n, サンプルビット数 l をともに 1000 とすると, 本来の誤り率 e p =5% に対し, 確率 6% 以上で推定誤差 1% 以上 Pr n l k cc 4% 6% p smp n 鍵生成レートを無限大と遜色ないレベルにするためには C 2 のビット長 n を 1Mbit 以上にとる必要があるとされる (Scarani-Renner 2008) l k

30 高速秘匿性増強アルゴリズム (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 10 6 (Hayashi 2007; Scarani and Renner 2008) QKD Device Error Correction Privacy Amp. Sifted Key Secret Key Key Distillation (msec) Running Time Efficient multiplication algorithm of Toeplitz matrices via FFT, with an almost constant running time per bit Privacy amplification on software for block size n>10 6 1e+7 1e Naïve Algorithm O(n 2 ) FFT-based Algorithm O(n*log(n)) Block Size n (bit) Running time of PA on software

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

32 Tokyo QKD Network 量子暗号で共有した鍵で暗号化し動画配信 ( テレビ会議 ) を実施記者発表 (10 月 14 日 ) および国際会議 UQCC でのデモ (18 日 ) 通信速度 : 数 kbps~300kbps ( 通信路により異なる ) UQCC ホームページより

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

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

35 通信デモの様子各社装置の状況を動画中継 NEC 三菱電機 NTT NICT ( 超伝導検出器 )

36 通信デモの様子各社装置の状況を動画中継東芝欧州研 ( イギリス ) id Quantique ( スイス ) All Vienna ( オーストリア )

37 Tokyo QKD Network 実際の装置の様子 ( 大手町 ) 東芝欧州研 Alice NEC Alice 三菱 Alice 三菱 Bob

38 まとめ量子暗号は絶対に破られない暗号でありなおかつすでに実用化レベルに達している量子暗号量子計算機海外ベンチャー企業による市販品内外各社による試作品 Tokyo QKD Network における接続デモその安全性証明において誤り訂正符号が重要である量子誤り符号 ( 量子 CSS 符号 ) のコンポーネントとして従来型の誤り訂正符号 ( 古典 CSS 符号 ) がある (C 2 C 1 かつ C 1,C 2 がよい符号 ) 古典 CSS 符号の性能が量子暗号装置の性能を左右する一方で量子暗号装置において古典 CSS 符号を実際に使う必要はない量子暗号においては C 2 による位相誤り訂正を実行しないのでランダム符号やユニバーサルハッシュ関数で置き換えられる結果として通常のビット誤り訂正を行った後にユニバーサルハッシュ関数による秘匿性増強を行うことと等価になった

An Automated Proof of Equivalence on Quantum Cryptographic Protocols

An Automated Proof of Equivalence on Quantum Cryptographic Protocols 量子暗号のためのプロトコル等価性検証ツール久保田貴大 *, 角谷良彦 *, 加藤豪, 河野泰人, 櫻田英樹 * 東京大学情報理工学系研究科, NTT コミュニケーション科学基礎研究所背景暗号安全性証明の検証は難しい量子暗号でもそうである検証のための形式体系が提案されているが, 実際には, 形式体系の適用は手作業では非常に煩雑である形式検証のためには, 検証ツールが開発されることが望ましい