為什麼雙重雜湊通用雜湊函式仍然是通用雜湊函式？
這是通用雜湊函式的定義 $ h \in H $ （通用雜湊函式族）
$$ \forall x, y \in U x \neq y : Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m} $$ 雙散列如下
$$ h_a , h_b \in H $$ $$ h_i(x, m) = (h_a(x) + i \times h_b(x)) \mod m $$ 是否有證據表明對任意兩個通用函式進行雙重散列 $ i $ 會產生另一種通用功能嗎？
如果
$$ k = (h_a(x) + h_b(x)) $$ 我們不能說有嗎 $ k + 1 $ 更多碰撞方式？
$$ 5 = 0 + 5, 1 + 4, 2 + 3, 3 + 2, 4 + 1, 5 + 0 $$
是否有證據表明對任意兩個通用函式進行雙重散列 $ i $ 會產生另一種通用功能嗎？
如果 $ i $ 是固定的，那麼沒有， $ h_i $ 不必是通用的。
舉一個簡單的反例，考慮 $ U $ 它由2個元素和 $ H $ 它由 1 個元素組成 $ h $ ， 和 $ \alpha $ 和 $ \beta $ ， 和 $ h(\alpha) = 0 $ 和 $ h(\beta) = 1 $ . 很容易看出 $ H $ 是通用的。
但是，如果我們選擇 $ i = m-1 $ ， 然後 $ h_i(x, m) $ 不是通用的（因為兩個可能的輸入都為 0 $ x $ ).
現在，讓我們考慮在哪裡 $ i $ 是均勻分佈的；也就是家庭 $ H’ $ 那 $ h_i(x, m) $ 屬於 包含所有 $ i $ 價值觀。
那麼，如果 $ m $ 是複合的，答案仍然是否定的。類似的反例：假設 $ a $ 是一個適當的因素 $ m $ ; 然後，考慮 $ H $ 它由 1 個元素組成 $ h $ ， 和 $ h(\alpha) = 0 $ 和 $ h(\beta) = a $
然後， $ h_i(\alpha, m) = h_i(\beta, m) $ 有機率 $ a/m $ ; 不是通用的。
另一方面，如果 $ m $ 是素數，那麼 $ h_i $ 必然是普遍的（我們不需要假設 $ h_b $ 邊是通用的）；這可以顯示為任何兩個不同的輸入 $ \alpha, \beta $ 通過簡單的案例分析（這兩種情況下的機率都是 $ \le 1/m $ ):
- 如果 $ h_b(\alpha) = h_b(\beta) $ ，那麼機率是 $ \le 1/m $ （由於普遍性 $ h_a $ )
- 如果 $ h_b(\alpha) \ne h_b(\beta) $ ，則有唯一值 $ i $ 和 $ h_a(\alpha) + i h_b(\alpha) = h_a(\beta) + i h_b(\beta) \mod m $ , 並且有 $ m $ 的可能值 $ i $ , $ i $ 將是具有機率的唯一值 $ 1/m $