散列的雪崩效應的最佳比特變化機率
嚴格雪崩準則 (SAC) 是雪崩效應的形式化。如果每次對單個輸入位進行補碼，則**每個輸出位都以 50% 的機率發生變化，**這是令人滿意的。
我的問題是：
- 對於任何散列來說， 50% 的比特變化機率是*最優的，*還是只是滿足嚴格雪崩標準的最小值？
- 如果散列算法有 100% 的比特變化機率會怎樣？
考慮一個函式 $ H:{0,1}^m\to{0,1}^h $ （也就是說，從集合 $ m $ -位雙串到集合 $ h $ 位位串）。定義 $ D_n=0^n\mathbin|1\mathbin|0^{m-n-1} $ （那就是 $ m $ -bit“干擾”位串，只有位 $ n $ 放）。
根據一個可能的定義， $ H $ 當對於每個 $ m\cdot h $ 對 $ (n,i) $ 和 $ 0\le n<m $ 和 $ 0\le i<h $ , 位的算術和 $ i $ 的 $ H(M\oplus D_n)\oplus H(M) $ 為所有人計算 $ M $ 在 $ {0,1}^m $ 是 $ 2^{m-1} $ （也就是說，恰好是總和的術語數量的 50%）。
這可以擴展到具有可變大小輸入的函式（例如通常的雜湊） $ m\ge2 $ 支持，該功能滿足 SAC（注：當 $ m<2 $ 和 $ h\ne0 $ , 沒有函式滿足 SAC)。
對於任何散列來說， 50% 的比特變化機率是*最優的，*還是只是滿足嚴格雪崩標準的最小值？
也沒有。
50% 不是滿足嚴格雪崩標準的最小值。為了使 SAC 成立，輸入的 1 位變化改變任何特定的輸出位的機率必須恰好為 50%，其中該機率是在 $ 2^m $ 輸入。
加密散列的最優值是表現得像一個隨機函式，而隨機函式極不可能滿足 SAC（對於 $ m=2 $ 有機率的 $ 2^{-h} $ ，並且當 $ m $ 增長）。如果一個實際的加密雜湊 ( $ h\ge128 $ ) 滿足 SAC 的一些要求 $ m $ 和 $ 2\le m\le50 $ ，這很容易檢測到，並且在某些可能的應用程序中是一個弱點。對於大 $ m $ 和實際的安全雜湊，計算上不可能測試是否 $ H $ 是否滿足 SAC。否則說，對於大消息，實際的安全雜湊表現得好像它滿足所有計算目的的 SAC，即使它很可能不滿足。
有點有趣的問題：達到什麼 $ m $ 是否有可能獲得實際雜湊不符合 SAC 的實驗證據？
如果散列算法有 100% 的比特變化機率會怎樣？
這樣的函式必須產生它的 XOR $ m $ 輸入位，重複 $ h $ 次形成一個 $ h $ -位向量，然後與 $ h $ -bit 任意值僅依賴於 $ m $ . 無論如何，它都不是安全的加密雜湊。獨立地，它不符合 SAC。