  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\"{u}ck and
Shipsey EDS attacks on the elliptic curve discrete logarithm problem in the
cases where these apply.
