Quantum computers can break the RSA and El Gamal public-key cryptosystems,
since they can factor integers and extract discrete logarithms. If we believe
that quantum computers will someday become a reality, we would like to have
\emph{post-quantum} cryptosystems which can be implemented today with classical
computers, but which will remain secure even in the presence of quantum
attacks.

In this article we show that the McEliece cryptosystem over rational Goppa
codes resists precisely the attacks to which the RSA and El Gamal cryptosystems
are vulnerable---namely, those based on generating and measuring coset states.
This eliminates the approach of strong Fourier sampling on which almost all
known exponential speedups by quantum algorithms are based. Specifically, we
show that the natural case of the Hidden Subgroup Problem to which the McEliece
cryptosystem reduces cannot be solved by strong Fourier sampling, or by any
measurement of a coset state. We start with recent negative results on quantum
algorithms for Graph Isomorphism, which are based on particular subgroups of
size two, and extend them to subgroups of arbitrary structure, including the
automorphism groups of Goppa codes. This allows us to obtain the first rigorous
results on the security of the McEliece cryptosystem in the face of quantum
adversaries, strengthening its candidacy for post-quantum cryptography.
Additionally, we establish a variant of a conjecture of Kempe and Shalev on the
subgroups of $S_n$ that can be efficiently reconstructed by quantum Fourier
sampling.