CSIDHにおける同値な秘密鍵の探索と秘密鍵空間の解析

同種写像暗号は耐量子計算機暗号の候補の一つであり，同種写像問題の計算困難性を安全性の根拠としている．特にCSIDHは鍵共有方式であり，超特異楕円曲線の同型類に対するイデアル類群の作用を利用する．CSIDHの秘密鍵空間はベクトル空間の部分集合であり，与えられたベクトルに対応する作用が一意に定まる．しかし一方で，その対応関係は１対１でなく，与えられた作用に対応するベクトルは必ずしも一意でない．実際，自明な作用に対応するベクトルとして(3k,...,3k)（kは整数）があることが，2021年に小貫らとCastryckらによって同時に示されている．そこで本研究では，自明な作用に対応するベクトルを探索するためのρ法探索法を開発し，実際に30～40bit標数に対して探索実験を行った．さらに，実験により発見したベクトルを用いて格子簡約を行い，ベクトル空間全体から自明な作用への写像の核空間に対して，その線形空間としての次元を評価する．加えて，核空間内の一次独立なベクトルのノルムを評価し，自明な作用に対応するベクトルの中で秘密鍵空間に入るものがあるか調べる．

Isogeny-based cryptosystem is one of the candidates for post-quantum cryptography, relying on the computational complexity of the isogeny problem for its security. In particular, CSIDH is a key exchange method that uses the action of the ideal class group on isomorphism classes of supersingular elliptic curves. The secret key space of CSIDH is a subset of a vector space, and the action corresponding to a given vector is unique. However, on the other hand, this correspondence is not one-to-one, and a vector corresponding to a given action is not necessarily unique. In fact, it has been simultaneously discovered by Onuki et al. and Castryck et al. in 2021 that there exist vectors corresponding to trivial actions, such as (3k, . . . , 3k) (k is an integer). Therefore, in this paper, we develop a ρ-method search algorithm to search vectors corresponding to trivial actions and make search experiments for 20-40bit characteristics. Furthermore, using the discovered vectors from the experiments, we perform lattice reduction and evaluate the dimension of the kernel space of a map to the actions of the ideal class group from the vector space as a linear space. Additionally, weevaluate the L1-norms of linearly independent vectors in the kernel space and investigate whether there are vectors corresponding to trivial actions that belong to the secret key space.