日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティシンポジウム平成 30 年 3 月 1 日日本銀行本店 01/17 耐量子計算機暗号の標準化動向高木剛東京大学大学院情報理工学系研究科

Size: px

Start display at page:

Download "日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティシンポジウム平成 30 年 3 月 1 日日本銀行本店 01/17 耐量子計算機暗号の標準化動向高木剛東京大学大学院情報理工学系研究科"

なつきこうい
6 years ago
Views:

1 日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティシンポジウム平成 30 年 3 月 1 日日本銀行本店 01/17 耐量子計算機暗号の標準化動向高木剛東京大学大学院情報理工学系研究科

2 現代社会と暗号技術昔の暗号限られた人だけが使う特殊技術現代の暗号電子政府個人認証プライバシー保護電子決済仮想通貨著作権保護コピー防止電気自動車スマートグリッド暗号は現代社会に無くてはならない技術 02/17

3 03/17 公開鍵暗号の歴史ラビ模型 (1944) Shorのアルゴリズム NMR 量子計算機実証 Haroche 等の量子もつれ実験 ~ RSA 暗号 ( 素因数分解問題 ) 広く普及楕円曲線暗号 ( 離散対数問題 ) 量子計算機で危殆化!! 研究段階ポスト量子暗号 ( 格子理論, 多変数多項式,etc)

Quantum Cloud - IBM Q https://www.research.ibm.

4 Quantum Cloud - IBM Q より転載 Currently IBM Q has 20 qubits in November 2017, and they plan to extend it to 50 qubits in a few years. Google also tries to build a 50-qubit Processor. 04/17

05/17 ポスト量子暗号の研究動向 2015 年 8 月 : アメリカ国家安全保障局

nsa.gov/ia/programs/suiteb_cryptography/

Workshop on The Mathematics of Post-Quantum

edu/workshops/post-quantum/ 2015 年 4 月, NIST

5 05/17 ポスト量子暗号の研究動向 2015 年 8 月 : アメリカ国家安全保障局 (NSA) はポスト量子暗号への将来的な移行プランを発表した最近のポスト量子暗号関係のワークショップ 2015 年 1 月, DIMACS Workshop on The Mathematics of Post-Quantum Cryptography 年 4 月, NIST Workshop on Cybersecurity in a Post-Quantum World 年 9 月, Dagstuhl Seminar - Quantum Cryptanalysis 年 10 月, ESTI Workshop on Quantum-safe Cryptography 2016 年 2 月, PQCrypto 2016: ポスト量子暗号関係の大型研究プロジェクト Post-quantum cryptography for long-term security: CROSSING: JST CREST 暗号数理 :

6 06/17 PQCrypto 2016 参加者 240 名 ( 北米 80 名欧州 60 名アジア 60 名日本 40 名 ) NIST がポスト量子暗号の標準化計画を発表した

7 07/17 NIST ポスト量子暗号標準化計画公開鍵暗号プリミティブを公募 (2017 年 11 月 30 日〆切 ) - 鍵交換方式 (key exchange) - 暗号化 (public-key encryption) - ディジタル署名 (digital signature) 公募〆切後 3~5 年かけて安全性と効率性を評価する利用される数学問題 - 格子暗号 (Lattice-based cryptography) - 符号暗号 (Code-based cryptography) - 多変数多項式暗号 (Multivariate polynomial cryptography) - ハッシュ関数署名 (Hash-based signature) - 同種写像暗号 (Isogeny-based cryptography)

8 応募状況 (69 件 ) 格子暗号 (24 件 ) Compact LWE, CRYSTALS-DILITHIUM, CRYSTALS-KYBER, Ding Key Exchange, DRS, EMBLEM and R.EMBLEM, FALCON, Frodo, HILA5, KINDI, LAC, LIMA, Lizard, LOTUS, NewHope, NTRU-HRSS-KEM, NTRU Prime, NTRUEncrypt, Odd Manhattan, pqntrusign, qtesla, Round2, SABER, Titanium 符号暗号 (16 件 ) BIG QUAKE, BIKE, Classic McEliece, DAGS, Edon-K, HQC, LEDAkem, LEDApkc, McNie, NTS-KEM, pqsigrm, QC-MDPC KEM, RaCoSS, Ramstake, RLCE-KEM, RQC 多変数多項式暗号 (10 件 ) CFPKM, DME, DualModeMS, GeMSS, Gui, HiMQ-3, LUOV, MQDSS, Rainbow, SRTPI ハッシュ関数署名 (2 件 ) Gravity-SPHINCS, SPHINCS+ 同種写像暗号 (1 件 ) SIKE その他 (16 件 ) Giophantus, Guess Again, HK17, LAKE, Lepton, LOCKER, Mersenne , OKCN/AKCN/CNKE, Ouroboros-R, Picnic, Post-quantum RSAEncryption, Post-quantum RSASignature, RankSign, RVB, Three Bears, WalnutDSA 08/17

