PRF 中的碰撞機率
我的問題與此有關：
假設我們有一個偽隨機函式如下：[PRF:{0,1}l×{0,1}t→{0,1}mMath Processing Error]， 在哪裡[lMath Processing Error]是安全參數。另外，假設[k,k′←{0,1}lMath Processing Error]是兩個獨立的隨機密鑰和[r1,r2←{0,1}tMath Processing Error]是兩個獨立的隨機值。 $ PRF: {0,1}^{l}\times{0,1}^{t}\rightarrow{0,1}^{m} $ $ l $ $ k,k’\leftarrow {0,1}^{l} $ $ r_1,r_2 \leftarrow {0,1}^{t} $
問題1：機率是多少 $ PRF(k,r_1)=PRF(k’,r_2) $
問題 2：如果我們替換，問題 1 中的機率是否會有所不同 $ r_1, r_2 $ 具有固定值 $ i $ , 機率 $ PRF(k,i)=PRF(k’,i) $ ?
你聲稱 $ k $ , $ k’ $ 是獨立和統一選擇的。假設這些密鑰除了以這種方式作為 PRF 密鑰外，其他任何地方都沒有使用，並且 PRF 密鑰的長度至少是安全參數，那麼您可以應用 PRF 的安全性。如果保證 PRF 輸入的關鍵部分是隨機選擇的，那麼碰撞阻力似乎與我無關。您的問題的答案與以下問題的答案幾乎可以忽略不計：
- 機率是多少 $ R(r_1) = R’(r_2) $ 在哪裡 $ R $ 和 $ R’ $ 是獨立的隨機函式嗎？
這裡的分佈很明顯 $ r_1 $ 和 $ r_2 $ 無關緊要。輸出 $ R(r_1) $ 和 $ R’(r_2) $ 均勻/獨立分佈。所以它們與機率相等[1/2mMath Processing Error]. $ 1/2^m $
所以你的問題的答案似乎是“微不足道地接近[1/2mMath Processing Error]’’ 其中微不足道的金額是您的 PRF 的安全損失。如果[mMath Processing Error]很大，那麼 PRF 安全損失可能會壓倒[1/2mMath Processing Error]學期。如果[mMath Processing Error]很小（例如，恆定），那麼安全損失可能會相形見絀[1/2mMath Processing Error]學期。 $ 1/2^m $ $ m $ $ 1/2^m $ $ m $ $ 1/2^m $