GF(3<sup><i>n</i></sup>) 上の関数体篩法の実装実験

スポンサーリンク

概要

論文の詳細を見る
高速実装が可能な実用的ペアリングとして有限体GF(3<sup><i>n</i></sup>) 上の超特異曲線を用いたη<sub><i>T</i></sub> ペアリングが知られている.このη<sub><i>T</i></sub> ペアリングを利用したペアリング暗号の安全性はGF(3<sup><i>n</i></sup>) 上の離散対数問題(DLP)の困難性を根拠とする.しかし,GF(3<sup><i>n</i></sup>) 上のDLPの困難性に関する計算実験の報告は数例のみであり,その困難性の正確な評価を行うにはデータが不十分となっている.本稿では,小さな標数の有限体上のDLPに対する漸近的に最も高速な計算アルゴリズムとして知られている関数体篩法の高速実装を行った.関数体篩法の計算の中で最も計算量を必要とするのは篩処理であるため,GF(3)[<i>x</i>] 上の篩処理についてwindow法を用いた高速化を行った.その結果,GF(3<sup><i>n</i></sup>) 上のDLP計算実験においてGrangerらが実験を行った従来の世界記録であるGF(3<sup>222</sup>)(352ビット)を大きく上回るGF(3<sup>277</sup>)(440ビット)上のDLPの計算に成功した.
2009-09-15

著者

関連論文

もっと見る

スポンサーリンク