日本銀行金融研究所情報技術研究センター第 19 回情報セキュリティ シンポジウム平成 30 年 3 月 1 日 日本銀行本店 01/17 耐量子計算機暗号の標準化動向 高木剛 東京大学大学院情報理工学系研究科 https://crypto.mist.i.u-tokyo.ac.jp/
現代社会と暗号技術 昔の暗号 限られた人だけが使う特殊技術 現代の暗号 電子政府 個人認証 プライバシー保護 電子決済 仮想通貨 著作権保護 コピー防止 電気自動車 スマートグリッド 暗号は現代社会に無くてはならない技術 02/17
03/17 公開鍵暗号の歴史 ラビ模型 (1944) Shorのアルゴリズム NMR 量子計算機実証 Haroche 等の量子もつれ実験 1980 1990 2000 2010 2020 2030 ~ RSA 暗号 ( 素因数分解問題 ) 広く普及 楕円曲線暗号 ( 離散対数問題 ) 量子計算機で危殆化!! 研究段階 ポスト量子暗号 ( 格子理論, 多変数多項式,etc)
Quantum Cloud - IBM Q https://www.research.ibm.com/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) は ポスト量子暗号への将来的な移行プランを発表した https://www.nsa.gov/ia/programs/suiteb_cryptography/ 最近のポスト量子暗号関係のワークショップ 2015 年 1 月, DIMACS Workshop on The Mathematics of Post-Quantum Cryptography http://dimacs.rutgers.edu/workshops/post-quantum/ 2015 年 4 月, NIST Workshop on Cybersecurity in a Post-Quantum World http://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm 2015 年 9 月, Dagstuhl Seminar - Quantum Cryptanalysis https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=15371 2015 年 10 月, ESTI Workshop on Quantum-safe Cryptography 2016 年 2 月, PQCrypto 2016: https://pqcrypto2016.jp/ ポスト量子暗号関係の大型研究プロジェクト Post-quantum cryptography for long-term security: http://pqcrypto.eu.org/ CROSSING: https://www.crossing.tu-darmstadt.de/ JST CREST 暗号数理 : https://cryptomath-crest.jp/
06/17 PQCrypto 2016 参加者 240 名 ( 北米 80 名 欧州 60 名 アジア 60 名 日本 40 名 ) NIST がポスト量子暗号の標準化計画を発表した
07/17 NIST ポスト量子暗号標準化計画 http://csrc.nist.gov/groups/st/post-quantum-crypto/ 公開鍵暗号プリミティブを公募 (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)
応募状況 (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-756839, OKCN/AKCN/CNKE, Ouroboros-R, Picnic, Post-quantum RSAEncryption, Post-quantum RSASignature, RankSign, RVB, Three Bears, WalnutDSA 08/17
09/17 今後の PQC 関係イベント 2018 年 4 月 9 日 -11 日 PQCrypto 2018, フロリダ http://www.math.fau.edu/pqcrypto2018/ 2018 年 4 月 11 日 -13 日 フロリダ 1st NIST PQC Standardization Conference https://csrc.nist.gov/events/2018/first-pqc-standardization-conference 2019 年 8-9 月頃 2nd NIST PQC Standardization Conference 2030 年までは SP 800-57 Part I も利用可能としている
10/17 その他の動向 CRYPTREC( 暗号技術評価委員会 ) ポスト量子暗号の代表的な方式について調査を行っており 調査結果を 2019 年末までに公表予定 ISO/IEC JTC1 SC27/WG2( 暗号とセキュリティメカニズム ) ポスト量子暗号を調査する Study Group が設置されており 研究動向をサーベイしたスタンディング ドキュメントを作成中
暗号の安全性検証サイクル 提案フェーズ 公開の場で議論 検証する この攻撃はどうだ? 暗号のストレステスト 新しい解読アルゴリズム 安全性検証フェーズ 何ビットの鍵長が安全? 10 年程度のサイクル 実用化フェーズ 計算機スピードの向上暗号解読技術の進歩 鍵長の寿命 11/17
RSA 暗号の公開鍵 12/17
RSA 暗号の安全性評価 (CRYPTREC) http://www.cryptrec.jp/ より転載 13/17
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/17 格子暗号解読コンテスト Progressive BKZ の計算量理論値 Aono et al. Eurocrypt 2016 2 24.0 sec 攻撃者の計算限界が評価可能となる https://www.latticechallenge.org/
16/17 処理性能の例 メモリ量と演算速度 格子暗号 Ding Key Exchange ( 鍵交換 ) AES 128 レベルの安全性 多変数多項式暗号 Rainbow ( ディジタル署名 ) AES 128 レベルの安全性 符号暗号 Classic McEliece ( 暗号化 ) AES 256 レベルの安全性 アリス : 848 バイトボブ : 896 バイト 公開鍵 :148.5 キロバイト秘密鍵 : 97.9 キロバイト署名 : 64バイト 公開鍵 :1357.8 キロバイト秘密鍵 : 14.1 キロバイト暗号文 : 240 バイト 鍵生成 : 1.31 ミリ秒暗号化 : 1.71 ミリ秒復号化 : 1.19 ミリ秒 鍵生成 : 394 ミリ秒暗号化 : 0.182 ミリ秒復号化 : 0.106 ミリ秒 鍵生成 : 1938.1 ミリ秒暗号化 : 0.095 ミリ秒復号化 : 0.148 ミリ秒 https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions
17/17 まとめ NIST PQC 標準化では 69 件投稿があった - 格子暗号 多変数多項式暗号 符号暗号など 2018 年から 3~5 年かけて評価を行なう - 幾つかの最終候補を選定する予定 2030 年迄は SP 800-57 Part I も利用可能