2021/12/14 by Gorjan Alagic, Alagic, Gorjan, Chen Bai +5 · 4 citations
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.2112.07530
19+4 pages
arxiv created 2021/12/14 · arxiv updated 2021/12/15
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 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 classical access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE ⋅ qP2 ≈ 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 ⋅ qE2 ≈ 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.