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

IR IPSJ HANDLE Web Site

Bibliographic Information

Other Title
  • GF(3<sup><i>n</i></sup>) 上の関数体篩法の実装実験
  • GF(3[n])ウエ ノ カンスウタイフルイホウ ノ ジッソウ ジッケン
  • An Experiment on Implementation of the Function Field Sieve over GF(3<sup><i>n</i></sup>)

Search this article

Abstract

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

The ηT pairing on supersingular curve over finite field GF(3n) is known as one of the most efficient pairings. The security of pairing based cryptosystems using the ηT pairing is based on the difficulty of the discrete logarithm problems (DLP) over GF(3n). 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(3n) have been reported. In this paper, we implemented the function field sieve and experimented the difficulty of the DLP over GF(3n). We present a faster implementation of the sieving in GF(3)[x] which is the most time-consuming step in the function field sieve. From this improvement, we succeeded solving the DLP over GF(3277) of 440 bits. This is currently the top-record bit-size of the function field sieve over GF(3n) to the best of our knowledge.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top