Hash
為雜湊函式找到多個衝突需要多少工作？
假設輸出大小
n位的理想散列函式，發現一次碰撞需要2^(n/2)使用生日攻擊對散列函式進行近似評估。但是，需要多少次評估才能產生兩次或更多碰撞？
注意我說的是不同的碰撞，即 $ H(A)=H(B) $ , $ H(C)=H(D) $ ， ETC。
尋找的預期努力 $ k $ 輸出大小的理想散列函式上的明顯衝突 $ n $ 是關於 $ \sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}} $ （為了 $ k << 2^{n/2} $ ).
看到這一點的一種方法是查看兩個不同輸入的輸出碰撞的機率，即 $ 2^{-n} $ ; 如果我們生成輸出 $ \sqrt{2k} \cdot 2^{n/2} $ 不同的輸入，有 $ (\sqrt{2k} \cdot 2^{n/2} \cdot (\sqrt{2k} \cdot 2^{n/2}-1))/2 \approx 2^nk $ 成對的輸出；如果碰撞機率是獨立的（如果我們留下，它們大約是 $ k << 2^{n/2} $ )，那麼我們在輸出集中得到的預期碰撞次數為 $ 2^{-n} \cdot 2^nk = k $
請注意，對於 $ k=1 $ ，我們了解一下 $ \sqrt{2}\cdot 2^{n/2} $ 單個碰撞的預期輸出。這並不矛盾 $ 2^{n/2} $ 經驗法則； $ \sqrt{2}\cdot 2^{n/2} $ 是一個更精確的值。