9 09/17 今後の PQC 関係イベント 2018 年 4 月 9 日 -11 日 PQCrypto 2018, フロリダ年 4 月 11 日 -13 日フロリダ 1st NIST PQC Standardization Conference 年 8-9 月頃 2nd NIST PQC Standardization Conference 2030 年までは SP Part I も利用可能としている

10 10/17 その他の動向 CRYPTREC( 暗号技術評価委員会 ) ポスト量子暗号の代表的な方式について調査を行っており調査結果を 2019 年末までに公表予定 ISO/IEC JTC1 SC27/WG2( 暗号とセキュリティメカニズム ) ポスト量子暗号を調査する Study Group が設置されており研究動向をサーベイしたスタンディングドキュメントを作成中

11 暗号の安全性検証サイクル提案フェーズ公開の場で議論検証するこの攻撃はどうだ? 暗号のストレステスト新しい解読アルゴリズム安全性検証フェーズ何ビットの鍵長が安全? 10 年程度のサイクル実用化フェーズ計算機スピードの向上暗号解読技術の進歩鍵長の寿命 11/17

12 RSA 暗号の公開鍵 12/17

13 RSA 暗号の安全性評価 (CRYPTREC) より転載 13/17

14 14/17 格子暗号の安全性 1 次独立なベクトル b 1,, b n R m の整数係数の線形和全体 n 格子 L b 1,,b n = t=1 x t b t, x t Z. Shortest Vector Problem (SVP) Input: 格子 L の基底 b 1,, b n R m Output: 非零の最短ベクトル NP-hard な問題として暗号で利用 Ajtai 1996, Regev 2005 など

15 15/17 格子暗号解読コンテスト Progressive BKZ の計算量理論値 Aono et al. Eurocrypt sec 攻撃者の計算限界が評価可能となる

16 16/17 処理性能の例メモリ量と演算速度格子暗号 Ding Key Exchange ( 鍵交換 ) AES 128 レベルの安全性多変数多項式暗号 Rainbow ( ディジタル署名 ) AES 128 レベルの安全性符号暗号 Classic McEliece ( 暗号化 ) AES 256 レベルの安全性アリス : 848 バイトボブ : 896 バイト公開鍵 :148.5 キロバイト秘密鍵 : 97.9 キロバイト署名 : 64バイト公開鍵 : キロバイト秘密鍵 : 14.1 キロバイト暗号文 : 240 バイト鍵生成 : 1.31 ミリ秒暗号化 : 1.71 ミリ秒復号化 : 1.19 ミリ秒鍵生成 : 394 ミリ秒暗号化 : ミリ秒復号化 : ミリ秒鍵生成 : ミリ秒暗号化 : ミリ秒復号化 : ミリ秒

17 17/17 まとめ NIST PQC 標準化では 69 件投稿があった - 格子暗号多変数多項式暗号符号暗号など 2018 年から 3~5 年かけて評価を行なう - 幾つかの最終候補を選定する予定 2030 年迄は SP Part I も利用可能

第 16 回情報セキュリティシンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる格子暗号を巡る最新動向日本銀行金融研究所情報技術研究センター清藤武暢本発表は ( 独 ) 情報通信研究機構青野良範研究員横浜国立大学四方順司准教授と共

第 16 回情報セキュリティシンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる格子暗号を巡る最新動向日本銀行金融研究所情報技術研究センター清藤武暢本発表は ( 独 ) 情報通信研究機構青野良範研究員横浜国立大学四方順司准教授と共第 16 回情報セキュリティシンポジウム 2015 年 3 月 11 日 ( 水 ) - 講演 3- 量子コンピュータによる解読に耐えうる格子暗号を巡る最新動向日本銀行金融研究所情報技術研究センター清藤武暢本発表は ( 独 ) 情報通信研究機構青野良範研究員横浜国立大学四方順司准教授と共同で実施した 1 研究に基づくまた本発表に示されている意見は発表者個人に属し日本銀行 ( 独

日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティ シンポジウム平成 30 年 3 月 1 日 日本銀行本店 01/17 耐量子計算機暗号の標準化動向 高木剛 東京大学大学院情報理工学系研究科

日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティシンポジウム平成 30 年 3 月 1 日日本銀行本店 01/17 耐量子計算機暗号の標準化動向高木剛東京大学大学院情報理工学系研究科