The elliptic curve discrete logarithm problem and equivalent hard problems for elliptic divisibility sequences
arXiv:0803.0728 · doi:10.1007/978-3-642-04159-4_20
Abstract
We define three hard problems in the theory of elliptic divisibility sequences (EDS Association, EDS Residue and EDS Discrete Log), each of which is solvable in sub-exponential time if and only if the elliptic curve discrete logarithm problem is solvable in sub-exponential time. We also relate the problem of EDS Association to the Tate pairing and the MOV, Frey-Rück and Shipsey EDS attacks on the elliptic curve discrete logarithm problem in the cases where these apply.
18 pages; revised version includes some small mathematical corrections, reformatted