SCOPE 多変数多項式システム を用いた安全な暗号技術の研究 の活動 研究代表者 : 安田貴徳 (ISIT), 研究分担者 :Xaver Dahan ( お茶の水女子大 ), Yun-Ju Huang (ISIT), 高木剛 ( 九州大学 ), 櫻井幸一 ( 九州大学, ISIT) この研究は総務省戦略的情報通信研究開発推進事業 (SCOPE) 平成 27 年度イノベーション創出型研究開発フェーズ II(no. 0159-0016) の委託を受けている
総務省戦略的情報通信研究 開発推進事業 (SCOPE) 重点領域型研究開発 (ICT イノベーション創出型 ) 過去には 平成 20 年度 ~ 平成 22 年度研究課題 量子コンピュータの出現に対抗し得る公開鍵暗号の研究 o 研究代表者 : 辻井重男 ( 中央大学研究開発機構 ) 研究分担者 : 笠原正雄 ( 中央大学 ), 境隆一 ( 中央大学 ), 村上恭通 ( 中央大学 ), 只木孝太郎 ( 中央大学 ), 原山友弘 ( 中央大学 ) 我々の研究課題 多変数多項式システムを用いた安全な暗号技術の研究 25 年度 26 年度 27 年度 4 月 7 月フェーズ I 3 月 4 月フェーズ II 3 月 現在 MELT up フォーラム 2015/6/19 2 3 月
3 つの大きな目標 1. 多変数多項式公開鍵暗号の安全性の厳密評価 o o 様々な攻撃方法がある中で どの場合にどれが最も効果的か見極める 公平で信頼のできる基準作成 2. 課題を克服した新方式の開発 o o 課題 1: 鍵長問題 課題 2: 暗号方式 3. 耐量子暗号研究の拠点形成 o o 日本での多変数多項式公開鍵暗号 ( および耐量子暗号 ) の研究の強化 ワークショップの開催 MELT up フォーラム 2015/6/19 3
目標 1 多変数多項式公開鍵暗号の安全性の厳密評価 MELT up フォーラム 2015/6/19 4
解読コンテスト 公平で信頼のできる基準作成するには o 解読コンテストを行う方法が良い o 攻撃手法の発展も促せる 解読コンテストは攻撃者の計算限界点を知るために必要 暗号標準化への通過点 o RSA チャレンジ (RSA Laboratores) 素因数分解問題の解読コンテスト o ECC チャレンジ (Certcom) 楕円曲線離散対数問題の解読コンテスト o Lattce チャレンジ (TU Darmstadt) 対象 : 最短ベクトル問題 2008 年 現在も (http://www.lattcechallenge.org/) 現在の公開鍵基盤 耐量子暗号の候補 MELT up フォーラム 2015/6/19 5
MQ チャレンジ 今年の 4 月 1 日からスタート. https://www.mqchallenge.org/ MELT up フォーラム 2015/6/19 6
MP チャレンジで扱う問題 m n j n m m j m j n m n j n j j n n j n j j n d c b a f d c b a f d c b a f, 1 1 ) ( ) ( ) ( 1 2, 1 1 (2) (2) (2) 1 2 1, 1 1 (1) (1) (1) 1 1 ),..., ( ),..., ( ),..., ( MQ 問題 : 以下の 2 次多変数多項式システムの解を求めよ 一般に MQ 問題の解読は困難と考えられている 2015/6/19 MELT up フォーラム 7 但し 係数 a j (k), b (k), c (k), d k は全て基礎体 GF(q) の元
MQ 問題の作成期間 平成 26 年度を問題作成の準備期間とした o 暗号方式 署名方式の調査 o 様々な攻撃法の調査と実験 6 種類の問題を用意 計算サーバ : 日本 HP 製 CPU:2.13GHz8 コア 8 個メモリ :2TB Type m と n の関係基礎体対象 I m = 2n GF(2) 暗号方式 II m = 2n GF 2 8 暗号方式 III m = 2n GF 31 暗号方式 IV n 1,5m GF(2) 署名方式 V n 1,5m GF 2 8 署名方式 VI n 1,5m GF 31 署名方式 MELT up フォーラム 2015/6/19 8
解読状況 1 Type I(m = 2n, GF 2 ) の場合 MELT up フォーラム 2015/6/19 9
解読状況 2 Type I(n 1.5m, GF 2 8 ) の場合 MELT up フォーラム 2015/6/19 10
Faugère の F 5 アルゴリズムの計算量 MQ 問題解読の最も基本的な数学的道具はグレブナー基底である. Faugère は効率的計算アルゴリズム F 4 と F 5 を考案 [1][2]. MQ 問題解読の計算量 [3] O( m n + d reg 1 d reg ω ) ここで 2 < ω < 3, d reg は多変数多項式システムに依存するある不変量. Reference: [1] Faugère, J.C., A New Effcent Algorthm for Computng Gröbner Bases (F4)", Journal of Pure and Appled Algebra, vol. 139, 1999. [2] Faugère, J.C., A New Effcent Algorthm for Computng Gröbner Bases (F5)", ISSAC, ACM press, 2002. [3] Bettale, L., Faugère, J.C. and Perret L., Hybrd approach for solvng multvarate systems over fnte felds", J. Math. Crypt. vol. 2, 2008. MELT up フォーラム 2015/6/19 11
目標 2 課題を克服した新方式 の開発 MELT up フォーラム 2015/6/19 12
多変数多項式公開鍵暗号 (MPKC) 特徴 o 耐量子暗号の候補 o 様々な暗号方式 署名方式 暗号方式 : Smple Matr scheme, ZHFE scheme 署名方式 : UOV, Ranbow o 暗号化 復号化 署名生成 検証が効率的 ( 特に復号化 署名生成が効率的 ) 問題 o MPKC の方式の正確な安全性評価 o (RSA と比べて ) 膨大な鍵長 o 安全な暗号方式 MELT up フォーラム 2015/6/19 13
MPKC の簡単な歴史 1988 松本 - 今井方式 (MI) の提案 Shorのアルゴリズム (1994) o Patarnによる攻撃 (1995) 1996 HFE(Hdden Feld Equaton) 暗号方式 o Kpns-Shamrによる攻撃 (1999) o 署名方式 Quartz への応用 (1996) 1997 (Balanced) Ol and Vnegar 署名方式 o Kpns-Shamrによる攻撃 (1998) 1999 UOV(Unbalanced Ol and Vnegar) 署名方式 o Kpns-Shamrの攻撃の改良 (UOV 攻撃 ) 1999 FaugèreによるF4アルゴリズム (Gröbner 基底の効率的計算方法 ) の開発 2002 EU が SFLASH 署名方式を暗号規格化 (NESSIE) o 程なく複数の研究者によって解読される 2005 Ranbow 署名方式 (UOV の多層化 ) 2013 Smple Matr 方式の提案 2014 ZHFE 方式の提案 MELT up フォーラム 2015/6/19 14
MPKC の基本構造 トラップドア一方向関数 1. 2 次の多変数多項式写像で逆写像計算が容易なものを選ぶ G: K n K m 秘密鍵 2. 2 つのアファイン写像を選ぶ F: K n K m 公開鍵 3. 選んだ多変数多項式写像とアファイン写像を合成する MELT up フォーラム 2015/6/19 15
MPKCの暗号方式と署名方式 公開鍵 : F 秘密鍵 : G, R, L F が単射の場合 暗号方式に利用できる. 多項式の評価計算をするだけ ベクトル空間 K n a F 計算が簡単 ベクトル空間 K m F(a) 平文 関数 F 1 秘密鍵を知っている人だけが計算できる 暗号文 MELT up フォーラム 2015/6/19 16
MPKCの暗号方式と署名方式 公開鍵 : F 秘密鍵 : G, R, L F が全射の場合 署名方式に利用できる. 多項式の評価計算をするだけ ベクトル空間 K n S = F 1 (M) F 計算が簡単 ベクトル空間 K m M 署名 関数 F 1 秘密鍵を知っている人だけが計算できる 文書 MELT up フォーラム 2015/6/19 17
MPKC は鍵長が大きい 鍵長削減問題 o 署名方式 Ranbow は RSA の 100~200 倍の鍵長 鍵長削減手法の開発 o o o その他 o Takanor Yasuda,Tsuyosh Takag,Kouch Sakura, Effcent varant of Ranbow wthout trangular matr 鍵の圧縮表示を用いる手法 representaton, The 2015 Asan Conference on Avalablty, Relablty and Securty (AsaARES2014),Sprnger LNCS, Vol.8407, pp.532-541, 2014. Takanor Yasuda, Tsuyosh Takag, and Kouch Sakura, Securty of multvarate sgnature scheme usng non-commutatve rngs, IEICE Transactons on Fundamentals of Electroncs, Communcatons 非可換環を用いる手法 and Computer Scences, Vol.E97-A, No.1, pp.245-252, 2014. Takanor Yasuda, Tsuyosh Takag, and Kouch Sakura, Effcent varant of Ranbow usng sparse secret keys, Innovatve Informaton Scence & Technology Research まだらな鍵を用いる手法 Group, Journal of Wreless Moble Networks, Ubqutous Computng, and Dependable Applcatons (JoWUA), Vol.5, No.3, pp.3-13, 2014. 効率性の向上手法 2 次形式を用いた署名など MELT up フォーラム 2015/6/19 18
安全な暗号方式 署名方式に比べて 暗号方式は作りにくい o 署名方式 :UOV 方式 Ranbow 方式 o 暗号方式 :ZHFE 方式 (2014) Smple Matr 方式 (2013) o 様々な暗号方式が開発されてきたが その多くに効率的攻撃法が見つかっている :MI, HFE, l-ic,trangular, TTM, Square 今年度は暗号方式の開発 o 研究中 その他進行中の関連研究 o 拡大体上の ECDLP の多変数多項式システムを用いた攻撃 o MQ 問題の新しい攻撃方法 MELT up フォーラム 2015/6/19 19
目標 3 耐量子暗号研究の 拠点形成 MELT up フォーラム 2015/6/19 20
量子コンピュータの普及により 耐量子暗号 RSA 暗号 (1978) 最も普及している 現在の公開鍵暗号基盤 楕円曲線暗号 (1985) ポスト RSA 暗号 暗号通信世界基準 著作権保護技術 その他 多変数多項式公開鍵暗号 格子ベース暗号 符号ベース暗号 ハッシュベース暗号 MELT up フォーラム 耐量子暗号の候補 2015/6/19 21
耐量子暗号の研究状況 公開鍵暗号の発明 (1976) 楕円曲線暗号の発明 (1985) Shor のアルゴリズム (1994) 現在 (2015) RSA 暗号の発明 (1977) PQCrypto2006 耐量子暗号の開発研究 国際会議 PQCrypto(2006~) o 1 年半に 1 度開催 2006 n Leuven, 2008 n Cncnnat, 2010 n Darmstadt, 2011 n Tape, 2013 n Lmoges, 2014 n Waterloo o PQCrypto2014 では 125 名の参加者が集まる NIST ワークショップ ETSI( 欧州電気通信標準化機構 ) ワークショップ MELT up フォーラム 2015/6/19 22
ワークショップの開催 o 2013 年 3 月 2 日 -3 日 Forefront Workshop for the Promoton of the Academa-Industry Cooperaton Applcaton of Computatonal Number Theory to Secure Socal Infrastructure (II) - Solvng Multvarate Polynomal Systems and Related Topcs - 場所 : 福岡百道浜 参加者 : 約 30 名 基調講演 :Jean-Charles Faugère 研究ディレクタ (INRIA) o 2013 年 11 月 14 日 -15 日 Workshop: Post-Quantum Cryptography and Its Related Topcs 場所 : 福岡百道浜 参加者 : 約 30 名 基調講演 :Jnta Dng 教授 ( シンシナティ大学 ) o 2014 年 11 月 3 日 -4 日 Workshop Post-Quantum Cryptography: Recent Results and Trends 場所 : 福岡百道浜 参加者 : 約 35 名 基調講演 :Johannes Buchmann 教授 ( ダルムシュタット工科大学 ) MELT up フォーラム 2015/6/19 23
PQCrypto 2016 過去に 6 度開催 o 2006 Leuven, 2008 Cncnnat, 2010 Darmstadt, 2011 Tape, 2013 Lmoges, 2014 Waterloo 7 度目の PQCrypto を福岡で! o 誘致活動が実り 見事 福岡開催が決定 PQCrypto 2016 o Wnter School o 本会議 2016 年 2 月 22 日 ~23 日 2016 年 2 月 24 日 ~26 日 場所 : 西新プラザ ( 九州大学 ) Web ページ : https://pqcrypto2016.jp/ MELT up フォーラム 2015/6/19 24
SCOPE の活動報告 まとめ 目標 1 多変数多項式公開鍵暗号の安全性の厳密評価目標 2 課題を克服した新方式の開発目標 3 耐量子暗号研究の拠点形成 MQ チャレンジを開催しています o MQ Challenge Homepage https://www.mqchallenge.org/ PQCryto2016 が福岡で 2 月に開催されます o PQCrypto2016 Homepage https://pqcrypto2016.jp/ MELT up フォーラム 2015/6/19 25