Elliptic curve discrete logarithm and lifting problem

Abstract

No subexponential time algorithm is known yet for the Elliptic Curve Discrete Logarithm Problem(ECDLP) except the cases of singular curves, supersingular curves and anomalous curves. In this paper, we introduce the lifting problem and show that it implies the ECDLP and integer factorization problem(IFP) and we note that finding a point in $E_1(Q)$, the kernel of the reduction map, also implies the ECDLP and the IFP since it solves the lifting problem. Moreover, we analyze the difficulty of the lifting problem by estimating the minimum of the canonical heights on the kernel of the reduction map.