Cover attacks for elliptic curves with prime order

Abstract

We give a new approach to the elliptic curve discrete logarithm problem over cubic extension fields ${\mathbb{F}}_{q^3}$. It is based on a transfer: First an ${\mathbb{F}}_q$-rational $(\ell ,\ell ,\ell )$-isogeny from the Weil restriction of the elliptic curve under consideration with respect to ${\mathbb{F}}_{q^3}/{\mathbb{F}}_q$ to the Jacobian variety of a genus three curve over ${\mathbb{F}}_q$ is applied and then the problem is solved in the Jacobian via the index-calculus attacks. Although using no covering maps in the construction of the desired homomorphism, this method is, in a sense, a kind of cover attack. As a result, it is possible to solve the discrete logarithm problem in some elliptic curve groups of prime order over ${\mathbb{F}}_{q^3}$ in a time of $\tilde{O}(q)$.

19 pages

References in corpus (2)

• Thomae's formulae for non-hyperelliptic curves and spinorial square roots of theta-constants on the moduli space of curves
• Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with $(\ell ,\ell ,\ell )$-isogenies