Post-Quantum Security of the Even-Mansour Cipher

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation from a public random permutation. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring
queries to and queries to such that . If the attacker is given *quantum* access to both and, however, the cipher is completely insecure, with attacks using queries known.  In any plausible real-world setting, however, a quantum attacker would have only *classical* access to the keyed permutation implemented by honest parties, while retaining quantum access to . Attacks in this setting with 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 . 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.