1
情報セキュリティ 第 14 回
大久保誠也 静岡県立大学経営情報学部
2/48
はじめに
はじめに
難しい問題と簡単な問題
未来の脅威 ～量子計算～
未来の通信 ～量子通信～
演習3/48
難しい問題 簡単な問題
4/48
現代暗号の安全性の根拠
基本的に、どんな暗号でも、時間をかければ、いずれ必ず解け る。安全であるとは『実時間で解くのは難しい』ということ。
数学的な難しさに、安全性の根拠を求めることが多い
本当に簡単に解けないかは、証明されていない（方法と、今の 人類が知らないだけの可能性も）この数学の問題は難しそうだ！
これ元にして暗号を作れば、きっと安全だ！
因数分解は難しい？
因数分解は、現在の計算機では、非常に時間がかか る問題であると考えられています。 15=3*5は簡単にわかる。
では、75462131は？正解は、7591*9941。
このぐらいなら、計算機で解けるけど、桁数が大きくな るほど難しくなる！問題の難しさ
『実時間で解くのは難しい』とは、どういうこと？
問題を解くのに必要な時間は、計算機の速度に よって違うんじゃないの？ 15と129813472では、因数分解するのに必要な時
間は違ってくるんじゃない？
結局のところ、
『問題を解くのに必要な時間』を 測るためのの尺度は何？
7/48
尺度
物事を測るためには、何事にも尺度が必要。
重さ： 単位はキログラム重 等。その物体にはたらく重力で、場所により異なる。
質量： 単位はキログラム 等。その物体固有の値で、場所により変化しない。
他にも、長さや明るさ、速度等、色々ある。8/48
問題の難しさの尺度
問題を解くのに必要な時間を測る尺度。
時間で測る：
ある問題を解くのに、現在の計算機では、どれ だけ時間が必要かを測る。
ある問題を解くのに、ある特定の計算機で、ど れだけ時間が必要かを測る。
数学的に測る：
その種の問題を解くのに、ある動作が何回必要 かを評価する。9/48
実際の時間を計測する例：
因数分解に対して
現在の計算機で、どのぐらいの桁まで実際に計算 可能なのか、実験が行われている。
（問題の難しさを測っているわけではない）
『因数分解 世界記録』で検索してみましょう。10/48
例：ベンチマーク
SPEC cpu2000
CPUの処理性能を測るベンチマーク。
UltraSparc-I を基準として、どれだけの処理性能
を持っているかを計測する。
（問題の難しさを測っているわけではない）
『SPEC cpu2000 性能』で検索してみましょう。11/48
そもそも「計算」とは？
「数学的に測る」として、定義は何？
計算機（コンピュータ）は「計算」するもの。
そもそも、「計算」ってなに？12/48
Church-Turing の提唱
Turing機械とは。
計算機の数学的モデルの一つ。
実際の計算機よりも、相当に単純化・理想化されて いる。
今の計算機でできることは、原理的にはTuring機 械でもできる！計算可能なものとは、Turing機械で実行できるもの
13/48
Turing 機械
p
1 0 0 1 0
有限制御部
（CPUに相当）
ヘッド
テープ
（メモリに相当）
現在の計算機の数学的モデルは，
Turing
機械状態遷移関数（プログラムに相当）に したがって、テープの値の書き換え、
状態の変更、ヘッドの移動を行う。
14/48
Turing 機械の動作
0 0 0 0 0
0 0 0 1 0 0 0
ヘッド
有限制御部 テープ
p q
テープの値を書き換える
ヘッドの位置が動く
動作
状態が変わる
15/48
計算量理論
計算の複雑さを扱う理論。
その問題を解くには、どのぐらい時間量が必要？
その問題を解くには、どのぐらい領域量が必要？
問題の複雑さを、入力サイズの関数として評価する。 Turing機械のテープは、どれだけ使用する？
Turing機械のヘッドは、何回動いた？
Turing機械は、特定の動作を何回やった？
入力 計算機 出力
16/48
計算量の例 [1/2]
n
ビットの長さの鍵で暗号化された暗号文ある。
総当たりで正解の鍵を発見するには、何回ぐらい、『鍵を入力し復号しようとする』動作を試みればよい？
入力：暗号化アルゴリズム n
ビットの長さの鍵を利用するのだから、長さはn
ビットぐらいはある。
出力：正しい鍵何回試みるか、
n
の関数として表現する17/48
計算量の例 [2/2]
n
ビットの長さの鍵だと、候補数は全部で2 n
個ある。
総当たりするとなると、2 n
回程度、試す必要がある。 n
の指数時間ぐらいの手間がかかる。→ こういうのを、『非常に時間がかかる問題』と言う
1ビット鍵の長さが伸びると、
必要になる時間は
2
倍に！
一方、多項式なら『時間がかからない問題』
2 n
は難しいn 2
は簡単回数
18/48
暗号で使用される問題の難しさ
秘密鍵暗号で、攻撃者が鍵探索をする場合。
暗号化関数が理想的に構成できていれば、2 n
の 試行が必要になり、非常に難しい。
本当に理想的に関数が構成できているかは不明。 RSA
暗号で、攻撃者が鍵探索をする場合。
指数時間の手間は必要ないが、多項式時間よりは 難しい問題だと予想されている。19/48
量子計算
20/48
古典力学と量子力学
古典力学
マクロな現象の力学。
古来から伝わる、由緒正しき力学。
例：手を離したらリンゴが落ちる
例：天体の運動
一方、原子や分子ぐらいミクロな世界になると、これ らの古典力学では説明できない現象が発生。こういう現象を説明できるのが量子力学
21/48
例：偏光板実験 (1)
偏光板には向きがあります。 1枚の偏光板を
縦向きのときには、光を（ ）。
横向きのときには、光を（ ）。 2枚の偏光板を
縦-縦 の順番に並べたときは、光を（ ）。
縦-横 の順番に並べたときは、光を（ ）。光 ？
22/48
例：偏光板実験 (2)
偏光板には向きがあります。 3枚の偏光板を
縦-縦-横 のときには、光を（ ）。
縦-横-横 のときには、光を（ ）。
縦-横-斜 のときには、光を（ ）。
縦-斜-横 のときには、光を（ ）。量子力学で説明可能
23/48
世界は分裂している？
多世界解釈と量子重ね合わせ
「シュレーディンガーの猫」で検索をかけてみよう。
世界は常に分裂し、
重ね合わさっている！
自分が認識しているのは、
その世界のうちの一つ
24/48
量子的な動作をする計算機
量子力学に基づいた計算機が、量子計算機。
通常の計算機に加え、量子力学的な動作ができる。
具体的には、
量子重ね合わせを状態を保持することができる。
上記の状態を利用することで、量子並列計算が 可能。
ある特定の問題に対しては、非常に高速に解くこ とができる。
物理的には実現していない。25/48
任意の重ね合わせ状態 を記憶
量子ビット (qubit)
1
0
と は を満たす複素数である.
と はヒルベルト空間内の状態ベクトル ( ) は，状態 ( )の確率振幅と呼ばれる.
2
2 1
0 1
0 or 1 0 1
重ね合わせ
Turing機械の場合
量子Turing機械の場合0 または1 を記憶
テープの1
つの区画に1bit 1qubit
1 0
and
26/48
量子 Turing 機械
1985
年にDavid Deutsch
が提案。
通常のTuring
機械に、量子並列計算機能を取り入れたもの。
p
1 0 0 1 0
有限制御部
（CPUに相当）
ヘッド
テープ
（メモリに相当）
状態遷移関数（プログラムに相当）に したがって、テープの値の書き換え、
状態の変更、ヘッドの移動を行う。
27/48
量子 Turing 機械の動作
0 0 0 0 0
0 0 0 1 0 0 0
c 2
遷移確率
ヘッド
有限制御部
p , 0 , 1 , q , R c
テープ
p q
状態 p
であり，ヘッドが0 を読んでいる時に
1 を書き込み，状態 q
にして, ヘッドを右に動かすc 2
その遷移を行う確率は，
28/48
量子計算機
量子コンピュータ 観測
|α i | 2
の確率で計算 結果c i
が観測される 入力1
|
|
1 2
Ni
i,
:
i C
確率振幅
…
N i
2
1
…
… …
c
Nc
ic
1量子重ね合わせ
c i
29/48
量子計算機
量子計算機は、量子並列計算を行う0 0 0 0
量子計算機 入力
0 0 0 0
0 0 0 0 0 0 0 1
1 0 1 0
量子並列計算
出力
0 0 0 1
量子計算機は内部では量子並列計算を行う
量子計算機は、その結果をすべて出力する わけではない
何が出力されるのか？（数学的モデル化の研究）
効率的に問題を解く方法は？（アルゴリズムの研究）30/48
物理的な実現の研究 (1)
NMR
量子計算機は，近い将来に実現可能（かも？）．→ 計算モデルは
Bulk
量子計算モデル
様々な物理的実現に関する研究が行われている． 2001
年IBM が核磁気共鳴機を使用した
量子計算機（NMR量子計算機）上で，
15
の因数分解に成功．© IBM
31/48
物理的な実現の研究 (2)
D-Wave
カナダのベンチャー企業 2007
年2
月に16qubit
の実現を主張。
現在は512qubit
と主張している。
本当に実現しているのか、評価は分かれている。
汎用量子計算機ではなく、特定の問題を解く専用 機らしい。量子アニーリング専用機。 2013
年、NASA
やD-Wave
の機械を使う予定。© D-Wave
32/48
物理的な実現の研究 (3)
日本でも、量子計算に関する研究は行われている。
「量子ビット 開発」で検索してみよう。33/48
Shor のアルゴリズム
1994年のPeter Shor
量子計算機は、因数分解を任意に小さい誤り確率で 多項式時間で実行可能であることを示す．
通常の計算機は、整数の因数分解を多項式時間で解く ことが難しいと信じられている．
量子計算機は通常の計算機より強力かもしれない！量子計算機が完成すると，
RSA暗号が解けてしまう！
34/48
Grover のアルゴリズム
1996年のL.K.Grover
量子探索アルゴリズムを発表。
鍵の総当たりに必要な時間が、 に。
指数時間ではあるが、時間の桁数は半分になる！量子計算機が完成すると，
鍵の総当たり攻撃も高速に可能
2 n
35/48
量子通信
36/48
重ね合わせ状態の崩壊
日本でも、量子計算に関する研究は行われている。
「量子ビット 開発」で検索してみよう。37/48
重ね合わせ状態の崩壊
人は、重ね合わせ状態を直に見ることはできない。
観測という行為を行って、状態を知る。
量子重ね合わせ状態は、観測すると崩壊してしまう。…
…
量子重ね合わせ
c i
観測すると、
重ね合わせが 壊れる。
38/48
量子通信
量子状態を通信するのが、量子通信。
さまざまな実験が行われている。
「量子通信 プレスリリース」で 検索してみよう。Alice
Bob
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
量子状態を やりとりする
39/48
量子通信の実現
さまざまな実験が行われている。
光子を用いた通信を利用する方式が有名。
1980 年代には数十センチの距離
2002 年には三菱電機により87km
2004 年には三菱電機により96km
2007 年にはロス・アラモス研究所により107km，
2006 年にはウィーン大学などにより144km，
2007 年にはNTT により200km40/48
量子鍵配送
量子通信を利用して、通常の（古典的な）秘密鍵を共 有するのが、量子鍵配送。Alice
Bob
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
量子通信も利用して、
秘密鍵を共有
盗聴者が居た場合
間に盗聴者が居た場合、重ね合わせ状態が壊れてし まい、正確に送られない。
盗聴されているかを検知できる！
盗聴されていたら 通信をやめる。Alice
Bob
送信
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
あｓｄふぁｓｄ Ｊｌｋｊぇｗｋｆ
盗聴だ！
あれ？
おかしいぞ。
盗聴されてる？
その他の量子情報処理
量子もつれ合い状態を利用した情報のやりとり
光子を飛ばさないで行うデータのやりとり
量子ゲーム理論
人間が量子的な動作をするなら（つまり、人と人 が量子力学的に繋がってるなら）何が起きるか。
量子不正行為
量子計算の考え方や、量子ビットを用いて、ゲー ム等でイカサマ行為をしよう。43/48
演習：
