Paper 2021/1601

Post-Quantum Security of the Even-Mansour Cipher

Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz

Abstract

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation $P:\{0,1{\}}^n\to \{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_E\cdot q_P\approx 2^n$. 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 $$ 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.