Hash
散列函式的抗碰撞性的正式定義
在我的密碼學課上，教授說固定散列函式的抗碰撞性不是一個“精確”的定義。原因是由於固定的雜湊函式是計算問題的單個實例，因此它並不難（至少對於抗碰撞的某種精確和完整的定義）。請注意，並不是說我們知道固定散列函式的解決方案。但是，該定義似乎對雜湊函式族更有意義。因此，這更像是一個理論問題，而不是“實踐中”。
你會如何解釋這一點？
定義固定散列函式的抗碰撞性 $ H $ ，它可能看起來像這樣：
CR：沒有有效的攻擊者（即具有多項式計算資源）可以找到兩條消息 $ m_0\neq m_1 $ 這樣 $ H(m_0)=H(m_1) $ 以不可忽略的機率。
然而，這是有問題的，因為這樣的攻擊者可能確實存在，但我們不能輕易找到它。從鴿巢原理，我們可以肯定地知道有兩個碰撞消息 $ H $ . 因此，存在一個非常有效的攻擊者，他可以簡單地輸出這兩條消息並破壞上述安全性。
為了解決這個問題，人們可能會嘗試將CR改寫為“很難建構攻擊者……”。但是後來你被困在正式定義“難以建構”上，而在實踐中這是可以的。
所以，一個簡單的解決方法是引入一個大的密鑰空間 $ K $ 這樣任何高效的攻擊者都很難為隨機選擇的雜湊函式輸出衝突消息 $ H_k $ （在哪裡 $ k\gets K $ ）。請注意，即使為攻擊者提供了所有鍵的所有衝突消息，與使用固定雜湊函式的情況相比，它也無法輕鬆“消化”它們，因為儲存所有衝突消息需要指數級大的空間（與鍵空間的大小成線性關係） ) 而攻擊者只有多項式計算資源。