抗碰撞雜湊函式意味著單向函式
我正在努力給出一個正式的證明 $ CRH \implies OWF $ 使用下面的定義。
直覺上，我明白為什麼 $ CRH $ 將是“難以預測”並且可能被用作 $ PRF $ ，但我無法給出正式的證明。
$ \mathcal{H} = {\mathcal{H}n = {h:{0,1}^* \rightarrow {0,1}^n }} $ 是一個 $ CRH $ 如果它可以被有效地採樣並且 $$ \forall{A;PPT} \exists_N \forall_{n>N} \Pr_{h \rightarrow H_n} [A(1^n, h) = (x, x’) \land x \neq x’ \land h(x) = h(x’)] = neg(n) $$
證明存在 $ PRG $ 或者 $ PRF $ s 就足夠了。
相關但已回答的問題here。
防碰撞意味著單向性。減少證明：如果你有算法 $ A $ 能夠反轉 $ H: b^* \rightarrow b^n $ ，我們可以建立一個算法 $ B $ 它能夠找到碰撞（以幾乎相同的時間和機率）。這裡 $ b $ 方法 $ {0,1} $ .
讓我們只考慮一些長度的輸入字元串 $ l\ge n $ . 請注意 $ H $ 拆分集合 $ b^l $ 進入以下 $ 2^n $ 類： $$ {C_h = {x: x\in b^l \land H(x)=h }}_{h\in b^n}. $$ 根據期望（如果函式隨機執行），每個類由 $ k = 2^{l-n} $ 元素。但是對於我們的具體函式，一些類可能是空的，而其中一些類的元素比其他類多。
算法 $ B $ 行為如下：
- 隨機選擇 $ x\in b^l $ 並評估 $ h = H(x) $ .
- 執行 $ A $ 在輸入 $ h $ : $ x’ = A(h) $ .
- 如果 $ x \neq x’ $ , 返回碰撞 $ (x, x’) $ . 否則轉到步驟 1。
很容易看出第 3 步成功的機率是 $ 1 - \frac{1}{k} $ （這是相當多的，你可以增加 $ k $ 或者只是做幾輪算法來實現你想要的任何機率）。解釋是：當你在採摘時 $ x $ 在第一步，你選擇一個 $ {C_h} $ 機率與類中的許多元素成正比： $ Pr[C_h] = \frac{|C_h|}{2^l} $ . 然後，在第 3 步，失敗機率，即 $ x = x’ $ ， 是 $ 1/|C_h| $ ，考慮到均勻隨機選擇 $ x $ 並且事實上 $ A $ “不知道”哪個元素 $ x $ 從課堂上 $ C_h $ 你選擇了（你只給了他 $ h $ ）。因此，常見的故障機率計算為： $$ Pr[\texttt{“failure”}] = \sum_{h\in b^n} {Pr[C_h] \cdot Pr[\texttt{“failure on C_h}”]} = \sum_{h\in b^n} {\frac{|C_h|}{2^l} \cdot \frac{1}{|C_h|}} = 2^n\cdot \frac{1}{2^l}. $$
請注意，我們不需要任何隨機屬性 $ A $ 也不 $ H $ . 我們僅使用隨機性來實現這個機率估計 $ B $ （均勻隨機選擇 $ x $ 在第 1 步）。