トロピカル楕円曲線論における計算困難問題の探究と暗号技術への応用

整理番号 20200030
種別 若手研究-短期研究員
研究計画題目 トロピカル楕円曲線論における計算困難問題の探究と暗号技術への応用
研究代表者 Jo Hyungrok(筑波大学 システム情報系・研究員)
研究実施期間 2021年3月23日(火)~ 2021年3月26日(金)
研究分野のキーワード 暗号理論、楕円曲線暗号、トロピカル幾何
本研究で得られた成果の概要 楕円曲線理論では、有限体上の楕円曲線の点PとQが与えられたとき、離散対数log_P Q を求める問題を楕円曲線上の離散対数問題と呼ぶ。楕円曲線上の離散対数問題は暗号への応用があり、特に、公開鍵暗号技術によく使われている。しかし、楕円曲線上の離散対数問題を現実的な時間内で解ける量子アルゴリズムの発見から、量子アルゴリズムに耐性を持つ新しい暗号技術が要求されている。

本研究の目的は、トロピカル楕円曲線にも群構造があることに着目し、楕円曲線上の離散対数問題の代替として、トロピカル楕円曲線上の離散対数問題を設計し、その問題の困難性について調査することであった。

結論から言うと、トロピカル楕円曲線上の離散対数問題は定義可能であるが、暗号に使えるほどの強度を達成するものではないことがわかった。 群構造の側面から既存の楕円曲線と異なる大きな違いの一つは、トロピカル楕円曲線の群構造は、トロピカル楕円曲線内で唯一に存在するサイクル上で定義され、単位円と同型となる。つまり、トロピカル楕円曲線のサイクル上の点PとQが与えられたとき、離散対数log_P Q を求める問題は、ユークリッドノルム持つ実数上の単位円で距離を測定する問題に帰着し、問題は平易となる。難しい問題へ修正する一つの案として、有限体上のトロピカル楕円曲線を考えることが挙げられるが、今までの調査ではそのような研究は知られておらず、トロピカル幾何の構成から言うと不可能かもしれない。今回の研究は研究期間が短く、この問題についてはまだまだ様々な側面から再考する余地があると思われる。

一方、耐量子計算機暗号(Post-Quantum Cryptography)の中で同種写像暗号(Isogeny-based cryptography)という研究分野がある。それは超特異楕円曲線の同種写像関係における計算困難問題を安全性の根拠としている。最近では、超特異楕円曲線理論のトロピカルバージョンが研究され、トロピカル楕円曲線理論が精巧に具体化されている。このことから、同種写像暗号の類似研究から考えられる別のシードとしてトロピカル超特異楕円曲線理論を調査・研究することは興味深いことと思われ、今後の課題となる。
組織委員(研究集会)
参加者(短期共同利用)
Jo Hyungrok(筑波大学 システム情報系・研究員)
アドバイザー 阿部 拓郎(九州大学マス・フォア・インダストリ研究所・教授)