GF(36) のn次拡大体における関数体篩法の実装実験

• Item type: Symposium(1)
• 公開日: 2009-10-19
• タイトル: GF(36) のn次拡大体における関数体篩法の実装実験
• タイトル / 言語: en
• タイトル: Implementation of the Function Field Sieve in the MediumPrime-power Case over GF(36n)
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 公開鍵暗号
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属: 公立はこだて未来大学大学院システム情報科学研究科
• 著者所属(英): 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(36n) 上の離散対数問題 (DLP) は，高速実装が可能な GF(3n) 上の超特異楕円曲線における ητペアリングを用いたペアリング暗号において安全性の根拠となる重要な問題の一つである．2006 年に Joux らによって提案された関数体篩法は，GF(qn) において q が中程度 （q ≈ n√n） の有限体上の DLP に対して有効なアルゴリズムである．また，GF(36n) 上の DLP に対して漸近的な計算量では従来の関数体篩法と同等であるが，上記の条件とは異なる n に対して従来の関数体篩法と比較して数倍程効率的である可能性がある．本稿では Joux, Lercier が提案した関数体篩法の GF(36n) 上での実装を行い，従来の関数体篩法との計算実験による比較を行った．その結果，従来の関数体篩法よりも高速に計算可能な拡大次数 n（n = 19, 61 など） が存在することを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The discrete logarithm problems (DLP) over GF(36n) is one of the most importantproblems which is the security basis of the pairing-based cryptosystems using the ηT pairingon supersingular curves over GF(3n). In 2006, Joux and Lercier proposed the new functionfield sieve algorithm which is efficient for solving the DLP over GF(qn) (q = pk) when q is a medium-sized prime-power. The new function field sieve has the same asymptotic complexityas traditional one for solving the DLP over GF(36n). However, it may be more efficient thantraditional one in some n. In this paper, we implemented the new function field sieve overGF(36n) and compared with traditional one by practical experiments. As a result, we confirmedthat the new function field sieve is more efficient than traditional one for solving the DLP overGF(36n) such as n = 19, 61.
• 書誌情報: コンピュータセキュリティシンポジウム2009 (CSS2009) 論文集; 巻 2009, p. 1-6, 発行日 2011-10-12
• 出版者 / 言語: ja
• 出版者: 情報処理学会