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

• Item type: Journal(1)
• 公開日: 2009-09-15
• タイトル: GF(3^<i>n</i>) 上の関数体篩法の実装実験
• タイトル / 言語: en
• タイトル: An Experiment on Implementation of the Function Field Sieve over GF(3^<i>n</i>)
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：社会を活性化するコンピュータセキュリティ技術
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Information Science, Future University Hakodate
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Information Science, Future University Hakodate
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Information Science, Future University Hakodate
• 著者名: 林, 卓也; 白勢, 政明; 高木, 剛
• 著者名(英): Takuya, Hayashi; Masaaki, Shirase; Tsuyoshi, Takagi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 高速実装が可能な実用的ペアリングとして有限体GF(3^<i>n</i>) 上の超特異曲線を用いたη_<i>T</i> ペアリングが知られている．このη_<i>T</i> ペアリングを利用したペアリング暗号の安全性はGF(3^<i>n</i>) 上の離散対数問題（DLP）の困難性を根拠とする．しかし，GF(3^<i>n</i>) 上のDLPの困難性に関する計算実験の報告は数例のみであり，その困難性の正確な評価を行うにはデータが不十分となっている．本稿では，小さな標数の有限体上のDLPに対する漸近的に最も高速な計算アルゴリズムとして知られている関数体篩法の高速実装を行った．関数体篩法の計算の中で最も計算量を必要とするのは篩処理であるため，GF(3)[<i>x</i>] 上の篩処理についてwindow法を用いた高速化を行った．その結果，GF(3^<i>n</i>) 上のDLP計算実験においてGrangerらが実験を行った従来の世界記録であるGF(3²²²)（352ビット）を大きく上回るGF(3²⁷⁷)（440ビット）上のDLPの計算に成功した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The η_<i>T</i> pairing on supersingular curve over finite field GF(3^<i>n</i>) is known as one of the most efficient pairings. The security of pairing based cryptosystems using the η_<i>T</i> pairing is based on the difficulty of the discrete logarithm problems (DLP) over GF(3^<i>n</i>). The most efficient algorithm for solving the DLP over finite fields of small characteristic is the function field sieve. However, few experiments on the difficulty of the DLP over GF(3^<i>n</i>) have been reported. In this paper, we implemented the function field sieve and experimented the difficulty of the DLP over GF(3^<i>n</i>). We present a faster implementation of the sieving in GF(3)[<i>x</i>] which is the most time-consuming step in the function field sieve. From this improvement, we succeeded solving the DLP over GF(3²⁷⁷) of 440 bits. This is currently the top-record bit-size of the function field sieve over GF(3^<i>n</i>) to the best of our knowledge.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 50, 号 9, p. 1956-1967, 発行日 2009-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764