Universal-Hash
具有同態 XOR 屬性的通用雜湊函式
讓 $ H = {h_r : U \rightarrow [m]} $ . 目前已知的最有效的算法是什麼？ $ H $
- 是一個普遍的家庭，並且
- 滿足同態異或運算性質 $ \forall h \in H \forall x,y \in U: h(x \oplus y) = h(x) \oplus h(y) $ ?
我相信來自GCM的內部 GHASH 函式將滿足該標準（如果您修剪長度字，並且僅要求具有相同長度輸入的通用性
$$ 1 $$); 它可以定義為： $$ \operatorname{GHASH}k( M_n, M{n-1}, …, M_0 ) = \sum k^i M_i $$
隨著輸入 $ M_n, M_{n-1}, …, M_0 $ 將輸入消息劃分為 128 位塊， $ k $ 作為通用散列鍵，以及在欄位上完成的算術（加法和乘法） $ \operatorname{GF}(2^{128}) $
它符合以下標準：
- 它是通用的（對於等長消息）；對於隨機 $ k $ 和任何兩個不同的等長消息 $ M, M’ $ ， 我們有 $ \operatorname{GHASH}_k(M) = \operatorname{GHASH}_k(M’) $ 有機率 $ \le |M| / 2^{128} $
- 它滿足您的同質化要求；這是因為在 $ \operatorname{GF}(2^{128}) $ 是異或，我們有 $ k^i M_i \oplus k^i M’_i = k^i( M_i \oplus M’_i) $
- 它非常有效（尤其是使用 AES-NI 指令）；我不能說它是最有效的……
$$ 1 $$：你不能同時保持同態屬性和普遍性（跨越不同長度的消息）。同態性質要求 $ h_k(0) = 0 $ 然後 $ h_k(00) = 0 $ ，因此我們有兩個不同的消息 $ 0 $ 和 $ 00 $ 它以高機率（實際上是 1）散列到相同的值，因此 $ h_k $ 不是一個通用的雜湊族。