拡大体上の楕円曲線のnon－hyperelliptic 被覆の構成法に関する考察

摘要

GHS 攻撃は，有限体k の拡大体上種数の小さな代数曲線の有理点群での離散対数問題（DLP）を，k 上被覆曲線が存在する場合，被覆曲線のヤコピ多様体でのDLPに帰着させる．特に，Gaudry などによるdouble－1arge－prime attack は被覆曲線としてhypereLLipti ccurveの場合に有効とされ，Diem のdouble－large－primeattack は被覆曲線としてnon－hyperelliptic curve の場合に有効とされている． Non-hyperelliptic curveへの攻撃がhyperelliptic curveへの攻撃に比べてより高速とされている．GHS 攻撃においては，被覆曲線の構成が重要である．今までにnon-hyperelliptic 被覆を構成する2つのアルゴリズムが，Diem と橋詰により示された．本研究では，Diem の手法と橋詰の手法を比較し，それぞれ適用可能な曲線の範囲を示す．次に橋詰の手法を種数2の代数曲線に拡張する．%The GHS attack transfers the discrete logarithm problem(DLP) in the group of rational points of an elliptic curve over an extension of a finite field k, when it has a covering curve over k, into the DLP in the Jacobian variety of the covering curve which has higher genus over the smaller definition field. Gaudry et al.'s double-large-prime attack can be applied if the covering curve is a hyperelliptic curve and Diem's double-large-prime attack can be applied if the covering curve is non-hyperelliptic. It is known that attack to non-hyperelliptic curves is more efficient than to hyperelliptic curves. An important issue in the GHS attack is to construct the covering curve over k explicitly. Until now, two algorithms for non-hyperelliptic covering curves were shown by Diem and Hashizume, et al.. In this paper, we compare the two methods on the classes of the curves each method can be applied. Then Hashizume' method is generalized for genus two hyperelliptic cryptosystems.