Title | Post-Quantum Security of the Even-Mansour Cipher |
Publication Type | Journal Article |
Year of Publication | 2022 |
Authors | Alagic, G, Bai, C, Katz, J, Majenz, C |
Journal | Eurocrypt |
Date Published | 12/14/2021 |
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→{0,1}n. It is secure against classical attacks, with optimal attacks requiring qE queries to E and qP queries to P such that qE⋅qP≈2n. If the attacker is given \emph{quantum} access to both E and P, however, the cipher is completely insecure, with attacks using qE,qP=O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE⋅q2P≈2n 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 qE⋅q2P+qP⋅q2E≈2n. 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. |
URL | https://arxiv.org/abs/2112.07530 |
DOI | 10.48550/arXiv.2112.07530 |