The Offline Quantum Attack Against Modular Addition Variant of Even-Mansour Cipher

At Eurocrypt 2017, the Even-Mansour (EM) cipher was modified to thwart the attack using Simon’s algorithm: replace the XOR operation with modular addition. We call it Even-Mansour+ (EM+) cipher. Kuperberg’s algorithm can recover the key of EM+ in sub-exponential time, but it requires quantum queries (Q2 mode), making it difficult to apply in practice. In this paper, we introduce a new attack against EM+, using only classical queries and offline quantum computations (Q1 mode). The key problem we solve is how to determine whether two functions have a shift, so that by combining Kuperberg’s algorithm with Grover’s algorithm, we can recover the key of EM+ in \(O(n2^{n/3+\sqrt{n}})\) time.