RSAは、もはや安全ではないっていうけど・・・

じゃあ、他のものはどうなの？量子暗号とか・・・は今一つよくわからなかった、

「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」
https://peatix.com/event/648891

を途中からメモメモ（遅れていったので、初めはとれていない）

---

日本の暗号　ぱーぷる暗号
→破られる　Code Girls

アメリカ　Code Talker→らばほいんであん：らばほ語に英語を訳す
→誰もわからない言語は暗号
暗号：コンピューターの走り

Colossus：こわされる（抹消）→いま検証しようとしてる：関係者死んでる

言語と暗号
・しゃんぽりあん　ろぜったすとーん
・べひいすとん
→同じ技術
線文字B　べんとりす
大量のデータがなくても解読できる
エンコーダー　＜＝＞　デコーダー→日ントンのオートエンコーダーと同じ考え

Semantec　Hashing（意味的ハッシング）

自然言語：ハッシング
　抽象概念・上位概念は、せまんてぃんぐハッシングなんだよね

DeepLearningで暗号解読は可能？
　もとと原文を手に入れる：データが揃わない　情報が少ない中でどうするか？

ナッシュ：１９５５年のNSA宛の手紙
　計算が難しい→誰も破れない：指数関数的時間
複雑性理論にとって、

ゲーデル

RSA暗号と素因数分解
２２０桁の数の素因数を求める（２００７年に終了）

公開キー暗号　１９７６年
RSA暗号　１９７７
→先行者がいた　Ellis－Cocks－Williamson
GCHQのパイオニア

暗号と計算複雑性理論
・ある種の数学的問題を「効率的」には解くことができない
　ゲーデル：不完全性定理→なにができて、なにができない
→時間とメモリーで定量的に

　優しい：手に負えない：不可能

不可能：計算可能性
優しい・手に負えない：計算複雑性理論
手に負えない＜＝＞多項式
※ｎがかたにのると、指数関数

P問題：多項式時間で解ける＝優しい問題
NP問題：Not　Pではない　正しいかどうかは多項式時間で解ける
　素因数分解
P=NP?問題：わからない
NP困難：多項式時間で解けない

〇一方向関数
ｙ＝ｆ（ｘ）はやさしい、しかしYからXを求めるのは、難しいもの
→平均して難しいこと必要→暗号として使えない

　候補
・RSA
・離散対数

言語と複雑性

計算：みじか　有限と無限

認識の限界；知りうることは限られる

Shorの素因数分解アルゴリズムの発見
　NSA：暗号の標準
・フェルマーの小定理
フェルマーテスト　確率的素数判定

６月２１日　マルレク・サブゼミ
・位相：キュービット

シュアのアルゴリズムと複雑性理論
　ショアのアルゴリズムが複雑性理論に衝撃を与える

BQPクラスの発見
ばじらーに
・かくちょうされたチャーチ、チューリングテーゼ
　どんな合理的なモデルも確率的チューリング機械で効率的にシミュレートできる
　→無限の長さとかは不自然：合理的ではない

ファインマンの問題提起

結論：新しい量子複雑性クラスのBQPの発見
　普通のコンピューターでは多項式時間では解けないが
　量子コンピューターなら、多項式時間でシミュレートできる

２００２　PRIMES is in P

・実は人間も、コンピューターも限られている

Post Quantum Cryptography
NIST 8240
量子耐性アルゴリズムへの移行のための準備計画
　IAD
　コスト
　SuiteBは当面安全。ただ移行してないのに投資するのはやめたほうが・・・

NIST 8150
　RSA　もはや安全ではない　NIST 2016年の報告

ラティスベース：格子
コードベース

NIST 8240

第二ラウンド
・８２のアルゴリズム

来年　ラウンド３
Moscaの定理：XとYとZ
　X:もってほしい
　Y:廃位する
　Z：量子コンピュータができるまでの年数
Zが４０を超えれば、暗号は破られる

ショアの論文の引用はうなぎのぼり

量子暗号
・観測の原理：観測すると失われる→暗号を量子に託せば、みられない
・No Cloning定理：コピーできない
BB84

０＞、１＞を規定にエンコード
＋＞、ー＞を規定にエンコード（４５どかたむける）
区別できない
０、１が確率２分の１：量子コイン

ありすとぼぶが秘密キーを共有
BD84




最近、いろいろ書きたまってるけど、公開してないのがあるので、
徐々に出していこうと思ってる。
とくに量子コンピューターのプログラミングの仕方は、どこかにまとめたい・・・