用量子週期發現破解偶曼蘇爾密碼：意外碰撞的機率
論文Breaking Symmetric Cryptosystems using Quantum Period Finding展示瞭如何使用 Simon 算法破解 Even-Mansour 密碼。Even-Mansour 使用兩把鑰匙 $ k_1, k_2 $ 和一個隨機公共排列 $ P $ 加密消息 $ x $ :
$$ E_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2 $$
在量子已知的明文場景中，我們可以使用量子週期查找（西蒙算法）來查找周期 $ k_1 $ 在以下函式中： $$ f(x) = P(x \oplus k_1) \oplus k_2 \oplus P(x) $$ 清楚地， $ f(x) = f(x \oplus k_1) $ 到目前為止，我可以跟隨。該論文然後爭辯說，如果會有另一個時期 $ t \notin {0,k_1} $ 這樣 $$ Pr[f(x) = f(x \oplus t)] \geq \frac{1}{2} $$ 那麼 P 會有一個更高階的微分，因為它會持有： $$ 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} $$ 我不清楚為什麼。另一個時期的存在是否不僅僅意味著： $$ 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) $$ 如何從中得出高階微分？
首先，你有一個錯字[失踪 $ =0 $ ] 你需要展示的是 $$ 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} $$
如果你然後外掛的定義 $ f(x) $ 進入關係 $$ Pr[f(x)=f(x\oplus t)]\geq \frac{1}{2}, $$ 你得到 $$ 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} $$ 在一些取消後減少到所需的表達式。