分野別セミナー

同種写像暗号とは，楕円曲線間の同種写像計算問題の困難性に安全性の根拠を置く暗号方式であり，量子計算機でも容易に解読できないポスト量子暗号の一つとして期待されている。近年では，2017年末に同種写像鍵交換アルゴリズムSIKEがポスト量子暗号候補としてNISTに提出されており，その安全性・実用性の研究が進められている。高橋らはSCIS2019において，同種写像問題を代数方程式系の求解に帰着させ，モジュラー多項式を利用した2分割求解法と，Velu公式・核多項式を利用した求解法を提案した。一方で，グレブナー基底計算などの実装方法に強く依存する計算を多く用いていることから，その計算量評価が困難であった。本講演では，計算代数の理論を用いることで高橋らの求解法において現れるイデアルの構造などを明らかにし，漸近計算量の厳密な評価を与える。さらに，2分割法の改良である3分割法を紹介し，今後期待できる高速化改良の見通しを述べる。