Q = d·G zu berechnen kostet mit Double-and-Add oder einem Leiterverfahren (Ladder) einige hundert Punktoperationen; für die Umkehrung ist auf gut gewählten Kurven kein effizienter klassischer Algorithmus bekannt. Der beste generische Angriff, Pollards Rho-Methode, braucht für eine Gruppe mit Primordnung n etwa √(πn/4) Gruppenoperationen, eine 256-Bit-Kurve bietet also etwa 128-Bit-Sicherheit. Index-Calculus-Verfahren, die diskrete Logarithmen in endlichen Körpern und die Faktorisierung subexponentiell machen, greifen bei Kurven über Primkörpern nicht – deshalb sind EC-Schlüssel so viel kürzer als RSA-Schlüssel.
Kurven werden so gewählt, dass bekannte Abkürzungen nicht greifen: anomale Kurven (Smarts Angriff), Kurven mit kleinem Einbettungsgrad (MOV-Transfer über Pairings, den pairingfreundliche Kurven bewusst in Kauf nehmen), Gruppenordnungen mit nur kleinen Primfaktoren (Pohlig-Hellman, daher die Primordnung n und ein kleiner Kofaktor) und schwache Twists. Die größte öffentlich gelöste generische Instanz auf einer Kurve über einem Primkörper hat 112 Bit (secp112r1, 2009 auf einem Cluster aus PlayStation-3-Konsolen gelöst).
Der Shor-Algorithmus löst das ECDLP auf einem großen fehlertoleranten Quantencomputer in Polynomialzeit; deshalb steht jedes Verfahren auf Basis elliptischer Kurven auf der NIST-Liste für den Post-Quanten-Übergang.