Introduction to algebraic approaches for solving isogeny path-finding problems (Theory and Applications of Supersingular Curves and Supersingular Abelian Varieties)

摘要: The isogeny path-finding is a computational problem that finds an isogeny connecting two given isogenous elliptic curves. The hardness of the isogeny path-finding problem supports the fundamental security of isogeny-based cryptosystems. In this paper, we introduce an algebraic approach for solving the isogeny path-finding problem. The basic idea is to reduce the isogeny problem to a system of algebraic equations using modular polynomials, and to solve the system by Gröbner basis computation. We report running time of the algebraic approach for solving the isogeny path-finding problem of 3-power isogeny degrees on supersingular elliptic curves. This is a brief summary of [16] with implementation codes.