奇標数3次拡大体上の楕円曲線に対するB.Smith変換を用いたGHS攻撃

摘要

GHS攻撃は，k_d:=F_(q~d）上定義された代数曲線C_0のヤコビアンの離散対数問題（DLP）をC_0のk:=F_q上の別の曲線H上のヤコピアンのDLPに移して解く攻撃法である．また，代数曲線上のDLPを効率的に解く方法として，種数3以上のhyperelliptic curveに対しては，Gaudry-Theriault-Thome-Diem·Nagaoによるdouble-large-prime algorithm，non-hyperelliptic curveに対してはDiemによるものが知られている．これらの計算量は，前者の場合はO（q~(2-2／g（H）)），後者はO（q~(2-2/（g（H）-1）)）と見積もられており，non-hyperelliptic curve上のDLP （non-HECDLP）はhyperelliptic curve上のDLP （HECDLP）よりも効率的に解けると考えられている．また，B.Smithによると，種数3のhyperelliptic curve H/kの18％程度は，同種写像を用いて種数3のnon-hyperelliptic curveに変換可能となる．GHS攻撃において得られるhyperellipticな被覆曲線H/kに対してB.Smithの変換手法が適用可能ならば，その安全性はnon-hyperelliptic curveと同程度に低下する．本文ではk_3上楕円曲線のhyperellipticな被覆曲線を構成し，B.Smithの変換手法を組み合わせたGHS攻撃に対する考察を行った．