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.
Some ECC cryptosystems in wide use, including ECDSA and Ed25519, ECDH.. are theoretically vulnerable to quantum computing, should that ever become usable for cryptanalysis (Cryptographically Relevant Quantum Computer in NSA terminology). These cryptosystems are based on a Discrete Logarithm problem and it becomes sub-exponential w.r.t. the bit size of the unknown exponent under quantum computing assumptions.
On the other hand, there are credible ECC-based cryptosystems designed for post-quantum security, such as SIKE. Thus ECC might still be mainstream post-quantum asymmetric cryptography, but in another form.
We don't know when, if ever, quantum cryptopocalypse might occur; or how to forecast it. So far, there are few things quantum computers do better than classical ones, and that tends to be unrelated to cryptanalysis; like: simulating the quantum system that the particular quantum computer is, or perhaps (that's debated) finding a good solution to a narrow class of optimization problems.
Most of public key algorithms used today are based on two mathematical problems, the factorization of large numbers (e.g., RSA) and the calculation of discrete logarithms (e.g., DSA signatures and ElGamal encryption). Both have similar mathematical structure and can be broken with Shor’s algorithm rapidly. Recent algorithms based on elliptic curves (such as ECDSA) use a modification of the discrete logarithm problem that makes them equally weak against quantum computers. For more details refer to section 4 subsection C of the following paper which describes above statements in detail: https://arxiv.org/abs/1804.00200?context=cs
