Phá vỡ mật mã chẵn-Mansour bằng việc tìm kiếm chu kỳ lượng tử: Xác suất xảy ra xung đột không mong muốn

Giấy Phá vỡ các hệ thống mật mã đối xứng bằng cách sử dụng Tìm kiếm thời kỳ lượng tử chỉ ra cách phá Mật mã Even-Mansour bằng thuật toán của Simon. Even-Mansour sử dụng hai phím $k_1, k_2$ và một hoán vị công khai ngẫu nhiên $P$ để mã hóa một tin nhắn $x$:

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

Trong một kịch bản bản rõ đã biết lượng tử, chúng ta có thể sử dụng phép tìm chu kỳ lượng tử (thuật toán của Simon), để tìm khoảng thời gian $k_1$ trong hàm sau: $$f(x) = P(x \oplus k_1) \oplus k_2 \oplus P(x)$$ Thông suốt, $f(x) = f(x \oplus k_1)$ Cho đến nay tôi có thể làm theo. Sau đó, bài báo lập luận rằng nếu có một khoảng thời gian khác $t \notin \{0,k_1\}$ như vậy mà $$Pr[f(x) = f(x \oplus t)] \geq \frac{1}{2}$$ Sau đó, sẽ có một vi phân bậc cao hơn cho P, bởi vì khi đó nó sẽ giữ nguyên: $$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}$ $ Tôi không rõ tại sao. Liệu sự tồn tại của một thời kỳ khác không chỉ ngụ ý rằng: $$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)$$ Làm thế nào có thể theo dõi sự khác biệt bậc cao hơn từ đó?