Algebraic approaches for solving isogeny problems of prime power degrees
type: Item
instance of: scholarly article
title: Algebraic approaches for solving isogeny problems of prime power degrees
zbMATH Open document ID: 1465.14027
author: Yasushi Takahashi
author: Momonari Kudo
author: Ryoya Fukasaku
author: Yasuhiko Ikematsu
author: Masaya Yasuda
author: Kazuhiro Yokoyama
published in: Journal of Mathematical Cryptology
publication date: 2021-05-25T00:00:00Z
review text: Since 2006, isogenies between elliptic curves have began to be used for constructing several cryptographic schemes and hash functions. The security of isogeny cryptosystems is based on the general isogeny problem: Given two elements \(j\), \(\tilde{j}\) of a finite field \(\mathbb{F}_q\), to find an isogeny \(\phi : E \rightarrow \tilde{E}\), if exists, such that \( j(E) = j\) and \(j(\tilde{E}) = \tilde{j}\), where \(j(E)\) denotes the \(j\)-invariant of an elliptic curve \(E\). In the supersingular case, it is sufficient to take \(\mathbb{F}_{p^2}\) as the base field for a prime \(p\), since every supersingular curve over \(\mathbb{F}_p\) is isomorphic to one defined over \(\mathbb{F}_{p^2}\). An interesting variant of this problem is the case where the degree of \(\phi\) is known. In this paper, practical approaches for solving isogeny problems are considered, and in particular, the supersingular isogeny graph path-finding problem of prime power degree \(\ell = \ell_0^e\), for small \(\ell_0\), is discussed. Two algebraic approaches are proposed for solving this problem. The basic strategy is the reduction of the isogeny problem to a system of algebraic equations. The first approach uses the modular polynomial of prime level \(\ell_0\). The system of equations of modular polynomial is divided into two, and their Gröbner bases are computed to efficiently find \(j\)-invariants of intermediate curves between given two isogenous elliptic curves \(E\) and \(\tilde{E}\). The second approach takes an intermediate curve \(E_0\) between \(E\) and \(\tilde{E}\), and considers kernel polynomials \(F(x)\) and \(\tilde{F}(\tilde{x})\) of two isogenies \(\phi : E \rightarrow E_0\) and \(\tilde{\phi} : \tilde{E} \rightarrow E_0\). Since the curve \(E_0\) is unknown, its Weierstrass coefficients are considered as variables, and represent \( F(x)\) and \(\tilde{F}(\tilde{x})\) as certain multivariate polynomials. Finally, by using Vélu's formulae for isogenies, \(\phi \) and \(\t…
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 7350875
zbMATH Keywords: elliptic curves
zbMATH Keywords: isogenies
zbMATH Keywords: Vélu's formulae
zbMATH Keywords: Gröbner basis computation
reviewed by: Dimitros Poulakis
describes a project that uses: SIKE
describes a project that uses: Magma
MaRDI profile type: Publication
full work available at URL: jmc-2020-0072
OpenAlex ID: W3112124927
cites work: On the cost of computing isogenies between supersingular elliptic curves
cites work: Q4693774
cites work: A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves
cites work: Q4265362
cites work: The Magma algebra system. I: The user language
cites work: Fast algorithms for computing isogenies between elliptic curves
cites work: CSIDH: an efficient post-quantum commutative group action
cites work: Cryptographic hash functions from expander graphs
cites work: Constructing elliptic curve isogenies in quantum subexponential time
cites work: Ramanujan Graphs in Cryptography
cites work: Q5690494
cites work: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
cites work: Supersingular isogeny graphs and endomorphism rings: reductions and solutions
cites work: Q4213383
cites work: Efficient computation of zero-dimensional Gröbner bases by change of ordering
cites work: Constructing Isogenies between Elliptic Curves Over Finite Fields
cites work: On the Security of Supersingular Isogeny Cryptosystems
cites work: Computational problems in supersingular elliptic curve isogenies
cites work: Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies
cites work: Isogeny-Based Quantum-Resistant Undeniable Signatures
cites work: Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
cites work: Elliptic Curve Cryptosystems
cites work: Q3718617
cites work: Counting points on elliptic curves over finite fields
cites work: Q4317891
cites work: The Arithmetic of Elliptic Curves
cites work: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves
cites work: Claw finding algorithms using quantum walk
cites work: Endomorphisms of Abelian varieties over finite fields
cites work: Parallel collision search with cryptanalytic applications
cites work: Q5631239
DOI: 10.1515/JMC-2020-0072
description: scientific article; zbMATH DE number 7350875