Elliptic Curves for Security

As I understand it, generally the big issue between 25519 and things like 448 is that you want the security level of your curve to meet the security level of the rest of your system, or else the extra work you're doing in the rest of your system is for nothing.

Quantum computing, if it ever becomes viable, will end elliptic curve discrete log cryptography.

the better five-year-old explanation is that quantum computers can perform vast numbers of 'computations', but can only report one result

it's a new and tricky mathematical problem to get that 'one result' to be anything useful, but from what i understand they are confident in their algorithms for breaking ECC wide open, given modest quantum hardware

[edit: my first sentences were absurdly badly written, retrying]

Quantum computers aren't capable of doing arbitrary computation in parallel. You need to create an algorithm that is "compatible" with a QC (these all seem to be related to waves as you can initialize a superposition of "all" the waves, and quantum Fourier transform to get fixed values you care about). What the QC provides is a single "value" representing all the answers to that problem for all the inputs, so you need some way of ensuring that when you actually read the quantum result and it collapses to one final solution, that that solution is actually the one you want.

What this means is that a quantum algorithm for some problem isn't any kind of "try all the possibilities, and select the solution". What the algorithms have to do is get the quantum computer to build up an internal state such that all the wrong answers cancel each other out, so at the end of the computation you have a stream of qubits where each qubit has a high probability of being 1 if the correct value (in the solution) for that bit is 1, and a high probability of being 0 if the correct value is 0.

Now you'll note that I'm saying probability a lot. This is one of the parts of quantum computers that people miss. When you get your "solution" out of the machine you don't know if the result is correct, because no bit ever becomes 100% zero or 100% one. The probability of getting the correct value is something like (1 - average error)^^number of qubits. This is why error bounds are important - per my reading of https://en.wikipedia.org/wiki/Shor's_algorithm, a 4096 bit number (the appropriate RSA key size) you'd need in the order of 200 million gates. Assuming error is independent that's something silly like your probability of a correct answer being (1-error level)^^200million which requires your error level be very small. The obvious solution to this problem is that you run the algorithm repeatedly and have a classical computer verify the correctness or not of the solution (it's super easy to see if the number you get from the QC is actually a factor of the number). [1]

This all means that developing a quantum algorithm that is actually doing things better than a classical one requires a lot of effort, generally a "quantum algorithm" consists of a classical algorithm with some quantum steps in the middle. That's because you can't simply run your original algorithm on the QC - that would have the same time complexity with a much larger constant because QCs are slow - instead you have to develop an equivalent-ish problem to the expensive part of the classical problem, such that you can get the "wrong answers cancel out" behaviour. You then need to be able to convert your original problem to/from the quantum problem you can solve in sub-exponential time (otherwise you're simply trading one exponential problem for another). For example, in Shor's algorithm for factorization (the thing that's relevant to modern cryptography) the quantum part is finding a value with an even period

To the final question. Shor's algorithm is actually solving the hidden sub group problem, which underlies (through math I don't understand :D) ECC and RSA, where "solving" in this case means "sub exponential complexity". RSA and ECC both rely on the known solutions not having a polynomial time solution, e.g factoring an N bit value takes e^^((N^^(1/3)*ln(N)^^(2/3)) operations, whereas shor's algorithm is afaict O(N). In this case for a 4 bit number classic factorization takes 7-8 operations, whereas shor's takes 4+the classic part. At 4096 bits (a sane RSA key size. Don't use RSA) Shor's algorithm requires 4096 operations, whereas the classical algorithm takes 33 billion billion billion. The latter number makes RSA and ECC secure, the former number is why modern cryptography is broken _if_ you can make a large enough quantum computer, with a low enough error level (I've read a bunch of arguments that sound plausible to me for why that may actually be physically impossible, but I'm sure we'll see over the next decade or so).

[1] Ok, so I've read and re-read the wikipedia page on Shor's algorithm and this does seem to be what the gate count is, but this required error level seems much worse than I remember so it would be great if someone could confirm or correct it :D