Post-quantum security of the Even-Mansour cipher
Chen Bai, University of Maryland, College Park
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.
Join the seminar on Zoom
Meeting link: IQC-QuICS Math and Computer Science Seminar
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Adam Bene Watts (adam.benewatts1@uwaterloo.ca).