強普遍性和強普遍性之間的區別dddelta通用雜湊函式
定義一系列強通用散列函式為：
$$ \forall x_1, x_2 \in {0,1}^n, \forall y_1, y_2 \in {0,1}^m, ~ x_1\ne x_2: ~~ \Pr_{h\in H} [h(x_1) = y_1 ~\text{and}~ h(x_2) = y_2] \le \frac{1}{2^{2m}} $$
如果 $ h: {0,1}^n \rightarrow {0,1}^m $ 和一個家庭 $ \delta $ 通用雜湊函式： $ \forall x_1, x_2 \in {0,1}^n $ 在哪裡 $ x_1 \neq x_2 $ : $$ Pr_{h \in H} [h(x_1) = h(x_2)] \leq \delta $$
（根據Moni Naor 幻燈片的定義。
然後我明白為什麼強烈普遍意味著 $ 2^{-k} $ 通用（只需選擇 $ y_2 = y_1 = h(x_1) $ )，但根據 Moni Naor 幻燈片， $ \delta $ 普遍並不意味著強烈普遍。
由於我不完全理解幻燈片上的反例（ $ h(x) = x $ ) 我正在尋找一個反例和對兩個定義之間差異的直覺描述？
這裡有兩個正交的問題軸：
- 普遍與強烈普遍。 通用雜湊族具有有限的碰撞機率：對於任何輸入 $ x \ne y $ ，它們在隨機散列函式下碰撞的機率 $ H $ 由 $ 1/t $ ， 在哪裡 $ t $ 是可能的雜湊值的數量：$$ \Pr[H(x) = H(y)] \leq 1/t. $$ （如果雜湊值是 $ m $ -位字元串，然後 $ t = 2^m $ .) 然而，雖然碰撞的機率可能會受到 $ 1/t $ ， 的知識 $ H(x) $ 可能會通知您 $ H(y) $ 對於某些對 $ x $ 和 $ y $ .
在一個強通用散列族中，有時稱為成對獨立的，這不會發生，因為任何兩個輸入的散列值 $ x \ne y $ 是獨立的均勻隨機變數：$$ \Pr[H(x) = u, H(y) = v] = \Pr[H(x) = u] \cdot \Pr[H(y) = v] = 1/t^2, $$對於任何雜湊值 $ u $ 和 $ v $ . 這被稱為成對獨立，因為它可能僅限於任何兩個變數——對於任何正整數 $ k $ ，有一個對應的概念 $ k $ -明智的獨立性。
顯然，任何成對獨立的雜湊族都是通用的（證明：練習），但反之則不成立。例如，修復一個素數 $ p $ , 並定義 $ H_1(x) = a x $ 上 $ \mathbb Z/p\mathbb Z $ 對於均勻隨機 $ a \in \mathbb Z/p\mathbb Z $ . 然後 $ H_1(x) = H_1(y) $ 方法 $ ax = ay $ , 一個事件, 對於 $ x \ne y $ , 當且僅當 $ a = 0 $ ， 所以$$ \Pr[H_1(x) = H_1(y)] = \Pr[a = 0] = 1/p. $$ 但如果 $ H_1(x) = a x = u $ , 只有一個可能的值 $ H_1(y) = a y = v $ ，即 $ v = y u/x $ ， 所以
$$ \begin{equation*} \Pr[H_1(x) = u, H_1(y) = v] = \begin{cases} 1, & \text{if $x v = y u$;} \ 0, & \text{otherwise.} \end{cases} \end{equation*} $$
因此 $ H_1 $ 不是成對獨立的，因為對於某些值 $ x $ , $ y $ , $ u $ ， 和 $ v $ , $ \Pr[H_1(x) = u, H_1(y) = v] = 1 $ 遠高於 $ 1/p^2 $ . 也就是說，如果你知道 $ x $ 和 $ y $ ，你就學會了 $ u = H_1(x) $ , 你可以完美地預測什麼 $ v $ 即使您事先不知道秘密雜湊密鑰是什麼 $ a $ 曾是。
- 通用對比 $ \delta $ -普遍的。 這只是概念的概括：您替換了界限 $ 1/t $ , 對於一個雜湊家族 $ t $ 可能的雜湊值，由邊界 $ \delta $ ，通常是的小倍數 $ 1/t $ . 有一個對應的概念 $ \delta^2 $ - 強通用雜湊族。一個 $ 1/t $ -universal 雜湊族只是通用的。一個 $ 1/t^2 $ -strongly-universal 雜湊族只是強通用的。
例如，修復一個素數 $ p $ ， 說 $ 2^{130} - 5 $ ， 然後讓 $ r \in \mathbb Z/p\mathbb Z $ 均勻隨機。對於多項式 $ f $ 超過 $ \mathbb Z/p\mathbb Z $ 最多學位 $ \ell $ ， 定義 $ H_2(f) = f(r) $ . 我們可以將消息編碼為多項式的係數 $ f $ . 如果 $ H_2(f) = H_2(g) $ 多項式 $ f \ne g $ ，那麼顯然 $ f(r) = g(r) $ ， 所以 $ r $ 是多項式的根 $ f - g $ . 但最多只有 $ \ell $ 這樣的根源。由於每 $ r $ 有機率 $ 1/p $ ， 我們有
$$ \begin{equation*} \Pr[H_2(f) = H_2(g)] = \Pr[r \mathrel{\text{is a root of}} f - g] \leq \ell/p. \end{equation*} $$
因此， $ H_2 $ 是 $ \ell/p $ -普遍的。這裡 $ \delta = \ell/p $ 是數字的小倍數 $ 1/p $ 從不同的輸出 $ H_2 $ . 這個雜湊家族 $ H_2 $ 在密碼學中值得注意，因為它是 Poly1305 消息驗證碼的基礎，它是世界上最流行的 MAC 的競爭者（與 GHASH 一起）。（關於密碼學中消息身份驗證程式碼中通用散列的歷史和作用的一些背景。）