### 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 \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)
Category
Secret-key cryptography
Publication info
Keywords
QuantumEven-Mansour
Contact author(s)
galagic @ gmail com
jkatz2 @ gmail com
chmaj @ dtu dk
cbai1 @ terpmail umd edu
History
2022-03-03: last of 2 revisions
See all versions
Short URL
https://ia.cr/2021/1601

CC BY

BibTeX

@misc{cryptoeprint:2021/1601,
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{https://eprint.iacr.org/2021/1601}},
url = {https://eprint.iacr.org/2021/1601}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.