This assumes people consider practical million qubit quantum computers relevant. They might actually be impossible or close to it, i.e. millions of years away.

I'd say by far the most important thing will stay resistance to unknown classical algorithms, at least until trends change.

I just recently played with an online quantum computer simulator to get a better understanding of how quantum fourier transform works, it's a lot of fun:

https://algassert.com/quirk

I have a mind to write a PQC daemon to negotiate/rotate WireGuard pre-shared keys. Even though WireGuard uses 3-way ECDH using Curve25519, with a 256-bit pre-shared key, an attacker will either need 2^128 work using Grover's quantum search algorithm or else find statistical flaws in ChaCha20.

That way, you keep the post-quantum crypto out of the kernel, and if done carefully by hashing together PQC, ECDH, and a pre-shared-pre-key to generate the pre-shared key, it would be easier to demonstrate that it's no weaker than WireGuard. If the daemon removes and forgets the negotiated pre-shared-keys after 24 hours, then against classic attackers you'd still have perfect forward secrecy, and against quantum attackers you'd have 24-hour forward secrecy (assuming no statistical flaws in ChaCha20).

AFAIK post-quantum crypto all has larger key sizes and much(?) worse performance. Has that changed? If not, I don't see ECC becoming obsolete any time soon.

We will probably just see more tricks like computing keys from random seeds and storing cached key exchanges, and AMP style clickbait accelerators to funnel stuff through CDNs you already have the key for(Assuming the EU lets us do that....)

I thought ring-lwe was pretty good. It's at least very embarrassingly parallel

They're all worse in terms of size and/or speed, but not disastrously so.

Ring-LWE is faster than ECC, but has keys and ciphertexts of 600+B instead of as few as 32 B (for eg curve/ed25519). NTRU is pretty similar, with slower key generation and slightly smaller ciphertexts. If you go to the bleeding edge, you might be able to cut these to 300-400 bytes with severe compromises in eg error rate and security margin. There are also structured code-based systems with fairly similar sizes to the Ring-LWE ones, but they aren't finalists.

McEliece is fast to encrypt and decrypt and has small ciphertexts (as few as 128 bytes), but has enormous public keys (multi-hundred KB) that are also slow to generate. The biggest benefit of McEliece is that we're pretty confident it will hold up to analysis.

SIKE (an alternate) has reasonable keys and ciphertexts (200-250 B) but is pretty slow, on the order of 5ms on a laptop for the smallest parameters. The bleeding-edge CSIDH is much slower, but has even smaller keys, but we can't be at all confident that CSIDH is secure.

On the sig side, Falcon is fast but extremely complicated, and has as low as ~660B sigs. Its main competitor, Dilithium, is modestly slower and larger, and also significantly simpler. The much more conservative SPHINCS+ is very slow and produces ~8kB sigs.

Depends on how quickly quantum computer size grows? We don't seem to have anything resembling a Moore's Law yet

The Cloud Security Alliance is assuming something powerful enough shall exist in under 8 years.

https://cloudsecurityalliance.org/press-releases/2022/03/09/...

But their job is to figure the realistic worst case I.e fastest plausible timeoine. Not the most likely / expected time it will take.

I'm very excited to see the results of the post-quantum crypto competition. Most of it is above my head, but it's neat to read about lattice problems. Asymmetric cryptography in general is incredible to me.

also, elliptic curves are much more vulnerable to quantum attacks than regular rsa since it uses smaller keys.

I wouldn't say more vulnerable necessarily — it requires fewer qubits, but requires larger coherence time. RSA requires more qubits and drastically less time. They're both vulnerable in different ways.

Isn't coherence time the big challenge?

I imagine it's a similar tradeoff - with more qubits there are more interactions, ergo lower coherence time