  The Even-Mansour cipher is a simple method for constructing a (keyed)
pseudorandom permutation $E$ from a public random permutation~$P:\{0,1\}^n
\rightarrow \{0,1\}^n$. It is secure against classical attacks, with optimal
attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_E
\cdot q_P \approx 2^n$. If the attacker is given \emph{quantum} access to both
$E$ and $P$, however, the cipher is completely insecure, with attacks using
$q_E, q_P = O(n)$ queries known.
  In any plausible real-world setting, however, a quantum attacker would have
only \emph{classical} access to the keyed permutation~$E$ implemented by honest
parties, even while retaining quantum access to~$P$. Attacks in this setting
with $q_E \cdot q_P^2 \approx 2^n$ are known, showing that security degrades as
compared to the purely classical case, but leaving open the question as to
whether the Even-Mansour cipher can still be proven secure in this natural,
"post-quantum" setting.
  We resolve this question, showing that any attack in that setting requires
$q_E \cdot q^2_P + q_P \cdot q_E^2 \approx 2^n$. Our results apply to both the
two-key and single-key variants of Even-Mansour. Along the way, we establish
several generalizations of results from prior work on quantum-query lower
bounds that may be of independent interest.
