Recently, Castryck, Lange, Martindale, Panny, and Renes proposed
CSIDH (pronounced "sea-side") as a candidate post-quantum
"commutative group action." It has attracted much attention and
interest, in part because it enables noninteractive
Diffie-Hellman-like key exchange with quite small
communication. Subsequently, CSIDH has also been used as a foundation
for digital signatures. In 2003-04, Kuperberg and then Regev gave asymptotically
subexponential quantum algorithms for "hidden shift" problems, which
can be used to recover the CSIDH secret key from a public key. In
2013, Kuperberg gave a follow-up quantum algorithm called the
collimation sieve ("c-sieve" for short), which improves the
prior ones, in particular by using exponentially less quantum memory
and offering more parameter tradeoffs. While recent works have
analyzed the concrete cost of the original algorithms (and variants)
against CSIDH, there seems not to have been any consideration of the
c-sieve. This work fills that gap. Specifically, we generalize Kuperberg's
collimation sieve to work for arbitrary finite cyclic groups, provide
some practical efficiency improvements, give a classical (i.e.,
non-quantum) simulator, run experiments for a wide range of parameters
up to and including the actual CSIDH-512 group order, and concretely
quantify the complexity of the c-sieve against CSIDH. Our main conclusion is that the proposed CSIDH-512 parameters provide
relatively little quantum security beyond what is given by the cost of
quantumly evaluating the CSIDH group action itself (on a uniform
superposition). The cost of key recovery is, for example, only
about $2^{16}$ quantum evaluations using $2^{40}$ bits of quantumly
accessible classical memory (plus insignificant other
resources); moreover, these quantities can be traded off against each
other. (This improves upon a recent estimate of $2^{32.5}$ evaluations
and $2^{31}$ qubits of quantum memory, for a variant of
Kuperberg's original sieve.) Therefore, under the plausible
assumption that quantum evaluation does not cost very much more than
indicated by a recent "best case" analysis, CSIDH-512 does not
achieve the claimed 64 bits of quantum security, and it falls well
short of the claimed NIST security level 1 when accounting for the
MAXDEPTH restriction.