正標数の数論の暗号理論への応用

本研究は次世代公開鍵暗号の有力候補である楕円曲線暗号に関してその安全性を高めることを数論的な面から研究するものである。楕円曲線の有限体上の有理点の曲線の位数は安全性に大きく影響する。したがって位数に応じた曲線の性質を調べたり、位数そのものを素早く求めることは極めて重要である。今年度はその線に沿って以下のようなことを行なった。まず、従来知られていたElkiesの方法がなぜ遅いのかを詳細に分析した。その結果(少なくともオーダーとして)これ以上の高速化は無理というのが結論である。これを踏まえて本研究では全く新しい方法を探求し、その実装に成功した。本研究で得られた方法はFrobenius写像そのものを用いない。替りに標数0への標準持ち上げとVerschiebugを用い、高速に位数を求める。この際、正標数の楕円曲線の自己準同型環が標数0へ関手的に持ち上がるという点が重要である。本研究の成果は代数学と計算99(平成11年10月)、暗号と情報セキュリティーシンポジウム2000(平成12年1月)などでアナウンスされ高い関心を集めた。研究の成果としてThe Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting(投稿中)を著した。

本研究は次世代公開鍵暗号の有力候補である楕円曲線暗号に関してその安全性を高めることを数論的な面から研究するものである。楕円曲線の有限体上の有理点の曲線の位数は安全性に大きく影響する。したがって位数に応じた曲線の性質を調べたり、位数そのものを素早く求めることは極めて重要である。今年度はその線に沿って以下のようなことを行なった。まず、従来知られていたElkiesの方法がなぜ遅いのかを詳細に分析した。その結果(少なくともオーダーとして)これ以上の高速化は無理というのが結論である。これを踏まえて本研究では全く新しい方法を探求し、その実装に成功した。本研究で得られた方法はFrobenius写像そのものを用いない。替りに標数0への標準持ち上げとVerschiebugを用い、高速に位数を求める。この際、正標数の楕円曲線の自己準同型環が標数0へ関手的に持ち上がるという点が重要である。本研究の成果は代数学と計算99(平成11年10月)、暗号と情報セキュリティーシンポジウム2000(平成12年1月)などでアナウンスされ高い関心を集めた。研究の成果としてThe Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting(投稿中)を著した。