為什麼可以任意壓縮函式映射{0,1}米+2米→{0,1}米{0,1}米+2米→{0,1}米{0,1}^{m+2^m} rightarrow {0,1}^m不認真考慮抗碰撞？

我最近收到了一個我想在這里分享的問題，因為對於第一次深入研究 Merkle-Damgård 雜湊結構的人來說，答案可能有用（或者至少很有趣）。

我們知道 Merkle-Damgård 雜湊函式是基於固定大小的 $ {0,1}^{m+t} \rightarrow {0,1}^m $ 壓縮功能。

為什麼可以任意壓縮函式映射 $ {0,1}^{m+2^m} \rightarrow {0,1}^m $ 不認真考慮抗碰撞？

有兩種情況。在第一種情況下， $ m $ 非常小，在這種情況下，您可以通過生日悖論找到碰撞。在第二種情況下， $ m $ 不是很小，並且 $ 2^m $ 太大而不能被認為是可行的。這個論點在具體設置中是顯而易見的（考慮 $ m=64 $ ; 這是小得離譜的，碰撞可以在剛剛找到 $ 2^{32} $ 時間，但一個消息 $ 2^{64} $ 大小不可行）。

漸近地，可以提出相同的論點。為了使該功能具有抗碰撞性，您必須具有 $ m=\omega(\log n) $ ， 在哪裡 $ n $ 是安全參數。這是必要的，否則 $ \sqrt{2^m} = \sqrt{n} $ 這是非常小的（特別是多項式）。否則，具體來說，請考慮 $ m=\log n\log\log n $ . 在這種情況下 $ 2^m = 2^{\log n\log\log n} = n^{\log n} $ ，這不是多項式。但是，這意味著無法使用長度輸入執行函式 $ 2^m $ .

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