# Breaking the Even-Mansour Cipher with Quantum Period Finding: Probability of unwanted collision

The paper Breaking Symmetric Cryptosystems using Quantum Period Finding shows how to break the Even-Mansour Cipher using Simon's algorithm. The Even-Mansour uses two keys $$k_1, k_2$$ and a random public permutation $$P$$ to encrypt a message $$x$$:

$$E_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$$

In a quantum known plaintext scenario we can use quantum period finding (Simon's algorithm), to find the period $$k_1$$ in the following function: $$f(x) = P(x \oplus k_1) \oplus k_2 \oplus P(x)$$ Clearly, $$f(x) = f(x \oplus k_1)$$ So far I can follow. The paper then argues that if there would be another period $$t \notin \{0,k_1\}$$ such that $$Pr[f(x) = f(x \oplus t)] \geq \frac{1}{2}$$ Then there would be a higher higher order differential for P, because then it would hold that: $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)] \geq \frac{1}{2}$$ It is unclear to me why. Would the existence of another period not merely imply that: $$P(x \oplus k_1) \oplus P(x) = P(x \oplus k_1 \oplus k_1) \oplus P(x \oplus k_1) = P(x \oplus t \oplus k_1) \oplus P(x \oplus t) = P(x \oplus t \oplus k_1 \oplus k_1) \oplus P(x \oplus t \oplus k_1)$$ How can the higher-order differential be followed from that?

Firstly, you have a typo [missing $$=0$$] what you need to show is that $$Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1)=0] \geq \frac{1}{2}$$
If you then plugin the definition of $$f(x)$$ into the relation $$Pr[f(x)=f(x\oplus t)]\geq \frac{1}{2},$$ you get $$Pr\left[P(x \oplus k_1) \oplus k_2 \oplus P(x) = P(x \oplus k_1 \oplus t) \oplus k_2 \oplus P(x \oplus t)\right]\geq \frac{1}{2}$$ which reduces to the desired expression after some cancellation.
• Thanks much! Could you also explain to me the derivation of the same argument for the LRW construction construction (page 13)? There, the function is $f(x) = E_K[x \oplus h(t_0)] \oplus h(t_0) \oplus E_k[x \oplus h(t_1)] \oplus h(t_1)$ and we want to show $Pr[E_k[x] \oplus E_k[x \oplus s] \oplus E[x \oplus t] \oplus E_K[x \oplus s \oplus t]] \geq 1/2$ if the probability of an unwanted collision is greater than $1/2$, where the period is $s = h(t_0) \oplus h(t_1)$ Mar 28, 2022 at 22:05