Paper 2021/1601

Post-Quantum Security of the Even-Mansour Cipher

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


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 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 $E$ implemented by honest parties, 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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2022
Contact author(s)
galagic @ gmail com
jkatz2 @ gmail com
chmaj @ dtu dk
cbai1 @ terpmail umd edu
2022-03-03: last of 2 revisions
2021-12-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz},
      title = {Post-Quantum Security of the Even-Mansour Cipher},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1601},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.