Post-Quantum Security of the Even-Mansour Cipher

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation P:\{0,1\}ⁿ → \{0,1\}ⁿ. 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ⁿ. If the attacker is given 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 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² approx 2ⁿ 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²_P + q_P cdot q_E² approx 2ⁿ. 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.