量子コンピュータと情報セキュリティ
只木孝太郎
中央大学大学院理工学研究科
「情報セキュリティ技術」資料
2014年12月10日
1
内容
•
•
•
•
•
量子コンピュータ開発の経緯と現状
量子コンピュータの原理
Shorの素因数分解アルゴリズム
情報セキュリティへの脅威
実現の可能性
2
量子コンピュータ研究のこれまで
・ １９７３年 C.H. Bennett
可逆計算
・ １９８０年代前半 R.P. Feynman
量子力学に基づく高速計算の可能性
・ １９８５年 D. Deutsch
汎用量子コンピュータのモデル化（量子チューリングマシン）
・ １９８９年 D. Deutsch & R. Jozsa
量子コンピュータが、従来のコンピュータより指数関数的に速い実例
・ １９９４年 P.W. Shor
素因数分解・離散対数問題を多項式時間で解く、量子アルゴリズム
・ １９９６年 L. Grover
データベース検索を加速する量子アルゴリズム
3
量子コンピュータの実現
最初の量子コンピュータはNMR装置を利用して実現した。
NMR（核磁気共鳴）装置： 有機化合物分子の構造解析で広く利用
2001年１２月 IBMのI. Chuangら
Shorの素因数分解アルゴリズムの実証を目的として15の素因数
分解を行う。
有機化合物分子中の、計7個のフッ素原子と炭素原子の
原子核スピンを、量子コンピュータとして利用
4
ＮＭＲ実験装置の例
写真提供：日本電子株式会社
NMR量子コンピュータ最近の発展
・ ２００８年
Xinhua Peng, Zeyang Liao, Nanyang Xu, Gan Qin, Xianyi Zhou,
Dieter Suter, and Jiangfeng Du
液晶NMRを用いて、断熱的量子計算に基づいて、21 (=3×7)の素因数
分解を実現。3キュービットで実現。大規模化不可能。
・ ２０１１年
Nanyang Xu, Jing Zhu, Dawei Lu, Xianyi Zhou, Xinhua Peng,
and Jiangfeng Du
液晶NMRを用いて、断熱的量子計算に基づいて、143 (=11×13)の素
因数分解を実現。143の特殊性を利用し、4キュービットで実現。
6
量子コンピュータの実現（再掲）
最初の量子コンピュータはNMR装置を利用して実現した。
NMR（核磁気共鳴）装置： 有機化合物分子の構造解析で広く利用
2001年１２月 IBMのI. Chuangら
Shorの素因数分解アルゴリズムの実証を目的として15の素因数
分解を行う。
有機化合物分子中の、計7個のフッ素原子と炭素原子の
原子核スピンを、量子コンピュータとして利用
以下では、ChuangらのNMR量子コンピュータを念頭において、
量子コンピュータの原理について解説する。
7
量子コンピュータの原理
8
量子コンピュータの構成要素
量子コンピュータ内部
データは２進数で表現される。
従来のコンピュータと同じ
従来のコンピュータの１ビット
量子コンピュータの１ビット
0, 1
物理的な実体： 異なる２つの電位
0, 1
物理的な実体： ２つの量子状態
1キュービット（qubit、量子ビット）
キュービットの例
電子のスピン
光子の偏向状態
原子核のスピン
イオンの振動状態
（スピン：方位磁針のような属性）
電子の有無
9
例： ＮＭＲ量子コンピュータ
キュービット：
磁場中に置かれた原子核スピン
（溶媒分子を構成する原子の原子核）
Chuangの実験
０
原子核
スピン
磁場
有機化合物分子の中
の7個の原子の原子核
スピンを利用
重ね合わせの原理 （量子力学の原理の１つ）
（複素数）×
このような重ね合わせで、
任意の方向を向いたス
ピンが表現できる。
１
＋ （複素数）×
スピンは、重ね合わせの状態をとることもできる。
０と１の重ね合わせ状態が存在する。
１キュービットは無限個の状態が表現できる。
10
ビット列（２進数）の表現
２桁以上の２進数は、上下いずれかを向いた
スピンの列で表現される。
例
１１０１
４個のスピンで表現される
スピンの列についても、重ね合わせの原理が成り立つ。
例
図２
１１０１、０１００、１１１１
の重ね合わせ状態が存在する。
波動関数の確率解釈 （量子力学の原理の１つ）
１１０１、０１００、１１１１
３つのパターンのうち１つが
の重ね合わせ状態
確率的に観測される。
スピンの列を測定
11
量子コンピュータでの計算の進め方
NMR量子コンピュータの場合
[1] 原子核のスピンの列を適当な初期状態に置く。
[2] 原子核スピンへの、高周波の磁場パルスの照射を繰り返し、量子状態を
変化させ、計算を進める。
入力はどう反映
されるか？
量子コンピュータの
１クロック
入力に応じて、磁場パルス列のパターンが変更され、
量子状態に反映される。
１つの磁場パルスの照射が１クロックに対応
[3] スピンの列を測定し、観測された２進数（0,1のパターン）が出力とされる。
12
量子並列性による高速計算
量子コンピュータと従来のコンピュータの違い
13
効率的なアルゴリズムとは？
効率的なアルゴリズム（実現可能な計算）
ある多項式p(x)が存在して、任意のNに対し、
入力Nでの計算時間≤p(log N)
log N： Nの桁数
多項式時間のアルゴリズム
14
整数Nの素因数分解を求めたい。
従来のコンピュータによる素朴な方法
整数を格納する２つのレジスタ１、２を用意する。
[1] 与えられた整数 i を、レジスタ1に格納する。
レジスタ１
レジスタ２
i
最悪
N ( 21/ 2log N ) 回
[1],[2]を繰り返す必要が
ある。
計算時間は指数関数的
[2] Nをレジスタ1の値で割った余りを、レジスタ２
に書き込む。
i
多項式時間のアルゴリ
ズムではない。
N mod i
以上の[1],[2]を、i=2から始めて、iを1ずつ増やながら繰り返し、そのつどレジス
タ２を見る。
レジスタ２の値が0
i がNの因数
15
整数Nの素因数分解を求めたい。
量子コンピュータによる方法
整数を格納する２つのキュービット列を用意し、
それらをレジスタ１・レジスタ２として用いる。
レジスタ１
レジスタ２
キュービット列
キュービット列
レジスタ１の値でNを割った余りが、レジスタ２に書き込まれるように、与える
磁場パルス列のパターンをあらかじめ設計しておく。
（例） N=77の素因数分解
2
2
1
6
5
磁場パルス列
6
磁場パルス列
ここまでは、従来のコンピュータと同じ
16
量子コンピュータでは、重ね合わせ状態が利用できる。
割り算に先立って、レジスタ１を、 2 から N までの全ての
整数が格納された重ね合わせ状態に置くことが可能
N=77の場合
従来のコンピュータで
N 回かかっていたのものが
たった1の割り算で済む。
量子並列性
速さの源
素因数分解のためには
別の工夫が必要
17
量子干渉の必要性
量子コンピュータが従来のコンピュータより（準）指数関数的に速くなる状況
重ね合わせ状態に乗っている（周期などの）グローバルな情報を取り出す場合
量子干渉によって実現される
Nの素因数分解は、ある関数 f の周期を求めることに帰着可能
Shorの素因数分解アルゴリズムは、
量子干渉で周期を取り出すことにより、
多項式時間での素因数分解を達成した。
18
Ｓhorの素因数分解アルゴリズム
19
Ｓｈｏｒの素因数分解アルゴリズム
メインルーティン： 従来のコンピュータを利用
入力：N (N=p×q、pとqは異なる素数)
出力：pとq
確率アルゴリズム
[1] N と互いに素な整数 a (2≦a≦N-1) をランダムに（一様に）選ぶ。
Nの桁数の多項式時間で、Nと互いに素なaが得られる。 （Euclidアルゴリズム）
[2] 関数 f(x)=ax mod N の周期 r を求める。
最も計算時間がかかる。
量子コンピュータで r を計算する。
[3] ar/2+1とNの最大公約数、及びar/2-1とNの最大公約数を求めて出力する。
最大公約数は、Nの桁数の多項式時間で求まる。（Euclidアルゴリズム）
20
Ｓｈｏｒのアルゴリズムの動作を例で見みる。
N=15の素因数分解を求めてみよう。
[1] N と互いに素な整数 a (2≦a≦N-1) をランダムに（一様に）選ぶ。
Nと互いに素な整数： 2,4,7,8,11,13,14
ランダムに選んだaが、a=7だったとする。
[2] 関数 f(x)=ax mod N の周期 r を求める。
f(x)の周期：ar ≡1 mod Nとなる最小の r （aのorder）
（Nとaは互いに素なので、フェルマーの小定理より必ず存在する。）
今の場合、f(x)=7x mod 15 となる。
この関数 f(x) の周期 r を計算するのに量子コンピュータを用いる。
21
レジスタ１、レジスタ２の重ね合わせ状態の推移
f(x)=7x mod 15
22
周期 r を求める量子サブルーティン
量子コンピュータ
整数を格納する２つの量子レジスタ、レジスタ１・レジスタ２と
作業用の量子レジスタを持つ。
レジスタ１
レジスタ２
作業用レジスタ
キュービット列
キュービット列
キュービット列
[1] レジスタ１に、0から15までの全ての数を重ね合わせた状態を準備する。（図4-a）
[2] レジスタ１の各値 x に対応する f(x) を量子並列的に計算し、隣のレジスタ２に書き
込む。（図4-b）
x
f(x)=7 mod 15
f(x)=ax mod N： Nの桁数の３乗の計算時間が掛かる。
量子サブルーチンで最も計算時間を消費する部分
23
レジスタ１、レジスタ２の重ね合わせ状態の推移
24
量子サブルーティン（続き）
周期性の構造を見やすくするため、順序を入れ替えてみる。（図4-c）
レジスタ１の内容
グループA: 0, 4, 8, 12
それぞれのグループで、始まりの値が
異なっている。
グループB: 1, 5, 9, 13
グループC: 2, 6, 10, 14
グループD: 3, 7, 11, 15
ここで、レジスタ１を観測しても、効率的に
周期を求めることはできない。
4ずつ増えている。
周期 r = 4
量子フーリエ変換を施して、
周期の始まりを揃える。
25
レジスタ１、レジスタ２の重ね合わせ状態の推移
グローバルな変換
26
量子サブルーティン（終わり）
[3] レジスタ１に量子フーリエ変換を施す。（図4-d）
フーリエ変換の量子版
計算経路間の量子干渉を引き
起こすグローバルな変換
レジスタ１の内容
グループA: 0, 4, 8, 12
グループB: 0, 4, 8, 12
グループC: 0, 4, 8, 12
グループD: 0, 4, 8, 12
ここでレジスタ１を観測すると、
十分に高い確率で周期 r が得られる。
定数
（ rが得られる確率）
log(Nの桁数)
揃っている
周期 r = 4 が得られた。
互いに強め合う
27
Ｓｈｏｒの素因数分解アルゴリズム
（メインルーティン）
[1] N と互いに素な整数 a (2≦a≦N-1) をランダムに（一様に）選ぶ。
a=7
[2] 関数 f(x)=ax mod N の周期 r を求める。
量子サブルーティン
周期 r = 4が得られた。
[3] ar/2+1とNの最大公約数、及びar/2-1とNの最大公約数を求めて
出力する。
ar/2+1 = 72+1 = 50
gcd(ar/2+1, N) = gcd(50,15) =5
ar/2-1 = 72-1 = 48
gcd(ar/2-1, N) = gcd(48,15) =3
Euclidアルゴリズム
出力： 5と3
15 = 5×3 が得られた。
28
Ｓｈｏｒのアルゴリズムの計算時間
[1] N と互いに素な整数 a (2≦a≦N-1) をランダムに（一様に）選ぶ。
(Nの桁数)2ステップ（Euclidアルゴリズム）
[2] 関数 f(x)=ax mod N の周期 r を求める。
(Nの桁数)3ステップ
C/log(Nの桁数) 以上の確率で正しい r が得られる。
[3] ar/2+1とNの最大公約数、及びar/2-1とNの最大公約数を求めて出力
する。
(Nの桁数)2ステップ（Euclidアルゴリズム）
正しい周期 r が与えられたとき、1/2以上の確率で1とN以外の因数が得られる。
全体として、C/(2 log(Nの桁数))以上の確率で、自明でない因数pとqが得られる。
[1],[2],[3]をlog(Nの桁数) 回程度繰り返せば、ほぼ確率1でNの素因数分解が得られる。
全体として、Nの桁数の多項式時間（ (Nの桁数)3 log(Nの桁数) ステップ）で
Nの素因数分解がが得られる。
29
情報セキュリティへの脅威
30
ＲＳＡ暗号の解読
(1) 従来のコンピュータ技術による解読（Shamir & Tromer, 2003）
TWIRL: 素因数分解を行う仮想的な並列コンピュータ
（当時標準的な0.13μm・1GHzのシリコンVLSI技術に基づく。直径30cmのLSI）
１万ドルのコストで
数体ふるい法
1024bit
合成数（鍵）のけた数
1/ 3
2/ 3
512bit
計算時間
１０分以下 １０００年
RSAモジュール(鍵)の素因数分解
O(exp[O(1)l (logl ) ])
ステップ
ここで、l = 合成数の桁数
(2) 量子コンピュータによる解読 （R. Hughesによる解析, 2003）
1GHz の量子コンピュータでは
最適化された
Shorのアルゴリズム
25 l3+O(l2) ステップ
表１
31
古典計算機でのRSA暗号の解読
1024bitの素因数分解にかかる時間とコストの比較
(1) TWIRL（Shamir and Tromer, 2003）
直径30cmのLSI
1000万ドルのコストで1年
(2) SHARK（Franke et al., 2005）
2億ドルのコストで1年
(3) YASD1024（Hirota et al., 2006; Geiselmann & Steinwandt, 2004）
411cm2 のLSI
1000万ドルのコストで16年以上
32
有限体上の離散対数問題を解く
p を素数、g をmod p の原始根とすると、
A {1,2,…,p-1} に対し、A≡ga mod p となる a {0,1,2,…,p-2} が存在する。
aをAの離散対数と言う。
Aが与えられたとき、aを求めるのが有限体上の離散対数問題
量子コンピュータは、有限体上の離散対数問題も、多項式時間で解く。
（素因数分解アルゴリズムの量子サブルーチンの変形。これもShorによる。）
有限体上の離散対数問題の困難さに基づく暗号
ElGamal暗号
解読
Diffie-Hellman鍵共有
33
楕円暗号の解読
楕円暗号： 楕円曲線上の離散対数問題の困難さに基づいている。
Shorによる有限体上の離散対数問題を解く量子アルゴリズムが適用可能。
Proos & Zalkaによる楕円暗号解読の量子アルゴリズムと
その解析（2003）
楕円曲線が基づく有限体GF(p)の元の数 p が
素数の場合
鍵長の多項式時間で
解読
GF(2^m)の場合を最適化（ Kaye & Zalka, 2004 ）
34
認証技術の安全性
認証技術
ディジタル署名、ゼロ知識対話証明など
主要なものは、以下のものの１つに、その安全性の根拠を置いている。
[1] 素因数分解の困難さ
[2] 有限体上の離散対数問題の困難さ
量子コンピュータは効率よく解く
[3] 楕円曲線上の離散対数問題の困難さ
量子コンピュータが実現
安全性の保証がなくなる。
35
量子コンピュータ実現の可能性
36
１０キュービットの壁
NMR量子コンピュータの限界
デコヒーレンス： 外界との相互作用により重ね合わせ状態が壊れてしまう現象
NMR量子コンピュータ
成功の理由
原子核スピンと外界との相互作用は弱い
溶媒中の有機化合物分子の１つ１つが量子コンピュータ
平均的なNMR信号を通じて、計算結果が読み出される。
初期化の問題
分子中の7個の原子
の原子核スピンを利
用
7キュービット
キュービット数が増えると、実効的な初期化が難
しくなる。
計算結果の信号が弱まる。
キュービット数の増加は、分子の巨大化を意味する。 １０キュービットが限界
デコヒーレンスを招く。
1997年より現在まで、
そう言われている。
37
量子コンピュータの実現
・イオントラップ： レーザー光による制御、多数イオンの制御が困難
・光子（偏向状態）： 相互作用が弱い→演算の実現が困難。
2007年、15の素因数分解を実現。
・ジョゼフソン位相キュービット： 超伝導の固体素子。2012年、固体素子
として初めて（15の）素因数分解を実現。大規模化可能。
量子コンピュータが情報セキュリティの脅威となるには、最低でも
1000キュービットの実装が必要
それを容易に実現する提案は存在しない。
いくつものブレークスルーが必要
量子コンピュータの研究開発
・新分野の開拓
・関連技術の進歩
（ナノテクノロジー）
38
© Copyright 2024 ExpyDoc
