高木研究室│九州大学 マス・フォア・インダストリ研究所

本研究室では情報社会のインフラのひとつである暗号技術について、数理的な角度から実装まで幅広く扱っています。

English

Japanese

九州大学
マス・フォア・インダストリ研究所
高木研究室
〒819-0395 福岡市西区元岡744番地

Tel: 092-802-4456
Fax: 092-802-4405

ペアリング暗号の安全性に関する計算実験

 暗号方式の安全性を評価する際,その暗号に対する解読アルゴリズムの考慮は必要不可欠である.多くの公開鍵暗号方式は, 計算困難な数学的問題を安全性の根拠においているため,その根拠としている数学的問題を有限時間内に解く事が出来ないことを実証出来れば,その暗号方式は安全であると考えらえる.

 ペアリング暗号方式は,楕円曲線上の離散対数問題(Discrete Logarithm Problem)および有限体上の離散対数問題の困難性を安全性の根拠としている.一般の楕円曲線上の離散対数問題の計算アルゴリズムとしてはPollardのρ法が知られており,また,有限体上の離散対数問題の計算アルゴリズムにはより高速な指数計算法クラスのアルゴリズムが知られている.指数計算法クラスのアルゴリズムは有限体の標数に対して,以下のように有効性が分かれている.

  • 大きな標数の有限体: 数体篩法 (Number Field Sieve)
  • 小さな標数の有限体: 関数体篩法 (Function Field Sieve)

  現在は,標数3を用いたペアリングの高速実装が行われているという背景から, その安全性の基盤となる有限体GF(3^(6n))上の離散対数問題の困難性について 計算実験を行っており,923ビットの離散対数問題の計算に成功している. この記録は有限体GF(3^(6n))上の離散対数問題の計算世界記録となっている (2012年6月現在).

ペアリング暗号の安全性

有限体上の離散対数問題の計算世界記録 (2012年6月現在)

有限体 GF(p) GF(2^n) GF(p^3) GF(p^30) GF(3^(6n))
著者 Kleinjung et al. Joux et al. Joux et al. Joux and Lercier Hayashi et al.
日付 2007/2/5 2005/9/22 2006/8/23 2005/9/11 2012/4/24
アルゴリズム 数体篩法 関数体篩法 数体篩法 関数体篩法 関数体篩法
関係探索
ステップ
Many CPUs 16個のItanium2
(1.3GHz)×4ノード
16個のAlpha
プロセッサ(1.15GHz)
16個のAlpha
プロセッサ(1.15GHz)
Xeon(2.83GHz)
計212コア
線形代数
ステップ
12~24個の
Xeon(3.2GHz)
16個のItanium2
(1.3GHz)×4ノード
16個のAlpha
プロセッサ(1.15GHz)
16個のAlpha
プロセッサ(1.15GHz)
Xeon(2.67GHz)
計252コア
計算時間 33日 17日 19日 12時間 148日
ビット長 532 613 394 556 923




発表論文

  • 早坂健一郎, 青木和麻呂, 小林鉄太郎, 高木剛, "GF(p^12)上の離散対数問題に対する数体篩法の計算機実験", 2013年暗号と情報セキュリティシンポジウム, SCIS2013, 4A1-3, 2013.
  • Takuya Hayashi, Takeshi Shimoyama, Naoyuki Shinohara, Tsuyoshi Takagi, "Breaking Pairing-Based Cryptosystems using EtaT Pairing over GF(3^97)", Asiacrypt 2012, LNCS 7658, pp.43-60, 2012.
  • 林卓也, 下山武司, 篠原直行, 高木剛, "GF(3^n)上のηTペアリングを用いたペアリング暗号の安全性評価", 電子情報通信学会, 信学技報, IEICE-ISEC2012-43, 2012.
  • Naoyuki Shinohara, Takeshi Shimoyama, Takuya Hayashi, Tsuyoshi Takagi,
    "Key Length Estimation of Pairing-Based Cryptosystems using EtaT Pairing",
    The 8th International Conference on Information Security Practice and Experience, ISPEC 2012, LNCS 7232, pp.228-244, 2012.
  • Naoyuki Shinohara, Takeshi Shimoyama, Takuya Hayashi, Tsuyoshi Takagi,
    "Estimation of Time Complexity of Solving DLP over GF(3^6n)",
    2012年暗号と情報セキュリティシンポジウム, SCIS 2012, 1B3-1, 2012.
  • 坂本恭一, 林卓也, 高木剛, "数体篩法におけるJoux-Lercier の多項式選択法について", 2012年暗号と情報セキュリティシンポジウム, SCIS2012, 2B1-2, 2012.
  • Kenichiro Hayasaka, Tsuyoshi Takagi, "An Experiment of Number Field Sieve over GF(p) of Low Hamming Weight Characteristic", International Workshop on Coding and Cryptology, IWCC 2011, LNCS 6639, pp. 191-200, 2011.
  • Takuya Hayashi, Naoyuki Shinohara, Lihua Wang, Shin'ichiro Matsuo,
    Masaaki Shirase, Tsuyoshi Takagi, "Solving a 676-bit Discrete Logarithm
    Problem in GF(3^{6n})", 13th International Conference on Practice and
    Theory in Public Key Cryptography, PKC 2010, LNCS 6056, pp.351-367, 2010.
  • 林卓也, 高木剛, "離散対数問題解読世界記録更新への道-676 ビットの解読-," 情報処理,Vol.51, No.9, pp.1181-1188, 2010.
  • 早坂健一郎,高木剛, "素体GF(p)上の離散対数問題に対する数体篩法の比較実験", 情報処理学会 コンピュータセキュリティシンポジウム, CSS 2010,2B1-1, pp.489-494, 2010.
  • 早坂健一郎, 高木剛, "低Hamming重み標数の素体上における数体篩法の計算機実験", 電子情報通信学会情報セキュリティ研究会, IEICE-ISEC2009-87, pp.53-60, 2010.
  • 林卓也,篠原直行,王立華,松尾真一郎,白勢政明,高木剛, "GF(3^(6・71))上の離散対数計算実験(676ビットの解読)", 2010年暗号と情報セキュリティシンポジウム, SCIS 2010,4D2-3, 2010.
  • 林卓也,白勢政明,高木剛, "GF(3^6)のn次拡大体における関数体篩法の実装実験", 情報処理学会 コンピュータセキュリティシンポジウム, CSS 2009, pp.21-26,2009.(CSS2009学生論文賞受賞)
  • 林卓也,白勢政明,高木剛, "GF(3^n)上の関数体篩法の実装実験", 情報処理学会論文誌,Vol.50,No.9,pp.1956-1967,2009.
  • 林卓也,白勢政明,高木剛, "GF(3^n)上の関数体篩法における篩処理の実装実験", 2009年暗号と情報セキュリティシンポジウム, SCIS 2009,3F1-1,2009.
  • 林卓也,白勢政明,高木剛, "GF(3^n)上の関数体篩法の実装", 情報処理学会 コンピュータセキュリティシンポジウム, CSS 2008,pp.193-198,2008.
  • 林卓也,白勢政明,高木剛, "GF(3^m)上の離散対数問題の困難性に関する実験", 2008年暗号と情報セキュリティシンポジウム, SCIS 2008,3B1-5,2008.
PAGETOP