Post-Quantum Security Analysis 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}^n -- {0,1}^n. 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 q_E queries to E and q_P queries to P such that q_P × q_E ≈ 2^n. If the attacker is given quantum access to both E and P, however, the cipher is completely insecure, with attacks using q_P = q_E = 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, while retaining quantum access to P. Attacks in this setting with q_P^2 × q_E ≈ 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 open question, showing that any attack in this post-quantum setting requires q^2_P × q_E + q_P × q_E^2 ≈ 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.