Complexity
為什麼差分密碼分析複雜度與機率倒數呈線性關係，而線性密碼分析與偏差倒數呈二次方關係？
我試圖了解差分密碼分析的複雜性與線性密碼分析的複雜性的分析。
- 在差分密碼分析中，所需文本的數量是 $ \mathcal{O} {\left( \frac{1}{p} \right)} $ 在哪裡 $ p := Pr(\alpha \to \beta) $ 對於一些差異 $ \alpha $ 和 $ \beta $
- 線上性密碼分析中，所需文本的數量是 $ \mathcal{O} {\left( \frac{1}{\epsilon ^ 2} \right)} $ 在哪裡 $ \epsilon $ 是一些mask的bias，即 $ \epsilon = | Pr(\lambda \to \gamma) - 1/2| $
我不明白為什麼複雜性線上性情況下變成二次方？例如，如果我們線上性密碼分析中使用機率而不是偏差，為什麼複雜度與 $ \frac{1}{Pr(\lambda \to \gamma)} $ .
我試圖閱讀 Ali Aydın Selçuk 的論文On Probability of Success in Linear and Differential 密碼分析，但我仍然不知道為什麼。
我不明白為什麼複雜性線上性情況下變成二次方？
好吧，線上性密碼分析中，對於每個輸入，我們都會得到一些偏差 $ 0.5 \pm \epsilon $ ，我們需要確定該偏差是否為 $ 0.5 + \epsilon $ 或者是否 $ 0.5 - \epsilon $
如果我們要查詢一個隨機位（即沒有偏差的位） $ n $ 時間並對結果求和，我們將得到一個值 $ 0.5n + \lambda \sqrt{n} $ , 對於某些分佈 $ \lambda $ 標準差約為 1
$$ 1 $$; 它會花時間 $ \epsilon^{-2} $ 我們試圖測量的偏差樣本在 $ \lambda \sqrt{n} $ 系統中固有的雜訊。 這種“我們需要克服系統內的雜訊”效應不會發生在差分密碼分析中，因為在 DC 中，我們希望差分能夠保持多個位，因此我們基本上可以忽略差分沒有的情況’不保持在內部，但差值恰好保持在輸出上。
實際上，如果我們使用截斷的差分，這可能不是那麼正確，在這種情況下，我們可能需要擔心誤報，給我們一個更接近線性密碼分析案例的分析……
$$ 1 $$: 其實標準差是 $ 0.5 $ ; 稍小的預期雜訊量不會改變分析。