代数曲線のセコビ多様体に関するアルゴリズムとその公開鍵暗号への応用についての研究

点击翻译按钮获取中文摘要

今年度は、有限体上定義された種数2の超楕円曲線のヤコビ多様体の群位数計算アルゴリズムの具体的構成に取り掛かった。有限体上の楕円曲線上の離散対数問題の計算量的困難性に安全性の根拠を置く「楕円曲線暗号」は安全性・効率ともに優れた公開鍵暗号であるが、暗号に適した曲線を探索するには、楕円曲線の位数計算(元の個数を数える)アルゴリズムを用いる。楕円曲線の代わりに種数2以上の曲線を利用した「代数曲線暗号」を設計しようとするならば、曲線のヤコビ多様体の群位数計算を実行するアルゴリズムが必要である。このアルゴリズムを構成するには、ヤコビ多様体の定義方程式、加法公式そして倍算公式が必要である。定義方程式と加法公式は1990年にGrantによって与えられ、倍算公式は2003年に研究代表者によって与えられた。今年度は、それらを道具として群位数計算アルゴリズムの構成に着手した。理論的には、楕円曲線のときのアルゴリズムの手順と同様であるが、種数2以上の場合は加法X+Yを計算するためにはXとYの性質の違いによる場合わけをせねばならず、そのため楕円曲線の場合と比べ極めて煩雑なアルゴリズムとなり計算機に実装するには大変不便なものとなる。しかし、数値実験により、上のような場合分けは実際は殆ど必要ないことがわかり、(確率的アルゴリズムとなるが)かなり簡単になることが分かった。現在は、簡略化されたアルゴリズムを書き下し実装作業を行いつつ発表準備をしている段階である。