トレース2の楕円曲線上の離散対数問題について

概要

論文の詳細を見る
楕円離散対数問題に対する効果的なアルゴリズムは, ほんの二, 三しか知られていない.即ち, Menezes, 岡本, Vanstone[6]はsupersingularな楕円曲線上の離散対数問題をWeil pairingを用いて, その定義体の拡大体の乗法群上の離散対数問題に帰着させることが出来ることを示し(MOV還元法), Frey, Ruckは, Take pairingを用いて, この結果の一般の曲線のdivisor class group上の離散対数問題への一般化を与えた(FR還元法).最近では, Semaev[10], Smart[13], 佐藤, 荒木[9]によって, 有限素体上定義されたanomalous楕円曲線と呼ばれる楕円曲線上の離散対数問題が, その定義体を加法群と見た時の離散対数問題に帰着されることが示された.ここでは, MOV還元法とFR還元法の効果の比較を行なう.まず, トレースが2の楕円曲線を除いて, MOV還元法とFR還元法の効果は等価であることを示し, 即ち, トレースが2の楕円曲線が, FR還元法が有効でかつ, MOV還元法が有効でない唯一の楕円曲線であることを示す.次に, FR還元法とは異なるpairingを用いて, トレースが2の楕円曲線上の離散対数問題を, 有限体の乗法群上の離散対数問題に帰着させる詳しいアルゴリズムを提案する.
社団法人電子情報通信学会の論文
1998-07-31