奇標数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攻撃に対する考察を行った.
2011-02-24