We recommend 4096-bit CSIDH for NIST level 1. Why so large? Because comparing to a Grover key search against AES-128 sets a high bar for security, since the attack on CSIDH (the quantum sieve) parallelizes so well. (1/8) https://twitter.com/Saab_jc/status/1334890289216024577

This graph highlights the problem: The cost to attack each prime is flat wrt depth, but Grover search gets more expensive at lower depths. We decided to limit hardware (qubits+memory+processors), which prevents very low-depth attacks.

That is, with only 2^80 quantum/classical hardware and 2^64 depth, you can't break CSIDH-4096 but you can break AES-128. With memory limits it looks like this (different colours have different memory limits):

What about CSIDH-512? Since this is twitter I can speculate wildly

In one sense, it's dead: We estimate (including 2^10 overhead for quantum error correction) a cost of 2^63 (with free oracle) or 2^87 (with a rough guess of oracle cost). If NIST level 1 is defined relative to a single-target offline attack on AES-128, CSIDH-512 is far short.

But 2^87 is a costly quantum attack. Maybe that's enough and we should reconsider security levels? Redefining the security threshold would have a big impact on CSIDH (4096 bit key exchange takes 22 BILLION cycles) but maybe not so much for other schemes.

E.g.: The best attack on SIKE is classical, not quantum; lowering quantum security thresholds won't permit smaller SIKE keys, but would permit smaller CSIDH keys. I think other PQcrypto is more like SIKE? So CSIDH is like a canary for over-cautious quantum security thresholds.

Finally: We only use small exponents. Isogenies made from small exponents have little structure as a subset of class group elements, so we think a quantum attacker must still attack the full class group. Hence we use a tiny subset of keys and likely lose no quantum security.

Small exponents allows more efficient constant-time key exchange

Bonus: if you do decide that CSIDH-512 is quantum secure, you could do the same trick: you only need 70 exponents in {-4,...,4} for 128 bits of classical security