How effective is quantum computing against elliptic curve cryptography? I've been reading the Wikipedia page on Elliptic-Curve Cryptography and I came across the following.


  in August 2015, the NSA announced that it plans to replace Suite B with a new cipher suite due to concerns about quantum computing attacks on ECC. Elliptic-Curve Cryptography


My question is, how vulnerable is ECC to quantum computing?
Elliptic curve cryptography is not presently vulnerable to quantum computing because there are no quantum computers big and reliable enough to matter.

But it would be vulnerable to quantum computers big enough to run Shor's algorithm.  All elliptic curve cryptography* is based on the difficulty of finding a secret integer $n$ given the scalar multiple $Q = [n]P = P + \cdots + P$ of a base point $P$ on an elliptic curve, say $E/k\colon y^2 = x^3 + 486662 x^2 + x$ where $k$ is the prime field $\operatorname{GF}(2^{255} - 19)$, a curve popularly known as Curve25519.†

On a capable quantum computer, Shor's algorithm would rapidly find a period $(\delta, \gamma)$ of the function $(a, b) \mapsto [a]P - [b]Q$.  Any such period satisfies $$[a - b n]P = [a]P - [b]Q = [a + \delta]P - [b + \gamma]Q = [a + \delta - (b + \gamma)n]P$$ for any $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma n \pmod \ell$, where $\ell$ is the order of $P$, from which we can trivially recover $n \equiv \delta \gamma^{-1} \pmod \ell$.

The number of qubits, and number of gates, and running time to compute this is a small polynomial function of the number of bits in the order $\ell$, which is ~256 in typical cryptography.  Most of the quantum circuit would be devoted to computing scalar multiplication, just like computing scalar multiplication on a classical computer, costing $O(\operatorname{poly} \log \ell)$ quantum gates just like it costs $O(\operatorname{poly} \log \ell)$ time and memory on a classical computer; the magic happens in the quantum Fourier transform to find a period, which costs only $O(\log \ell \cdot \log \log \ell)$ quantum gates.

The danger today is primarily for long-term secrecy of documents and conversations in the face of future quantum cryptanalysis: TLS key agreements with elliptic curve Diffie–Hellman, for example, could be attacked with Shor's algorithm, just like finite-field Diffie–Hellman, enabling retroactive decryption of TLS sessions.  (The ‘forward secrecy’ property of DH—or really, the erasure of session keys by all parties involved—is of no use if the adversary can break the key agreement cryptography.)  For authentication and signature, e.g. Ed25519 signatures, the danger is not so much as long as you have an upgrade path for changing the signature scheme by the time Shor-capable quantum computers become feasible.



* I am not addressing isogeny-based cryptography, such as SIDH or CSIDH or SIKE, which also involve elliptic curves but which are all based on problems other than elliptic curve discrete logs—problems that are conjectured to remain infeasible to break even if Shor-capable quantum computers were practical.

† This is not the only way to attack elliptic curve cryptography.  There are many other issues to worry about, as catalogued in SafeCurves.  But in a well-designed protocol with a well-designed curve, the best known way to break the cryptography is to compute discrete logs.