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?
