Q = d·G の計算は、バイナリ法（double-and-add）やラダーを使えば数百回の点演算で済みますが、適切に選ばれた曲線では、その逆を効率よく解く古典アルゴリズムは知られていません。最良の汎用攻撃である Pollard のロー法は、素数位数 n の群に対して約 √(πn/4) 回の群演算を必要とするため、256 ビットの曲線は約 128 ビットのセキュリティを提供します。有限体の離散対数と素因数分解を準指数時間で解く指数計算法は素体上の曲線には適用できず、これが EC 鍵が RSA 鍵よりはるかに短くて済む理由です。
曲線は、既知の近道を避けるように選ばれます。避けるのは、アノマラス曲線（Smart の攻撃）、埋め込み次数が小さい曲線（ペアリングで問題を移す MOV 攻撃。ペアリングフレンドリー曲線は、まさにこの性質を意図的に受け入れています）、小さな素因数しか持たない群の位数（Pohlig–Hellman 法。そのため位数 n は素数とし、コファクターは小さくします）、そして弱いツイストです。素体上の曲線で公開されている汎用的な解読例の最大は 112 ビット（secp112r1。2009年に PlayStation 3 のクラスターで解かれました）です。
Shor のアルゴリズムは、大規模な誤り耐性量子コンピューター上で ECDLP を多項式時間で解きます。そのため、すべての楕円曲線方式が NIST のポスト量子暗号への移行対象リストに入っています。