Collision-Resistance
漸近散列函式和具體散列函式
我正在閱讀Collision-Resistant Hashing: Towards Making UOWHFs Practical，他們
說它的形式化是非漸近的。為什麼形式化是非漸近的？
什麼是具有漸近形式化的雜湊函式的範例？
漸近形式化只關心安全參數變得“足夠大”時會發生什麼。由於我們（本質上）使用一個固定的安全參數，因此當然可以建構對某些固定安全參數不安全的密碼系統，但在漸近形式化中是安全的。
這意味著非漸近形式化比漸近形式化更受歡迎（儘管後者可能“更乾淨”）。
一個愚蠢的例子是壓縮函式的以下構造（它應該存在於合理的數論假設下）：
為了 $ n \leq 10000 $ ， 讓 $ p_n = 10^n $ . 為了 $ n > 10000 $ ， 讓 $ u_n $ 是由第一個組成的整數 $ n $ 十進制數字 $ \pi $ ， 然後讓 $ p_n $ 是大於的最小安全素數 $ u_n $ . 讓 $ g=4 $ 和 $ h_n $ 是我們從第一個得到的整數 $ n $ 十進制數字 $ e $ .
讓 $ f_n:{0,1,\dots,\lfloor (p_n-1)/2 \rfloor}^2 \rightarrow {0,1,\dots,p_n-1} $ 定義為
$$ f_n(x,y) = g^x h_n^{2y} \bmod p_n . $$ 在合理的數論假設下（漸近地難以計算 $ h_n^2 $ 到基地 $ g $ 模組 $ p_n $ )，這是漸近抗碰撞的。但是對於任何安全參數 $ n $ 我們想使用的，很容易找到碰撞。
（請注意，我們可以翻轉這個結構來獲得一個壓縮函式族（在合理的假設下）對於我們想要使用的任何安全參數都是抗衝突的，但漸近不安全。）