通用雜湊的機率如何計算？

嘿，對於通用雜湊，我們說以下內容：

定義：

隨機算法 $ H $ 用於構造散列函式 $ h\colon U \to {1,\ldots,M} $ 如果對所有人 來說都是通用的 $ x \neq y $ 在 $ U $ ， 我們有 $ \Pr_{h\gets H} [h(x) = h(y)] \leq 1/M $

我實際上只是無法理解機率如何 $ 1/M $ 任何狀況之下。我總是嘗試以任何隨機函式 mod M 為例，並將其與擲骰子進行比較，但是對於每個例子，我們有一個 1/6 的機率，因為我們有 mod M 的 1/M。但是當我擲骰子時我至少有兩次骰子 $ \frac{1}{6}^2 $ 但是說我們有二項式機率，認為骰子會被拋出 y 次看起來更糟。

您能幫我理解在這種情況下如何達到 1/m 嗎？

實際上 2 次骰子擲出相同值的機會是 1\6，而不是 1\36。定義還比較了 2 個值。

您要問的是https://en.wikipedia.org/wiki/Birthday_problem，即使使用通用散列，它仍然存在。或擲骰子。如果多於 2 個進行比較。

引用自：https://crypto.stackexchange.com/questions/86860