Linear-Cryptanalysis
隨機排列上的近似值的相關性
我讀了一篇關於線性密碼分析的論文，它是 J.Daemen 等人的Probability distribution of correlation and Differences in block cipher。
在本文的引理 8 的證明中，我無法理解這個公式（第 13 頁）。
平衡布爾函式的數量 $ g(a) $ 對於給定的值 $ x $ 是 ：
$$ {{2^{n-1}} \choose {2^{n-2}+x}} {{2^{n-1}} \choose {2^{n-2}-x}} = {{2^{n-1}} \choose {2^{n-2}+x}}^2 $$ 和
如果我們將其除以平衡布爾函式的總數，……”
請告訴我這個公式是如何得出的。
所以 $ x $ 測量真值表左半部分與平衡的偏差，說它是長度左半部分中 1 的多餘數量 $ 2^{n-1} $ . 根據二項式係數的定義，有$$ \binom{2^{n-1}}{2^{n-2}+x} $$這樣的載體。這是第一個因素。第二個因素是缺失向量的數量 $ x $ 1，因為整體真值表是平衡的。
使用$$ \binom{a}{b}=\binom{a}{a-b} $$完成論證。