Collision-Resistance
防撞功能 - 定義
讓 $ f $ 是一個抗碰撞函式，即在計算上不可能找到 $ x_0, x_1 $ 這樣 $ f(x_0) = f(x_1) $ . 如果一個計算有界的對手證明他知道一些 $ x_0 $ 和 $ f(x_0) $ ，在什麼意義上他無法確定 $ x_1 $ ?
我的直覺是，他只能從域中隨機猜測 $ f $ 但這是如何定義碰撞阻力的嗎？此外，如果 $ f $ 有一個陷門，定義是否仍然相同，即抗碰撞意味著對手要麼知道陷門，要麼他只能從域中選擇一個隨機元素 $ f $ ?
我很抱歉這是一個是/否的問題，儘管如果答案是否定的，那麼還有更多要說的！
編輯：或者，捕捉沒有有效算法來發現碰撞的想法的數學陳述是什麼？
讓范圍 $ Y $ 功能的 $ f $ 有大小 $ N $ 抗碰撞函式不能比均勻映射到的理想函式更好 $ Y $ 因為碰撞機率被均勻分佈最小化。因此，給定 $ (x_0,f(x_0)) $ 號碼 $ k $ 隨機點 $ x_i\neq x_0 $ 必須在機率之前嘗試 $ f(x_i)=f(x_0) $ 很重要，至少可以這麼說 $ 1/2 $ 是 $ k\approx \sqrt{\ln 2 N} $ 由生日悖論。
如有必要，請參閱@fgrieu 關於生日悖論數學的詳細文章。